Well done, we have completed the first induction example! Let’s try a different example. For any positive integer
n, the number
3n actually does have an interesting property:
You may think that the first step in proving this statement is to provide one base case. Unfortunately, that base case is not enough for our new example. Why? The big reason is this: our induction hypothesis currently assumes that our statement is true for some integer
k. Recall that our conjecture is:
This means that our induction hypothesis is this: for some positive integer
k which exceeds
If we were to prove this using induction on the left-hand side, then we would need our hypothesis to be true at
k-1 in order to use our induction hypothesis correctly. However, the current induction hypothesis states that the theorem is true at just
k; thus, a new method of proof needs to be used.
These next two exercises (including this one) will help to formally define strong induction, the approach we need in proving statements like these. The first step to strong induction is to identify the base cases we need. For this problem, since we have the terms
n-1 in our statement, we need three base cases to proceed.
Create a variable called
first and set it equal to your guess as to what the first base case should be in the code editor.
Create another variable called
second and set it equal to your guess as to what the second base case should be in the code editor.
Finally, create a new variable called
third and set it equal to your guess as to what the third base case should be in the code editor.