Question

Prove by induction:

n
∑(i/2^i) = 2 - (n+2)/2^n
i=1

Answer 1

we first prove it is true for n=1, so:\[\sum_{i=1}^1\frac{i}{2^i}=\frac{1}{2^1}=\frac{1}{2}\]and\[2-\frac{1+2}{2^1}=2-\frac{3}{2}=\frac{1}{2}\]therefore:\[\sum_{i=1}^1\frac{i}{2^i}=2-\frac{1+2}{2^1}\]which means we have proved it for n=1.

next we "assume" the formulae is true for some value of n, say n=k. so assume following is true:\[\sum_{i=1}^k\frac{i}{2^i}=2-\frac{k+2}{2^k}\]
we then test to see if it is also true for n=k+1:\[\sum_{i=1}^{k+1}\frac{i}{2^i}=\sum_{i=1}^k\frac{i}{2^i}+\frac{k+1}{2^{k+1}}\]\[=2-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}}\]\[=2-\frac{2(k+2)}{2^{k+1}}+\frac{k+1}{2^{k+1}}\]\[=2-\frac{2k+4}{2^{k+1}}+\frac{k+1}{2^{k+1}}\]\[=2-(\frac{2k+4}{2^{k+1}}-\frac{k+1}{2^{k+1}})\]\[=2-(\frac{k+3}{2^{k+1}})\]\[=2-\frac{(k+1)+2}{2^{k+1}}\]so we can see that if we assume the formulae is correct for n=k, then it is also correct for n=k+1.

So now, using induction, we have proved it true for all n>=1.