Prove:
[tex]1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+n\left(\frac12\right)^{n-1}=4-\dfrac{n+2}{2^{n-1}}[/tex]
____________________________________________
Base Step: For n=1:
[tex]n\left(\frac12\right)^{n-1}=1\left(\frac12\right)^{0}=1[/tex]
and
[tex]4-\dfrac{n+2}{2^{n-1}}=4-3=1[/tex]
--------------------------------------------------------------------------
Induction Hypothesis: Assume true for n=k. Meaning:
[tex]1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+k\left(\frac12\right)^{k-1}=4-\dfrac{k+2}{2^{k-1}}[/tex]
assumed to be true.
--------------------------------------------------------------------------
Induction Step: For n=k+1:
[tex]1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+k\left(\frac12\right)^{k-1}+(k+1)\left(\frac12\right)^{k}[/tex]
by our Induction Hypothesis, we can replace every term in this summation (except the last term) with the right hand side of our assumption.
[tex]=4-\dfrac{k+2}{2^{k-1}}+(k+1)\left(\frac12\right)^{k}[/tex]
From here, think about what you are trying to end up with.
For n=k+1, we WANT the formula to look like this:
[tex]1+2\left(\frac12\right)+...+k\left(\frac12\right)^{k-1}+(k+1)\left(\frac12\right)^{k}=4-\dfrac{(k+1)+2}{2^{(k+1)-1}}[/tex]
That thing on the right hand side is what we're trying to end up with. So we need to do some clever Algebra.
Combine the (k+1) and 1/2, put the 2 in the bottom,
[tex]=4-\dfrac{k+2}{2^{k-1}}+\dfrac{(k+1)}{2^{k}}[/tex]
We want to end up with a 2^k as our final denominator, so our middle term is missing a power of 2. Let's multiply top and bottom by 2,
[tex]=4+\dfrac{-2(k+2)}{2^{k}}+\dfrac{(k+1)}{2^{k}}[/tex]
Distribute the -2 and combine the fractions together,
[tex]=4+\dfrac{-2k-4+(k+1)}{2^{k}}[/tex]
Combine like-terms,
[tex]=4+\dfrac{-k-3}{2^{k}}[/tex]
pull the negative back out,
[tex]=4-\dfrac{k+3}{2^{k}}[/tex]
And ta-da! We've done it!
We can break apart the +3 into +1 and +2,
and the +0 in the bottom can be written as -1 and +1,
[tex]=4-\dfrac{(k+1)+2}{2^{(k-1)+1}}[/tex]
