Thread: proof by induction with sigma

1. proof by induction with sigma

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

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

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

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

RHS $\displaystyle = 16+2=18$

3. I think the formula is$\displaystyle \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$\displaystyle \sum^{n}_{k=0} k2^{k} = 2^{n+1}(n-1)+2$
Adapting this formula to look more like the original, we get

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

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

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

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

So $\displaystyle P(1)$ is true.

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

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

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

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

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

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

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

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