Prove by induction $\sum_{i=1}^{n}i\cdot2^{i-1}=(n-1)\cdot2^n+1$

Question

The question is:

Prove by induction that $1\cdot2^0+2\cdot2^1+3\cdot2^2+\cdots+i\cdot2^{i-1}+\cdots+n\cdot2^{n-1}=(n-1)\cdot2^n+1$.

I am stuck and don't know how to advance. How can I prove by induction?

Answer 1

Your problem statement is missing a few key words.

What you're looking for is

Prove for all integers $n \geq 1$ that $$\sum_{i=1}^n i\cdot 2^{i-1} = (n-1)2^n+1.$$

First you verify a base case by showing that this statement is true for $n=1$.

Then, you assume that it holds for some $n=k$, and then show that this implies that it holds for $n=k+1$.

You assume

$$\sum_{i=1}^k i\cdot 2^{i-1} = (k-1)2^k+1.$$

Now you want to show that

$$\sum_{i=1}^{k+1} i\cdot 2^{i-1} = k2^{k+1}+1.$$

A good way to start from here is to break out the last term of the left-hand sum:

$$\sum_{i=1}^{k+1} i\cdot 2^{i-1} = \left(\sum_{i=1}^{k} i\cdot 2^{i-1}\right) + (k+1)2^k.$$

From here, you can use your assumption to substitute the sum in parentheses, and then rearrange the terms on the right-hand side to show what you want.

Can you take it from here?

Answer 2

Hint:

$$((n+1-1)2^{n+1}+1)-((n-1)2^n+1)=(2n-n+1)2^n=(n+1)2^n.$$

Answer 3

For the induction step use

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