sequences and series - Proving $sumlimits_{i=0}^n i 2^{i-1} = (n+1) 2^n - 1$ by induction

I'm trying to apply an induction proof to show that $((n+1) 2^n - 1$ is the sum of $(i 2^{i-1})$ from $0$ to $n$.

• the base case: L.H.S = R.H.S


• we assume that $(k+1) 2^k - 1$ is true.


• we need to prove that $(k+2) 2^{k+1} - 1$

My try to prove 3 is as follows:

$(k+2) 2^{k+1} - 1$

$(k+2) (2^k * 2) - 1$ , from 2: $2^k = 1/(k+1)$

$(k+2) (2 / (k+1)) - 1$

$(k+1) 2 - 1$

My question is, how could I get to $2^k$ from the last line to prove this formula is right?

Answer

You have a typo in your statement. You want to show $$\sum_{i=0}^n i 2^{i-1} = n 2^n - 2^n + 1$$

Base case $n = 0$:

$$\sum_{i=0}^0 i 2^{i-1} = 0 = 0 - 1 + 1$$

Assume that $$\sum_{i=0}^n i 2^{i-1} = n 2^n - 2^n + 1$$

Then make an induction step from $n$ to $n+1$. This means you want to show that given your assumption you can show

$$\sum_{i=0}^{n+1} i 2^{i-1} = (n+1) 2^{n+1} - 2^{n+1} + 1$$

Do this as follows:

$$\sum_{i=0}^{n+1} i 2^{i-1} = \sum_{i=0}^{n} i 2^{i-1} + (n+1)2^n = n 2^n - 2^n + 1 + (n+1)2^n = n 2^{n+1} + 1 = (n+1)2^{n+1} - 2^{n+1} + 1$$

Which is what you wanted to show. Hope this helps.