Question

Prove by induction:

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

Answer 1

ah a repeat. did you start with proving true for n = 1?

Answer 2

then you assume true for n, show true for n + 1
so
\[\sum_{i=1}^{n+1}\frac{i}{2^i}=\sum_{i=1}^n\frac{i}{2^i}+\frac{n+1}{2^{n+1}}\]

Answer 3

by induction the first term is
\[2-\frac{n+2}{2^n}\] so you have
\[\sum_{i=1}^{n+1}\frac{i}{2^i}=\sum_{i=1}^n\frac{i}{2^i}+\frac{n+1}{2^{n+1}}=2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}\]

Answer 4

now compute
\[\frac{n+1}{2^{n+1}}-\frac{n+2}{2^n}\] and you will get exactly what you want

Answer 5

that's the part i'm having difficulty with

Answer 6

namely
\[
\frac{n+1}{2^{n+1}}-\frac{n+2}{2^n}=\frac{n+1-2(n+2)}{2^{n+1}}\]

Answer 7

i multiplied top and bottom of second fraction by 2

Answer 8

multiply out and get
\[\frac{n+1-2n-4}{2^{n+1}}=\frac{-n-3}{2^{n+1}}=-\frac{n+3}{2^{n+1}}\]

Answer 9

which is exactly what you needed to get to finish the induction