Prove:
![1+2\left(\frac12\right)+3\left(\frac12\right)^{2}+...+n\left(\frac12\right)^{n-1}=4-\dfrac{n+2}{2^{n-1}}](https://tex.z-dn.net/?f=1%2B2%5Cleft%28%5Cfrac12%5Cright%29%2B3%5Cleft%28%5Cfrac12%5Cright%29%5E%7B2%7D%2B...%2Bn%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bn-1%7D%3D4-%5Cdfrac%7Bn%2B2%7D%7B2%5E%7Bn-1%7D%7D)
____________________________________________
Base Step: For n=1:
![n\left(\frac12\right)^{n-1}=1\left(\frac12\right)^{0}=1](https://tex.z-dn.net/?f=n%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bn-1%7D%3D1%5Cleft%28%5Cfrac12%5Cright%29%5E%7B0%7D%3D1)
and
![4-\dfrac{n+2}{2^{n-1}}=4-3=1](https://tex.z-dn.net/?f=4-%5Cdfrac%7Bn%2B2%7D%7B2%5E%7Bn-1%7D%7D%3D4-3%3D1)
--------------------------------------------------------------------------
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}}](https://tex.z-dn.net/?f=1%2B2%5Cleft%28%5Cfrac12%5Cright%29%2B3%5Cleft%28%5Cfrac12%5Cright%29%5E%7B2%7D%2B...%2Bk%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk-1%7D%3D4-%5Cdfrac%7Bk%2B2%7D%7B2%5E%7Bk-1%7D%7D)
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}](https://tex.z-dn.net/?f=1%2B2%5Cleft%28%5Cfrac12%5Cright%29%2B3%5Cleft%28%5Cfrac12%5Cright%29%5E%7B2%7D%2B...%2Bk%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk-1%7D%2B%28k%2B1%29%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk%7D)
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}](https://tex.z-dn.net/?f=%3D4-%5Cdfrac%7Bk%2B2%7D%7B2%5E%7Bk-1%7D%7D%2B%28k%2B1%29%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk%7D)
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}}](https://tex.z-dn.net/?f=1%2B2%5Cleft%28%5Cfrac12%5Cright%29%2B...%2Bk%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk-1%7D%2B%28k%2B1%29%5Cleft%28%5Cfrac12%5Cright%29%5E%7Bk%7D%3D4-%5Cdfrac%7B%28k%2B1%29%2B2%7D%7B2%5E%7B%28k%2B1%29-1%7D%7D)
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}}](https://tex.z-dn.net/?f=%3D4-%5Cdfrac%7Bk%2B2%7D%7B2%5E%7Bk-1%7D%7D%2B%5Cdfrac%7B%28k%2B1%29%7D%7B2%5E%7Bk%7D%7D)
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}}](https://tex.z-dn.net/?f=%3D4%2B%5Cdfrac%7B-2%28k%2B2%29%7D%7B2%5E%7Bk%7D%7D%2B%5Cdfrac%7B%28k%2B1%29%7D%7B2%5E%7Bk%7D%7D)
Distribute the -2 and combine the fractions together,
![=4+\dfrac{-2k-4+(k+1)}{2^{k}}](https://tex.z-dn.net/?f=%3D4%2B%5Cdfrac%7B-2k-4%2B%28k%2B1%29%7D%7B2%5E%7Bk%7D%7D)
Combine like-terms,
![=4+\dfrac{-k-3}{2^{k}}](https://tex.z-dn.net/?f=%3D4%2B%5Cdfrac%7B-k-3%7D%7B2%5E%7Bk%7D%7D)
pull the negative back out,
![=4-\dfrac{k+3}{2^{k}}](https://tex.z-dn.net/?f=%3D4-%5Cdfrac%7Bk%2B3%7D%7B2%5E%7Bk%7D%7D)
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,