Prove:
\(1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+n\left(\frac12\right)^{n-1}=4-\dfrac{n+2}{2^{n-1}}\)
____________________________________________
Base Step: For n=1:
\(n\left(\frac12\right)^{n-1}=1\left(\frac12\right)^{0}=1\)
and
\(4-\dfrac{n+2}{2^{n-1}}=4-3=1\)
--------------------------------------------------------------------------
Induction Hypothesis: Assume true for n=k. Meaning:
\(1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+k\left(\frac12\right)^{k-1}=4-\dfrac{k+2}{2^{k-1}}\)
assumed to be true.
--------------------------------------------------------------------------
Induction Step: For n=k+1:
\(1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+k\left(\frac12\right)^{k-1}+(k+1)\left(\frac12\right)^{k}\)
by our Induction Hypothesis, we can replace every term in this summation (except the last term) with the right hand side of our assumption.
\(=4-\dfrac{k+2}{2^{k-1}}+(k+1)\left(\frac12\right)^{k}\)
From here, think about what you are trying to end up with.
For n=k+1, we WANT the formula to look like this:
\(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}}\)
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,
\(=4-\dfrac{k+2}{2^{k-1}}+\dfrac{(k+1)}{2^{k}}\)
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,
\(=4+\dfrac{-2(k+2)}{2^{k}}+\dfrac{(k+1)}{2^{k}}\)
Distribute the -2 and combine the fractions together,
\(=4+\dfrac{-2k-4+(k+1)}{2^{k}}\)
Combine like-terms,
\(=4+\dfrac{-k-3}{2^{k}}\)
pull the negative back out,
\(=4-\dfrac{k+3}{2^{k}}\)
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,
\(=4-\dfrac{(k+1)+2}{2^{(k-1)+1}}\)
