# Thread: proof by induction with sigma

1. ## proof by induction with sigma

$\sum_{i=1}^{n+1}i\cdot2^i=2^{n+2}+2$ for all $n\geq 0$.

2. Hello gohangoten1
Originally Posted by gohangoten1
$\sum_{i=1}^{n+1}i\cdot2^i=2^{n+2}+2$ for all $n\geq 0$.
This is incorrect. $n = 2$ gives

$\sum_{i=1}^{3}i\cdot2^i=2^{4}+2$

The LHS is $1.2 + 2.4 + 3.8 = 34$

RHS $= 16+2=18$

3. I think the formula is $\sum^{n}_{k=0} k2^{k} = 2^{n+1}(n-1)+2$

4. Hello everyone

Thanks to
Renji Rodrigo for this:
Originally Posted by Renji Rodrigo
I think the formula is $\sum^{n}_{k=0} k2^{k} = 2^{n+1}(n-1)+2$
Adapting this formula to look more like the original, we get

$\sum^{n+1}_{i=1} i\cdot2^{i} = 2^{n+2}n+2$

So let $P(n)$ be the propositional function $S_n=\sum^{n+1}_{i=1} i\cdot2^{i} = 2^{n+2}n+2$

$P(1)$ is $S_1=\sum^{2}_{i=1} i\cdot2^{i} = 2^{3}\cdot1+2$

i.e. $S_1=1\cdot2 + 2\cdot2^2 = 10 = 2^{3}\cdot1+2$

So $P(1)$ is true.

Now $P(n) \Rightarrow S_{n+1} = S_n+(n+2)\cdot2^{n+2}$

$=2^{n+2}n+2+(n+2)\cdot2^{n+2}$

$=2^{n+2}(n+n+2)+2$

$=2^{n+2}(2n+2)+2$

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

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

i.e. $P(n) \Rightarrow P(n+1)$

So $P(n)$ is true for all $n \ge 1$