2.4 Proof by Induction
We shall see a number of other examples of using the axioms to prove basic results in number theory later in the course. For now, we conclude by introducing a final method of proof, that many of you will have seen before.
This method is referred to as Proof by Induction and concerns proving statements of the form \[ \forall n\in \mathbb N,\; P(n). \] The method of proof uses the Principle of Mathematical Induction, which can be expressed as
If \(P(1)\land \left[\forall n\geq 1,\; P(n)\implies P(n+1)\right]\) then \(P(n)\) is true for all \(n\geq 1\).
So to prove a statement of the form \[ \forall n\geq1,\; P(n). \] we prove
- \(P(1)\) is true
- \(\forall n\geq1,\ P(n)\implies P(n+1)\).
The first step is often referred to as the base step or anchoring step, while the second step is referred to as the inductive step. To prove the inductive step we take \(P(n)\) as premise and prove \(P(n+1)\). The premise \(P(n)\) is referred to as the induction hypothesis.
We shall prove this theorem shortly but it is helpful to look at a simple example first.
The principle relies on the fact that if a statement about the positive integers is false for some positive integers, then there is a first one at which it fails to be true. If we take \(n\) to be the last number before it fails then \(P(n)\) is true but \(P(n+1)\) is false, so if we want to prove that a statement is true for all positive integers we just have to show that when \(P(n)\) is true then \(P(n+1)\) is also true.
The equation \(\displaystyle\sum\limits_{i=1}^n 2i = n\cdot (n+1)\) seems to be true for all values of \(n\). How would we prove this?
\(P(1)\), the statement that \(2.1=1.2\), is true by (Comm).
Now if \(\displaystyle\sum\limits_{i=1}^n 2i = n\cdot (n+1)\) fails for some values, let \(n\) be one less than the first value where it fails. So \(P(n)\) is true but \(P(n+1)\) is false. Therefore \(\displaystyle\sum\limits_{i=1}^n 2i = n\cdot (n+1)\) and so \[\sum\limits_{i=1}^{n+1} 2i = 2(n+1) + \sum\limits_{i=1}^n 2i = 2(n+1) + n\cdot (n+1) = (n+1)(n+2)\] where the first inequality follows from the definition of \(\sum\), the second as \(P(n)\) is true, and the third is (Dist).
But the equation \(\displaystyle\sum\limits_{i=1}^{n+1} 2i = (n+1)(n+2)\) tells us that \(P(n+1)\) is true! This is a contradiction so there cannot be a first place at which the statement becomes false, and it must be true for all values of \(n\).
Here is a proof of Theorem 2.8.
Proof. We will use proof by contradiction so our premise is \[P(1)\land \left[\forall n\geq 1,\; P(n)\implies P(n+1)\right]\] and we suppose (for a contradiction) that \[\exists k\geq 1,\ P(k)\text{ is false}.\] (We’ve used a different variable to avoid confusion with \(n\) in the previous statement.)
As in 2.9 the idea is to consider \(n\) to be one less than the first value where \(P(k)\) is false.
By assumption \(P(k)\) fails for some \(k\) so \[S=\{k\in\mathbb Z: k\geq 1 \text{ and } P(k)\text{ is false}\}\] is a non-empty subset of \(\mathbb N\). By (WO) this set has a least element \(m\).
As \(m\in S\) we know \(1\leq m\). We consider cases:
If \(m=1\) then \(P(1)\) is false, contradicting the premise.
If \(m\neq 1\) then \(1<m\) so \(1+1\leq m\) by Corollary 2.7.
Applying (Sh) and Lemma 2.4 we get \(1\leq m-1\).
Let \(n=m-1\). Then \(n<n+1\) (by (Sh) as \(0<1\)).
But \(n+1=m\) which is the least element of the set \(S\).
So \(n\geq 1\) but \(n\notin S\) meaning that \(P(n)\) is true.
But \(P(n+1)=P(m)\) which is false as \(m\in S\).
So we have \(P(n)\land\lnot P(n+1)\equiv \lnot (P(n)\implies P(n+1))\).
We have shown \(\exists n\in \mathbb N,\; \lnot(P(n)\implies P(n+1))\), but this contradicts the premise as \[\exists n\geq 1,\; \lnot(P(n)\implies P(n+1)) \equiv \lnot\left[\forall n\geq 1,\; P(n)\implies P(n+1)\right]\] Since both cases (\(m=1\) and \(m\neq 1\)) lead to contradictions the assumption (that \(P(k)\) fails for some \(k\)) is false, meaning \[\forall k\in\mathbb N,\; P(k)\text{ is true }.\]
Notice also that there is nothing special about the starting value of 1. If we wish to prove the statement \(\forall n\ge m\ P(n)\) we do so by proving
- \(P(m)\) is true
- \(\forall n\ge m\ P(n)\implies P(n+1)\). Here \(m\) could be positive, zero, or even negative.
Show that for all \(n\ge 1\) \[ n!\le n^n \]
Solution. The base step is to prove the statement \[ P(1): 1!\le 1^1 \] This is quite obvious, as both sides are equal to 1.
The inductive step is to prove the statement \[ \forall n\ge 1\ P(n)\implies P(n+1), \] or in other words \[ \forall n\ge 1\ n!\le n^n\implies (n+1)!\le (n+1)^{n+1}. \]
The best strategy with this kind of example is to take one side of the inequality in the statement \(P(n+1)\) and rewrite it using the corresponding expression from the statement \(P(n)\).
Assume \(n!\leq n^n\) (induction hypothesis) \[ \begin{array}{rcl} (n+1)!&=&(n+1)n!\qquad\text{by definition of $n!$}\\ &\le&(n+1)n^n\qquad\text{by } \textit{(Sc)} \text{ and the induction hypothesis}\\ &<&(n+1)(n+1)^n\quad \text{by } \textit{(Sc)} \text{ as $n<n+1$}\\ &=&(n+1)^{n+1}\qquad\text{by definition of powers} \end{array} \] Hence the result follows by mathematical induction.
Show that for all \(n\geq1\) \[ 1 + 3 + \ldots + (2n-1) = n^2 \]
Show that for all \(n\ge1\) \[ (1+a)^n \ge 1+na \] where \(a\) is any real number greater than -1.
Strong Induction
There is a more general form of induction called strong induction. In the standard form of induction (sometimes called weak induction) we show that when a result holds for \(n\) then it also holds for \(n+1\). For strong induction we show that if \(P(m)\) is true for all \(m<n+1\) then \(P(n+1)\) is true.
The idea is that this should make it easier to prove \(P(n+1)\) as we can use all of the statements \(P(1),P(2),\dots,P(n)\).
Strong induction is really just induction where the the induction hypothesis is that \(P(1),P(2),\dots,P(n)\) are all true.
In the induction step we must therefore prove that \(P(1),P(2),\dots,P(n),P(n+1)\) are all true. But since \(P(1),P(2),\dots,P(n)\) are true by assumption we only need to show that \(P(n+1)\) is true.
In a strong induction we may start with multiple cases in the base step, i.e. we prove \(P(1),P(2),\dots, P(k)\) directly for some (hopefully small) \(k\), and then start the induction at \(k\).
Solution. The base step in this case, involves proving the statement for \(n=3\) and \(n=4\). Since \(\alpha <2 = f_3\) and \(\alpha^2 = (3+\sqrt{5})/2 < 3 = f_4\), the result is true for \(n=3\) and \(n=4\).
Suppose then that \(f_k > \alpha^{k-2}\) for \(k=3,4,\dots,n\) with \(n\geq 4\) (this is the induction hypothesis) and consider the case \(k = n+1\).
We know in particular that \(f_n>\alpha^{n-2}\) and \(f_{n-1}>\alpha^{(n-1)-2}=\alpha^{n-3}\).
It is easy to check that \(\alpha^2 = \alpha + 1\). Hence \[ \alpha^{(n+1)-2} = \alpha^{n-1} = \alpha^2\alpha^{n-3} = (\alpha+1)\alpha^{n-3} = \alpha^{n-2}+\alpha^{n-3}. \] So \[f_{n+1}=f_n+f_{n-1} > \alpha^{n-2}+ f_{n-1} >\alpha^{n-2} + \alpha^{n-3} = \alpha^{n-1}\] using the inequalities for \(f_n,f_{n-1}\) from the induction hypothesis.
We have thus shown that \(f_k > \alpha^{k-2}\) for \(k=3,4,\dots,n+1\), and hence by induction \(f_k > \alpha^{k-2}\) for all \(k\geq 3\).