0

Prove by induction that $$\sum_{i=1}^n \frac{i}{2^i}=2-\frac{n+2}{2^n}.$$

this is a question that must be proved by induction. For the base case I used $n=1$ and simplified to $1/2$ and now for the inductive step $$p(k)\to p(k+1)=2-\frac{(k+1)+2}{2^{k+1}}.$$ I am not sure if this is right step or if I should simply be $p(k)+(k+1)$.

Arctic Char
  • 16,007
  • A basic introduction here – Arctic Char Oct 06 '20 at 20:50
  • You need to use $\sum_{i=1}^{k+1} i/2^i =\sum_{i=1}^{k} i/2^i + (k+1)/2^{k+1}$. – Arctic Char Oct 06 '20 at 20:53
  • is that implying to sub in(k+1)? @ArcticChar –  Oct 06 '20 at 20:56
  • A strategy for all induction proofs about sums. To prove $\sum_{k=1}^n a_k = f(n)$, then for the induction step can ALWAYS but $\sum_{k=1}^{n+1} a_k = a_{n+1} + \sum_{k=1}^n a_n = a_{n+1} + f(n)\underbrace{=}{to\ prove}f(n+1)$. So to do an induction step about sums it is ALWAYS sufficient to prove $ a{n+1} + f(n)=f(n+1) $. The will always work (if it can be done) and that should always be your first strategy. – fleablood Oct 06 '20 at 21:06
  • @fleablood Thanks I think I get it now, instead of adding k+1 I am supposed to add the previous term to the next term since it is the sigma notation –  Oct 06 '20 at 21:09
  • So if you can prove $\frac {n+1}{2^{n+1}} + (2 -\frac {n+2}{2^n})=2 - \frac {(n+1)+2}{2^{n+1}}$ you are done. That will prove your induction step. – fleablood Oct 06 '20 at 21:09

1 Answers1

1

Suppose $\sum_{i=1}^n \frac{i}{2^i}=2-\frac{n+2}{2^n}$ for some $n$.

Induction step: $\sum\limits_{i=1}^{\color{blue}{n+1}} \frac{i}{2^i}=\color{blue}{\frac {n+1}{2^{n+1}}} + (\sum\limits_{i=1}^{\color{red}{n}} \frac{i}{2^i})=$

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

$.........=$

$2 - \frac {(n+1)+2}{2^{n+1}}$

Can you fill in the missing step?

fleablood
  • 124,253