Mathematical Induction is a a method of confirming conjectures (i.e. guesses) about the properties of mathematical objects.
The method uses the idea that if something is true for an arbitrary positive integer n and you can prove that it is also true for n + 1, then it must be true for all n greater than the initial n as well.
The steps in an inductive proof:
The format of an induction proof must always follow the steps outlined above.
Note that in step 3, you will need to use the inductive hypothesis to somehow reduce things to a form which will allow you to prove it is true for k+1.
Areas of Application
Common areas of application are:
However, induction does not provide any guidance on how to come up with a conjecture.
Example To prove that \[ \begin{align} 1^3 + 2^3 + \cdots + n^3 &= \frac{n^2}{4}(n+1)^2 \quad (1) \\ \end{align} \ \]
To show this is true for n=1, observe that the left hand side = 1 and the right hand side = 1/4.4 = 1. So the statement is true for n=1.
Assume the statement is true for n=k.
To show the statement is true for n = k+1, call the LHS \( S_{k+1} \). Then \[ \begin{align} S_{k+1} &= 1^3 + 2^3 + \cdots + k^3 + (k+1)^3 \\ \end{align}\]
Use the inductive hypothesis to reduce this \[ \begin{align} S_{k+1} &= \frac{k^2}{4}(k+1)^2 + (k+1)^3 \quad \\ &= \frac{1}{4}(k+1)^2[k^2 + 4(k+1)] \quad \\ &= \frac{(k+1)^2}{4}(k+2)^2 \quad \\ &= \frac{(k+1)^2}{4}((k+1)+1)^2 \quad \\ \end{align} \ \] Now the RHS has the same form as the RHS of (1) with k+1 substituted for n. So the statement is true for n = k+1.
By the principle of mathematical induction, statement (1) is true for \( n \ge 1 \).
Write down the inductive hypothesis for the above example.
Guided Examples
O E Qs
Example A divisibility example - to prove that \[ \begin{align} \text{For n } \ge 2, \quad n^3 - n \end{align}\] is divisible by 3.
To show this is true for n = 2, substitute to get 23 - 2 = 6. So the statement is true for n = 2.
Assume the statement is true for n = k. Here the inductive hypothesis means \[ \begin{align} k^3 - k &= 3m \\ \end{align}\] for some integer m.
To show the statement is true for n = k+1, \[ \begin{align} (k+1)^3 - (k+1) &= k^3 + 3k^2+ 3k +1 - k - 1 \\ &= k^3 - k + 3k^2 + 3k \\ &= 3m + 3(k^2+k) \\ &= 3(m + k^2 + k) \end{align}\] which is divisible by 3.
So the statement is true for n = k+1. By the principle of mathematical induction, the statement is true for \( n \ge 2 \).
Express \(3^{k+1}\) as \(2a3^k + b3^k\). If you know that \(3^k - 1\) is divisible by 2, what can you say about \(3^{k+1} -1\) ?
Example An inequality example - to prove that \[ \begin{align} \text{For n } \ge 3, \quad n^2 \ge 2n+1 \quad \\ \end{align} \ \]
To show this is true for n = 3, substitute to get \[ 3^2 \ge 2.3 + 1 \] So the statement is true for n = 3.
Assume the statement is true for n = k.
To show the statement is true for n = k+1, \[ \begin{align} (k+1)^2 &= k^2+ 2k + 1 \quad \\ &\ge (2k+1) + 2k + 1 \quad \text{(inductive hypothesis)} \quad \\ &= 2(k+1) + 2k \quad \\ &\ge 2(k+1) + 1 \quad \text{(because } 2k \ge 1 \text{)} \quad \\ \end{align} \ \]
So the statement is true for n = k+1. By the principle of mathematical induction, the statement is true for \( n \ge 3 \).
Find the first value of n for which \(n! > 2^n\).