Hi any Ideas where I went wrong (induction)?

• Feb 23rd 2010, 09:43 AM
Henryt999
Hi any Ideas where I went wrong (induction)?
What is wrong with this solution?(Headbang)
Problem:
Prove that $\displaystyle \frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{ n}{2^n} = 2-\frac{n+2}{2^n}$ for $\displaystyle n=1,2,3,...$

Solution:
Proof by induction
Let the LHS =
$\displaystyle \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 $\displaystyle 2-\frac{n+2}{2^n}$

Is it valid for n=1?
LHS = $\displaystyle \frac{1}{2}$
RHS= $\displaystyle 2-\frac{1+2}{2^1} = \frac{1}{2}$ True!
Now let LHS =
$\displaystyle \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:
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)$
.
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)$
.
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}- 2+\frac{2(n+2)}{2\times 2^{n}}$
.
$\displaystyle \frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}$
.
$\displaystyle \frac{n+1}{2\times 2^{n}}$
RHS = LHS and by induction this is true for all n $\displaystyle \in \textbf{R}$
Why is this not right?
• Feb 23rd 2010, 10:02 AM
tonio
Quote:

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

Solution:
Proof by induction
Let the LHS =
$\displaystyle \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 $\displaystyle 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 = $\displaystyle \frac{1}{2}$
RHS= $\displaystyle 2-\frac{1+2}{2^1} = \frac{1}{2}$ True!
Now let LHS =
$\displaystyle \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:
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)$
.
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)$
.
$\displaystyle 2-\frac{(n+1)+2}{2^{n+1}}- 2+\frac{2(n+2)}{2\times 2^{n}}$
.
$\displaystyle \frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}$
.
$\displaystyle \frac{n+1}{2\times 2^{n}}$
RHS = LHS and by induction this is true for all n $\displaystyle \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

$\displaystyle \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:

$\displaystyle \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}}$ $\displaystyle =_{\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]$ $\displaystyle =2-\frac{n+3}{2^{n+1}}$ and we're done since now we got the RHS...(Cool)

Tonio
• Feb 23rd 2010, 11:12 AM
Henryt999
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 =)(Rock)