Proof by induction
A proof by induction is a direct proof that proves a predicate \(P(n)\) evaluates to a true proposition for every integer \(n \geq b.\) It does this by establishing a base case \(P(b)\) and showing an inductive step can always be taken from \(P(k)\) to \(P(k + 1)\) for any integer \(k \geq b.\) Then, all cases can be considered proven, according to the principle of mathematical induction (PMI):
- A base case, \(P(b)\), is true. Often, \(b\) is \(1\), but it can really be any fixed integer you want to start at.
- For any integer \(k \geq b\), \(P(k) \rightarrow P(k+1)\), meaning any case implies the case after it. This is the inductive step.
In an inductive step \(P(k) \rightarrow P(k+1)\), the assumption \(P(k)\) is known as the inductive hypothesis. Thinking about how it can imply \(P(k+1)\) will help you come up with a working inductive step.
You can imagine a proof by induction as trying to connect the base case to any arbitrary case through infinitely many implications.
Proofs by induction are considered direct proofs. Once you prove the base case and inductive step, you essentially have the hypothesis: \(P(1) \land (P(1) \rightarrow P(2)) \land (P(2) \rightarrow P(3)) \land (P(3) \rightarrow ...)\), from which you can deduce the conclusion: \(P(1) \land P(2) \land P(3) \land ...\)
Proofs by induction are preferred when trying to show a statement holds true for all elements in a sequence, set, or other recursively defined structures.
If you're new to writing proofs by induction, you may feel more comfortable following a "recipe" like this:
- State the variable you intend to perform induction on.
- Establish a base case by checking the case where the variable is input as some integer \(b.\)
- To make an inductive step, assume the \(k\) case is true, for \(k \geq b.\) Use this to show the \(k+1\) case must also be true.
- Write out the implication you've just proven. Then, state the principle of mathematical induction, and you're done! \(■\)
Here's an example of a proof by induction, with plenty of extra comments to make it clear what's going on:
Proof by induction: Let \(P(n)\) be defined as the following predicate: $$P(n) : \sum\limits_{i=1}^{n}i = \frac{n(n+1)}{2}$$ We will show \(P(n)\) holds true for all positive integers by performing induction on \(n.\)
Base case:
Let's start from the base case \(n = 1\): $$P(1) : \sum\limits_{i=1}^{1}i = \frac{1(1+1)}{2}$$ $$(1) = \frac{1(2)}{2}$$ $$1 = 1\checkmark$$ The base case holds true.
Inductive step:
Now, the difficult part. We need to prove \(P(k)\) implies \(P(k + 1)\), for \(k \geq 1.\) In other words, we must deduce: $$P(k + 1) : \sum\limits_{i=1}^{k + 1}i = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$$ From the inductive hypothesis: $$P(k) : \sum\limits_{i=1}^{k}i = \frac{k(k+1)}{2}$$ Well, we know intuitively that \(\sum\limits_{i=1}^{k + 1}i\), the sum of the first \(k+1\) positive integers, must be equal to the sum of the first \(k\) positive integers plus that last positive integer, \(k+1\): $$\sum\limits_{i=1}^{k + 1}i = \sum\limits_{i=1}^{k}i + (k + 1)$$ According to our inductive hypothesis, \(\sum\limits_{i=1}^{k}i = \frac{k(k+1)}{2}.\) Substituting: $$\sum\limits_{i=1}^{k + 1}i = (\frac{k(k+1)}{2}) + (k + 1)$$ $$\sum\limits_{i=1}^{k + 1}i = \frac{k(k+1)}{2} + \frac{2(k + 1)}{2}$$ $$\sum\limits_{i=1}^{k + 1}i = \frac{k(k+1) + 2(k + 1)}{2}$$ $$\sum\limits_{i=1}^{k + 1}i = \frac{k^2 + 3k + 2}{2}$$ After factoring: $$\sum\limits_{i=1}^{k + 1}i = \frac{(k+1)(k+2)}{2}$$ Thus, it can be concluded that if \(\sum\limits_{i=1}^{k}i = \frac{k(k+1)}{2}\) for \(k \geq 1\), then \(\sum\limits_{i=1}^{k + 1}i = \frac{(k+1)(k+2)}{2}.\) By the principle of mathematical induction, \(\sum\limits_{i=1}^{n}i = \frac{n(n+1)}{2}\) for \(n \geq 1.\) \(■\)
Here's another, much more compact proof by induction:
Proof by induction: Let's perform induction on \(n.\)
Base case:
$$n = 5 : 2^{(5)} > 4(5)$$ $$32 > 20\checkmark$$ Inductive step: Assume \(2^k > 4k\) for \(k \geq 5.\) We want to show \(2^{(k+1)} > 4(k+1)\), which simplifies to \(2^{k+1} > 4k + 4.\) According to the inductive hypothesis: $$2^k > 4k$$ Therefore: $$2 \times 2^k > 2 \times 4k$$ $$2^{k+1} > 8k$$ We've now established that \(2^{k+1} > 8k\), but is \(8k > 4k + 4\)? Since \(k \geq 5\), it is a positive integer greater than or equal to \(1\), so we can safely assume: $$8k > 4k + 4$$ Combining this with the previous inequality: $$2^{k+1} > 4k + 4$$ Thus, it can be concluded that if \(2^k > 4k\) for \(k \geq 5\), then \(2^{k+1} > 4k + 4.\) By the principle of mathematical induction, \(2^n > 4n\) for integers \(n \geq 5.\) \(■\)