Hi any Ideas where I went wrong (induction)?

**Henryt999** · February 23rd 2010, 09:43 AM

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?

**tonio** · February 23rd 2010, 10:02 AM

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

**Henryt999** · February 23rd 2010, 11:12 AM

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 =)

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

LinkBack

Thread Tools

Display

Hi any Ideas where I went wrong (induction)?

Similar Math Help Forum Discussions

Any ideas here please? :-)

Where did I go wrong on this proof? (Mathematical Induction)

Any ideas...

What's wrong with this proof (complete induction)

i need some ideas

Search Tags