# Thread: Hi any Ideas where I went wrong (induction)?

1. ## Hi any Ideas where I went wrong (induction)?

What is wrong with this solution?
Problem:
Prove that $\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{ n}{2^n} = 2-\frac{n+2}{2^n}$ for $n=1,2,3,...$

Solution:
Proof by induction
Let the LHS =
$
\sum_{k=1}^{n+1}(\frac{n}{2^n})= \sum_{k=1}^{n}(\frac{n}{2^n})+\sum_{n}^{n+1}(\frac {n}{2^n})
$

RHS is $2-\frac{n+2}{2^n}$

Is it valid for n=1?
LHS = $\frac{1}{2}$
RHS= $2-\frac{1+2}{2^1} = \frac{1}{2}$ True!
Now let LHS =
$
\sum_{k=n}^{n+1}(\frac{n}{2^n}) = \frac{n+1}{2^{n+1}}
$

Thats what we want our RHS to look like:
Now
Lets look att RHS.
Lets set (n+1) into the formula and subract n that should then equal the LHS hopefully:
$
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)
$

.
$
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)
$

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

.
$
\frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}
$

.
$
\frac{n+1}{2\times 2^{n}}
$

RHS = LHS and by induction this is true for all n $\in \textbf{R}$
Why is this not right?

2. Originally Posted by Henryt999
What is wrong with this solution?
Problem:
Prove that $\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{ n}{2^n} = 2-\frac{n+2}{2^n}$ for $n=1,2,3,...$

Solution:
Proof by induction
Let the LHS =
$
\sum_{k=1}^{n+1}(\frac{n}{2^n})= \sum_{k=1}^{n}(\frac{n}{2^n})+\sum_{n}^{n+1}(\frac {n}{2^n})
$

RHS is $2-\frac{n+2}{2^n}$

Here really begins your proof. The above stuff is only algebraic manipulations.

Is it valid for n=1?
LHS = $\frac{1}{2}$
RHS= $2-\frac{1+2}{2^1} = \frac{1}{2}$ True!
Now let LHS =
$
\sum_{k=n}^{n+1}(\frac{n}{2^n}) = \frac{n+1}{2^{n+1}}
$

Thats what we want our RHS to look like:
Now
Lets look att RHS.
Lets set (n+1) into the formula and subract n that should then equal the LHS hopefully:
$
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)
$

.
$
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)
$

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

.
$
\frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}
$

.
$
\frac{n+1}{2\times 2^{n}}
$

RHS = LHS and by induction this is true for all n $\in \textbf{R}$
Why is this not right?

I think it is right but you did it so messed up and unclear that, apparently, you succeeded to confuse, and perhaps even annoy, your instructor.

After proving the claim for n=1, you must say/write: let us assume the claim's true for n (this is also called "inductive hypothesis") and we shall prove for n+1, i.e. we must prove that

$\sum\limits_{k=1}^{n+1}\frac{k}{2^k}=2-\frac{n+3}{2^{n+1}}$ . We now take the LHS and develop it:

$\sum\limits_{k=1}^{n+1}\frac{k}{2^k}=\sum\limits_{ k=1}^n\frac{k}{2^k}+\frac{n+1}{2^{n+1}}$ $=_{\substack{Ind. Hyp.}}2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{1}{2^{n+1}}\left[2(n+2)-n-1\right]$ $=2-\frac{n+3}{2^{n+1}}$ and we're done since now we got the RHS...

Tonio

3. I think it is right but you did it so messed up and unclear that, apparently, you succeeded to confuse, and perhaps even annoy, your instructor.

IŽll give you a big thanks for making me laugh for 2 minutes =)