0

So the question in my textbook is:

Show by induction that $\sum\limits_{k=1}^n \frac{k}{2^k} = 2 - \frac{n+2}{2^n}$ for all $n$ $\in Z_+$.

My attempt at a solution:

First of all $Z_+ = 1, 2, 3, 4, 5, 6, 7, 8 ...$

So I start to make sure that the base case is right... For that I choose $k = 1$

This gives us:

$$\sum\limits_{k=1}^1 \frac{1}{2^1} = 2 - \frac{1+2}{2^1} \rightarrow \frac{1}{2} = 2 - \frac{3}{2}$$

The base case does work.

The next step is to take make the inductive assumption that it is true for $n = k$. This gives us:

$$\frac{1}{2^1} + \frac{2}{2^2} + ... + \frac{k}{2^k} = 2 - \frac{k+2}{2^k}$$

The next step is to show that $n = k + 1$ holds:

$$\frac{1}{2^1} + \frac{2}{2^2} + ... + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} = 2 - \frac{k+1+2}{2^{k+1}}$$

By using the induction hypothesis we have:

$$\frac{1}{2^1} + \frac{2}{2^2} + ... + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} = 2 - \frac{k+2}{2^k} + \frac{k+1}{2^{k+1}}$$

The $RHS$ can be written as: $$2 - \frac{k+2}{2^{k}} + \frac{k+1}{2^{k+1}}$$

How do I move on from here and show that:

$$2 - \frac{k+2}{2^{k}} + \frac{k+1}{2^{k+1}} = 2 - \frac{k+1+2}{2^{k+1}}$$

Thank you!

Lukas Arvidsson
  • 2,376

3 Answers3

1

I think that what they ask you is to show that

$\sum\limits_{k=1}^n \frac{k}{2^k}- (2 - \frac{n+2}{2^n}) = 0$

Claude Leibovici
  • 260,315
1

By induction, it is quite easy : just add the $(n+1)$ term if the lhs and in the rhs independently (to this one, substract the value of the sum for $n$). You will see, after very simple simplifications, that these two terms are equal.

Now, how to establish this formula ? Look at the term in the summation as $k x^k$. This is $x$ times the derivative of $x^k$; that is to say that you have to sum from $k=1$ to $k=n$ terms which are in geometric progression; you know the formula for the sum. So, compute the derivative of the sum, multiple the result by $x$ and .... plug $x=1/2$. Then, manipulate a little and you get it.

Claude Leibovici
  • 260,315
  • Hi @ClaudeLeibovici I have trouble with showing that the these two terms are equal: $2 - \frac{k+2}{2^{k}} + \frac{k+1}{2^{k+1}} = 2 - \frac{k+1+2}{2^{k+1}}$ (please look at updated question if you want to know how I derived these terms) Have I done something wrong? Thank you VERY much for your help! Much appreciated! – Lukas Arvidsson Jan 22 '14 at 09:55
  • @LukasArvidsson.First replace $k$ by $n$. But you made a mistake since the difference of the two consecutive rhs's is : 2 - (n+3)/2^(n+1) - 2 + (n+2)/2^n = 2 (n+2) / 2^(n+1) - (n+3) / 2^(n+1) = (n + 1) / 2^(n+1). QED. By the way, if you like my answer, you can accept it. – Claude Leibovici Jan 22 '14 at 10:20
  • Thank you Claude for your help! – Lukas Arvidsson Jan 22 '14 at 10:22
1

It works in this way. Consider this (I will skip some passages to make the answer shorter, but they should be easy enough). $$ S(x)=\sum_{k=1}^nkx^k $$ we are interested in $S(1/2)$. Now is easy to see that $$ kx^k=x\frac{d}{dx}x^k $$ so we can write $$ S(x)=\sum_{k=1}^n x\frac{d}{dx}x^k=x \frac{d}{dx}\sum_{k=1}^n x^k $$ but $$ \sum_{k=1}^n x^k = \frac{x(x^n-1)}{x-1} $$ so taking the derivative of this sum we get $$ S(x)=x\frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2} $$ Now we can calculate $S(1/2)$ and we get $$ S(1/2) = \frac{1}{2}\left( 2\frac{n}{2^n} - 4\frac{n+1}{2^n} +4\right) $$ and if you simplify this you get your result. I hope you can complete the missing passage. That is only algebra.

Umberto
  • 1,263
  • 8
  • 16