# Prove by induction that $\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} +2$. Help finding my mistake

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

Basis: let $p(n)$ be the predicate.

Let $n=1$ this gives $(1-1) \cdot 2^1+1+2 = 2$ and $1 \cdot 2^1 = 2$ so its true for $p(1)$

Induction: assume $n=k$ thus $$\sum_{i=1}^{k} i \cdot 2^i = (k-1) \cdot 2^{k+1} +2$$

when $n=k+1$:

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

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

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

$$=\frac{2^{k+1}k-2^{k+1}+2 \cdot 2^{k+1}(k+1)-2 \cdot 2^{k+1} +4}{2}$$

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

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

I've been messing around with the arithmetic part of this for a while now and it's getting frustrating, I'm thinking that I've possibly made a mistake at the beginning of the induction step and that's why I cant get this to work, or maybe I'm just missing something in the algebra, either way can someone please help.

The following is strange:

when $$n=k+1$$:

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

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

• @kris if you see what siong did... Recall $\sum_{i=1}^{k+1} i \cdot 2^{i}=1 \cdot 2^1 +2 \cdot 2^2+ 3 \cdot 2^3+ \cdots + k\cdot 2^k+(k+1) \cdot 2^{k+1}$ The sum of those first k terms is given. Commented Nov 3, 2017 at 4:49
• @randomgirl thanks for pointing that out
– kr1s
Commented Nov 3, 2017 at 6:15

Assuming $P(n)$ is true, we have \begin{align*} \sum_{i=1}^{n+1} i \cdot 2^i &= \sum_{i=1}^n i\cdot2^i + (n+1)\cdot2^{n+1} \\\\ &= (n-1)\cdot2^{n+1}+ 2 +(n+1)\cdot2^{n+1} \\\\ &= 2^{n+1}\cdot((n-1)+(n+1))+2 \\\\ &=2^{n+1}\cdot(2n)+2 \\\\ &=n\cdot2^{n+2}+2 \\\\ &=((n+1)-1)\cdot2^{((n+1)+1)}+2 \end{align*} as desired.

This might not be what you're looking for, but I just saw an induction proof the other day in class that was eerily similar to yours:

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

This one shakes out just fine. In yours, I think I see a mistake in the third line of your inductive step. You should simplify that $((k+1)-1)$ to $k$ instead of distributing the $2^{k+2}$. Then you can pull out a $2^{k+1}$ and it should be fine. Tell me if you need follow up.