0

I am stuck on a question regarding induction. I know that we are supposed to solve it using 3 steps: the base step, the n= p step and n = p+1.

The question is prove that $$\displaystyle\sum_{i=1}^n\dfrac{i}{2^i}= 2- \dfrac{n+2}{2^n}$$

For $n = 1$ both sides will be $\dfrac{1}{2}$.

It is on the step $n+1$ that I am stuck.

I have calculated LHS to:

$$2-\dfrac{n+2}{2^n} + \dfrac{n+1}{2^{n+1}}$$

On the RHS for $n+1$ I have:

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

I would be thankful for any ideas on how to continue. My guess has to do with finding common factors which could be: $2$, $n+1$ or $2^{n+1}$.

Let me know if anything needs to be clarified.

addde
  • 449
  • Can you simplify $-\dfrac{n+2}{2^{n}}+\dfrac{n+1}{2^{n+1}}$ ? – Henry Jun 27 '15 at 09:31
  • 1
    Just a bit of clarification. Induction proofs do not involve three steps, but two: first you need to prove the base case, and then you need to prove that if the statement holds for some number $n$, then it also holds for $n+1$. It seems that you are doing this, but it is not what you stated in the introduction. – A.P. Jun 27 '15 at 09:41

3 Answers3

1

For the Induction Step,

$2-\dfrac{n+2}{2^n}+\dfrac{n+1}{2^{n+1}}=2-\dfrac{1}{2^n}\left(n+2-\dfrac{n+1}{2}\right)=2-\dfrac{1}{2^n}\left(\dfrac{2n+4 -n-1}{2}\right)=2-\dfrac{n+3}{2^{n+1}}$

  • Thanks for the quick replies really nice of you. but i still don't understand. How do you get Left-hand side :2−n+22n+n+12n+1=2−2(n+2)2n+1+n+12n+1

    and

    For the Induction Step, 2−n+22n+n+12n+1=2−12n(n+2−n+12) ?

     – addde Jun 27 '15 at 09:45
  • The problem was to show that $\displaystyle\sum_{i=1}^N\dfrac{i}{2^i}=2-\dfrac{N+2}{2^N}$. You have verified the base case (i.e., you have checked that the equality holds for $N=0$) and so you assume that it holds for $N=n$. In other words you have, $\displaystyle\sum_{i=1}^n\dfrac{i}{2^i}=2-\dfrac{n+2}{2^n}$. So to prove the case for $n+1$ we add $\dfrac{n+1}{2^{n+1}}$ to both sides which gives $\displaystyle\sum_{i=1}^{n+1}\dfrac{i}{2^i}=2-\dfrac{n+2}{2^n}+\dfrac{n+1}{2^{n+1}}$. In my answer have just simplified the R. H. S. part. –  Jun 27 '15 at 12:46
1

You forgor some parentheses around the exponents:

Left-hand side: $\quad 2-\dfrac{n+2}{2^n}+\dfrac{n+1}{2^{n+1}}=2-\dfrac{2(n+2)}{2^{n+1}}+\dfrac{n+1}{2^{n+1}}=2-\dfrac{n+3}{2^{n+1}}.$

Right-hand side: $\quad 2-\dfrac{(n+1)+2}{2^{n+1}}$.

Bernard
  • 175,478
0

you must show that $$2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{n+3}{2^{n+1}}$$

Dr. Sonnhard Graubner
  • 95,283