Proof by strong induction
A proof by strong induction is a variation of a proof by induction in which all preceding cases can be assumed true to prove the next case, strengthening the inductive hypothesis. By contrast, a proof by induction is restricted to only being able to use the immediately preceding case to prove the next case.
Still, the two types of proof share the same goal: to prove that a predicate \(P(n)\) holds true for all \(n \geq b.\) What's new is that in a proof by strong induction, there are multiple base cases, ranging from \(P(a)\) to \(P(b)\), where \(a \leq b\), and taking an inductive step involves assuming \(P(k)\) as well as all the cases that came before it hold true (with \(P(a)\) being the first case), in order to show \(P(k + 1)\) holds true, where \(k \geq b.\) All cases will then be proven by the principle of strong mathematical induction:
- The base cases, \(P(a)\) through \(P(b)\), are all true.
- For any integer \(k \geq b\), \((P(a) \land ... \land P(k)) \rightarrow P(k+1)\), meaning that the assumption that all preceding cases are true is enough to imply the next case. This is the inductive step.
Proofs by strong induction are favored when a preceding case does not imply the next case, but rather some case further ahead. With an appropriate number of base cases, you can ensure that all elements are covered.
The number of base cases you'll need may depend on the distance between cases. For example, if the trend seems to be that \(P(x)\) implies \(P(x + 3)\), you'll likely end up needing \(3\) base cases: \(P(a), P(a+1), P(a+2)\), where \(b\) would be \(a+2.\) As a general rule, your base cases should include every case before the one that is implied by your first base case, \(P(a).\) Any more base cases would be unnecessary as this should be enough to cover all elements.
Here's a recipe you can follow for proofs by strong induction, if you like that sort of thing:
- State the variable you intend to perform strong induction on.
- Establish base cases by checking each case, starting with using \(a\) as input for the variable, and ending with \(b.\) Preferably, the \(b + 1\) case should appear to be implied by the \(a\) case.
- To make an inductive step, assume the \(j\) case is true, for every \(j\) in the range \(a \leq j \leq k\), where \(k \geq b.\) Use algebra on \(k \geq b\) to determine which cases fall into the range of assumption so that you can use them to show the \(k+1\) case must also be true.
- Write out the implication you've just proven. Then, state the principle of strong mathematical induction, and you're done! \(■\)
With all that said, let's dive into some proofs by strong induction!
As before, let's start with a heavily-commented version so that the thought process behind the proof is easier to see:
Proof by strong induction: Let \(P(n)\) be defined as the following predicate: $$P(n) : f_n \leq 2^n$$ We will show \(P(n)\) holds true for all non-negative integers by performing strong induction on \(n.\)
Base cases:
Let's start from the base case \(n = 0\): $$P(0) : f_0 \leq 2^0$$ $$0 \leq 1\checkmark$$ It holds. Next, \(n = 1\): $$P(1) : f_1 \leq 2^1$$ $$1 \leq 2\checkmark$$ It also holds. We could keep going, but these are the only base cases we really need. Interestingly, the order of the recurrence relation (how far back one needs to go to determine the next element) is \(2\), the same as the number of base cases we need.
Inductive step:
We need to prove that if \(P(j)\) holds true for every \(j\) in the range \(0 \leq j \leq k\), where \(k \geq 1\), then \(P(k + 1)\) also holds true. In other words, we must deduce: $$P(k + 1) : f_{k+1} \leq 2^{k+1}$$ From the inductive hypothesis (where we assume every case before and including \(P(k)\) holds true): $$P(a) \land ... \land P(k)$$ $$f_0 \leq 2^0 \land ... \land f_k \leq 2^k$$ By definition of the Fibonacci sequence, we can begin by writing: $$f_{k+1} = f_{k} + f_{k-1}$$ Since \(k \geq 1\), \(k\) and \(k - 1\) both fall into the range of our strong inductive hypothesis, \(0 \leq j \leq k.\) That means we can use the assumptions \(f_k \leq 2^k\) and \(f_{k-1} \leq 2^{k-1}.\) Adding these two inequalities results in \(f_k + f_{k-1} \leq 2^k + 2^{k-1}.\) Substituting: $$f_{k+1} = f_{k} + f_{k-1} \leq 2^k + 2^{k-1}$$ Again, since \(k \geq 1\), we know \(2^{k-1}\) is some positive integer. Adding a positive integer to a number will make it bigger. Therefore: $$f_{k+1} \leq 2^k + 2^{k-1} \leq 2^k + 2^{k-1} + 2^{k-1}$$ $$= 2^k + 2 \times 2^{k-1}$$ $$= 2^k + 2^k$$ $$= 2 \times 2^k$$ $$= 2^{k+1}$$ Thus, it can be concluded that if \(f_j \leq 2^j\) for all \(j\) in \(0 \leq j \leq k\), and \(k \geq 1\), then \(f_{k+1} \leq 2^{k+1}.\) By the principle of strong mathematical induction, \(f_n \leq 2^n\) for \(n \geq 0.\) \(■\)
The Fibonacci sequence favors proofs by strong induction because of the nature of its recurrence relation. Although, it is best to try standard induction first if you're not sure, so that you can better understand why stronger induction might be needed for your particular theorem.
Now, another example, this time written compactly:
Proof by strong induction: Let's perform strong induction on \(n.\)
Base cases:
$$n = 12 : 12 = 3(4) + 7(0)\checkmark$$ $$n = 13 : 13 = 3(2) + 7(1)\checkmark$$ $$n = 14 : 14 = 3(0) + 7(2)\checkmark$$ Inductive step:
Assume every \(j\) in the range \(12 \leq j \leq k\), where \(k \geq 14\), can be expressed as a linear combination of \(3\) and \(7.\) Since \(k \geq 14\), \(k - 2 \geq 12\), which places \(k - 2\) within the range of assumption, \(12 \leq j \leq k.\) According to our strong inductive hypothesis, for some integers \(x\) and \(y\): $$k - 2 = 3x + 7y$$ Let's add \(3\) to both sides of this equation: $$k - 2 + 3 = 3x + 7y + 3$$ $$k + 1 = 3(x + 1) + 7y$$ Thus, it can be concluded that if every \(j\) in the range \(12 \leq j \leq k\), where \(k \geq 14\), can be expressed as a linear combination of \(3\) and \(7\), then \(k + 1\) can be expressed as a linear combination of \(3\) and \(7.\) All you need to do is add \(3.\) By the principle of strong mathematical induction, \(n\) can be expressed as a linear combination of \(3\) and \(7\) for \(n \geq 12.\) \(■\)
You might remember the fundamental theorem of arithmetic. It can be proven with strong induction:
Proof by strong induction: Let's perform strong induction on \(n.\)
Base case:
\(2\) is prime, so it already qualifies as a product of primes (specifically, of one prime, itself): $$n = 2 : 2 = 2\checkmark$$ Inductive step:
Assume every \(j\) in the range \(2 \leq j \leq k\), where \(k \geq 2\), can be expressed as a product of primes. If \(k + 1\) is prime, then, like \(2\), it already qualifies as a product of primes, and our work here is done. So, let's assume \(k + 1\) is composite. By the definition of a composite number, it must have some factor \(a\), where \(1 < a < k + 1\), alternatively written as \(2 \leq a \leq k\), since \(a\) is an integer. Being a factor of \(k + 1\) means \(a\) divides \(k + 1\), so an integer \(b\) must exist such that: $$k + 1 = ab$$ That means \(b\) is also a factor of the composite number \(k + 1\), so it is likewise restricted to the range \(2 \leq b \leq k.\) At this point, we have determined that \(2 \leq a \leq k\) and \(2 \leq b \leq k\), so the integers \(a\) and \(b\) fall into the range of assumption, \(2 \leq j \leq k.\) According to our strong inductive hypothesis, \(a\) and \(b\) can therefore both be expressed as products of primes: $$a = p_1 \times p_2 \times ... \times p_x$$ $$b = q_1 \times q_2 \times ... \times q_y$$ Substituting: $$k + 1 = (p_1 \times p_2 \times ... \times p_x)(q_1 \times q_2 \times ... \times q_y)$$ Thus, it can be concluded that if every \(j\) in the range \(2 \leq j \leq k\), where \(k \geq 2\), can be expressed as a product of primes, then \(k + 1\) can be expressed as a product of primes. By the principle of strong mathematical induction, every integer \(n\) has a prime factorization for \(n \geq 2.\) \(■\)
Maybe you've realized a trend in these proofs by strong induction. Generally, the inductive steps involve discovering which cases fall into the range of assumption so that you can make use of the strong inductive hypothesis.