Now that we have our base cases, our next step is to fix our induction hypothesis. Recall that our statement we supposed in the previous exercise is the following:
We noted in the previous exercise that we needed to modify our induction hypothesis so that the hypothesis is true at
k and at
k-1. We will fix this problem by supposing, for all integers between our largest base case (we saw from the last exercise that this is
n = 3) and some integer
Now we have an induction hypothesis that is true at
k and at
k-1. (Note that we started our assumption from the largest base case because we have already proved the conjecture for each base case below our largest one, and so assuming their truth is unnecessary.)
Our task will be to prove that:
We will need to be creative with our left-hand expression. We know by the induction hypothesis that
(k+1) + k + (k-1) = 3k. Why not force this into our left-hand side expression? We know that:
We can now use or induction hypothesis to substitute
3k in for
(k+1) + k + (k-1) to obtain:
Finally, factor out a 3 from the right-hand side to obtain:
Since we obtained our desired result, our proof is now complete.
That was a lot to take in. Hopefully seeing this proof written out in Python might explain things more clearly! First, create a variable called
s and set it equal to
k + 1 + k + k - 1. Print
s as well.
Now use the
== operator to print whether or not
3 * k.