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