Maths extension 1 students need to learn a proof technique called mathematical induction (MI), which may seem sort of abstract to them. They may remember all the three (or four if you separate the assumption for n=k from the proof for n=k+1) steps, and are able to solve the HSC questions, but may still find it hard to get.
Step 1. The induction basis (Ron & Dreyfus, 2004).
Prove that the statement is true for n=1 (or the initial value of n).
Step 2. The induction step.
Assume that the statement is true for n=k (where k is any legitimated value of n).
Prove that the statement is then true for n=k+1.
Step 3. Conclusion.
Here I listed several common questions that students may ask.
Q: Why do we still need Step 1 when we can show that “the statement is always true for n=k+1 when it’s true for n=k, for all integral k“?
To validate an MI proof, we shall compose both the induction basis and the induction step. The induction basis ensures that the statement is true for n=1. Together with the induction step, we can then come to the conclusion that the statement is also true for n=2 by substituting 1 for k, ditto for n=3 by substituting 2 for k, and by repeating this process infinite times, we can show it’s true for all integral n.
Here, to visually illustrate the role of each step in MI, we can use the domino model as an analogy. Trust me, it can be very helpful!
In step 2, the induction step, we shall prove that “If the statement is true for n=k, then it is always true for n=k+1“. In our analogous domino model, the scenario is “If the kth tile fails, it will always knock down the k+1th tile.” Well, in a practical way, it means we should space our domino tiles not too far from each other. “If the kth tile fails…” Well, we don’t know if the kth tile will fall down or not, all we know so far is that they are in a row, ready to go.
Now let’s have a look at step 1, the induction basis. Why do we need to prove the statement is true for n=1 if we have already proved the induction step? Here is the reason — we need to push the first domino tile down, or nothing is going to happen however your tiles have been arranged in order. But once the first tile is down, all the following tiles are to be knocked down effortlessly (at least no more effort at this stage). Similarly, only if we can show it is true for n=1, then given the induction step has been proved, it can be proved true for n=2, then for n=3, and so on and so forth.
Lastly, let me raise a counterexample. If we prove with step 2 alone, we probably can prove this: n=n+1. What a nonsense, right? Well, you may reach that conclusion if you believe step 2 is good enough.
Assume the statement is true for n=k, i.e., k=k+1
Hence show the statement is true for n=k+1, i.e., k+1=k+2
LHS=k+1=(k+1)+1=k+2=RHS, it’s true for n=k+1 too.
Therefore, the statement is true for all positive integral value of n.
Q: We say “assume it is true for n=k”, but wait a minute, what if it is not true?
What if the statement is true for n=1, but it becomes false in the middle of the sequence, say it is false for n=10?
Well, since we have proved the induction step and the induction basis, the statement is true for n=1, then it must be true for n=2, then for n=3, all the way to n=10. Once we have proved the two steps, there is no room for the statement to be false for any integral n! That’s why we call the first step the “induction basis”–it’s the basis for the validity of the following statements.
Q: Why call it “induction” when we use deductive reasoning to show step 1 and step 2?
Generally, “induction” or “inductive reasoning” means one examined several individual instances then generalize the findings to all the instances. For statements involving parameters like n for all integer, the results based on inductive reasoning cannot be reliable–even one has checked a million cases and found they are all true, the exemption may happen in the 1000001st case.
On the other hand, results reached through deductive reasoning are reliable. Almost all the theorem we have encountered in our maths textbooks are proved by deduction. Here in MI, we still need to use deductive reasoning to prove the two steps true.
But MI is an inductive strategy. And it is still reliable because there will be no unscrutinized cases if we prove the statement by MI.
In an MI proof, we first check the statement is true for n=1, then we can use step 2, which automatically do all the remaining checkings for us. Please be aware of the modifier — mathematical. The mathematical technique, this step 2, this induction step, has freed us from the repetitive examination and done all these for us.
Hope you will find this post useful.
Reference:
Ron, G & Dreyfus, T (2004), The Use of Models in Teaching Proof by Mathematical Induction. Proceedings of the 28th Conference of the International Group for the Psychology of Mathematics Education, Vol 4 pp 113-120.
Maths for us 