Proving by induction on $n$ that $\sum \limits_{k=1}^n (k+1)2^{k} = n2^{n+1} $

Question

Alright so here is what I've got so far.

$$\sum_{k=1}^n (k+1)2^{k} = n2^{n+1} $$

---

Base Case: ($n = 1$)

LHS:

$\sum \limits_{k=1}^n (k+1)2^{k} = (2)2^{1} = 4 $

RHS:

$\ n2^{n+1} = 1(2^{2}) = 4 $

LHS = RHS

---

Inductive Case:

LHS for $n+1$

$\sum \limits_{k=1}^n (k+1)2^{k} + ((n+1) +1)2^{n+1} $

---

I'm not sure how to progress from here.

I am a complete beginner to induction and this as far as I could make it with my notes.

My best guess is to use induction hypothesis but I'm not sure how that works.

If you could explain your steps and the reasoning behind them I would appreciate it.

Answer 1

Hints:

It always a very good idea to write down, very clearly, three things in an induction proof:

• Your base case
• Your inductive hypothesis (the case you assume holds)
• What you need to prove in your induction step (the $n+1$ case if the hypothesis is the $n$ case)

Another good idea for induction is always remember that this "induction hypothesis" is key to the whole mess - it basically means "the previous case implies the next, which with the base case lets us prove infinitely many cases." In other words, you need to do whatever you can to try to make your inductive hypothesis applicable - in a proof like this, you want to manipulate your $n+1$ case into revealing the $n$ case. And then since you assume the $n$ case holds, you can substitute values as necessary, and use that to try and prove the $n+1$ case.

You made some errors in your $n+1$ equation as well which lent itself to problems. Usually if you assume the $n$ case holds you just replace every $n$ with $n+1$ in the inductive step when you want to see what you need to show.

That re-emphasizes the point of writing down the three things clearly.

---

Solution:

Let's assume the base case as you give in the OP is valid. If we make the inductive hypothesis that

$$\sum_{k=1}^n (k+1)2^k = n2^{n+1}$$

then we want to show in our induction step that

$$\sum_{k=1}^{n+1} (k+1)2^k = (n+1)2^{n+1+1} = (n+1)2^{n+2}$$

(Just replace all the $n$'s with $n+1$ here!) We note: we can split up the sum into the $1,2,...,n$ sum and basically "drag out" the $n+1$ term by itself:

$$\sum_{k=1}^{n+1} (k+1)2^k = (n+1+1)2^{n+1} + \sum_{k=1}^{n} (k+1)2^k = (n+2)2^{n+1} + \sum_{k=1}^{n} (k+1)2^k$$

Invoking our inductive hypothesis and doing some factoring, we obtain

$$\begin{align} (n+2)2^{n+1} + \sum_{k=1}^{n} (k+1)2^k &= (n+2)2^{n+1}+n2^{n+1}\\ &=2^{n+1}(2n+2) \\ &=2^{n+1}\cdot 2 (n+1)\\ &= 2^{n+2}(n+1) \end{align}$$

completing the proof.

Answer 2

$$\begin{align} \sum\limits_{k=1}^{n+1} (k+1)2^k & = \sum\limits_{k=1}^{n} (k+1)2^k + (n+2) 2^{n+1}. \\ & = n2^{n+1} + (n+2)2^{n+1}. \\ & = (2n+2)2^{n+1}. \\ & = (n+1)2^{n+2}. \end{align}$$

Proving the result for $n+1.$