There are many techniques to prove various statements. The simplest ones are direct proof, where you show that if the first statement (P) is true then the second statement (Q) is also true; the proof by contrapositive, where you assume that the negation of the second statement (~Q) is true and show that this forces the negation of the first statement (~P) to be true as well. Mathematical induction is a technique used to prove that an all statements of an infinite list of statements (instead of just two like in the first two techniques mentioned) are all true.
To motivate the discussion, let’s first examine the kinds of statements that induction is used to prove.
Consider the following statement.
Conjecture. The sum of the first \(n\) odd natural numbers equals \(n^2\).
The following table illustrates what this conjecture says. Each row is headed by a natural number \(n\), followed by the sum of the first \(n\) odd
natural numbers, followed by \(n^2\).
Note that in the first five lines of the table, the sum of the first \(n\) odd numbers really does add up to \(n^2\). Notice also that these first five lines indicate that the \(n\)th odd natural number (the last number in each sum)
is \(2n-1\). (For instance, when \(n=2\), the second odd natural number is \(2 \cdot 2−1 =3\); when \(n=3\), the third odd natural number is \(2 \cdot 3−1 =5\), etc.)
The table raises a question. Does the sum \(1+3+5+7+\cdots+(2n−1)\) really always equal \(n^2\)? In other words, is the conjecture true?
Let’s rephrase this as follows. For each natural number \(n\) (i.e., for each
line of the table), we have a statement \(S_n\), as follows:
Our question is: Are all of these statements true?
Mathematical induction is designed to answer just this kind of question.
It is used when we have a set of statements \(S_1,S_2,S_3,\cdots ,S_n,\cdots \), and weneed to prove that they are all true. The method is really quite simple.
In this setup, the first step (1) is called the basis step. Because \(S1\) is usually a very simple statement, the basis step is often quite easy to do.
The second step (2) is called the inductive step. In the inductive step direct proof is most often used to prove \(S_k \Rightarrow S_{k+1}\), so this step is usually carried out by assuming \(S_k\) is true and showing this forces \(S_{k+1}\) to be true.
The assumption that \(S_k\) is true is called the inductive hypothesis.
Now let’s apply this technique to our original conjecture that the sum of the first \(n\) odd natural numbers equals \(n^2\). Our goal is to show that for each \(n \in \mathbf{N}\), the statement \(S_n : 1+3+5+7+\cdots+(2n−1) = n^2\) is true. Before getting started, observe that \(S_k\) is obtained from \(S_n\) by plugging \(k\) in for \(n\).
Thus \(S_k\) is the statement \(S_k : 1+3+5+7+\cdots+(2k −1)=k^2\). Also, we get \(S_{k+1}\) by plugging in \(k +1\) for \(n\), so that \(S_{k+1} : 1+3+5+7+\cdots+(2(k +1)−1) =(k +1)^2\).
More:
checksum: 38957cccdef0229b17dfce1dfb41c983f71f59d88a0e338d8718d21943258cae965609e9d16032c9fa87a0271e120d2c465784b7048fa0c9cd7dfecbe94e7680