Section 8.3 Induction with inequalities
Remember that if a function \(a_n\) is big-O of a function \(b_n\text{,}\) that means there exist integers \(k\) and \(C\) such that for all \(n \ge k\text{,}\) \(a_n \le C|b_n|\text{.}\) It turns out that induction can be used to prove many big-O relationships:
Polynomials satisfy a recurrence relation, e.g. \((k+1)^2 = k^2 + 2k + 1\)
Exponential functions satisfy two recurrence relations: \(2^{k+1}\) can be expressed as either \(2\cdot 2^k\) or \(2^k + 2^k\) depending on whether multiplication or addition is appropriate
Factorials satisfy the recurrence \((k+1)! = (k+1)k!\)
So, since many expressions involved in these inequalities can be expressed recursively, they are natural candidates for proof by induction.
Many readers will struggle with manipulating inequalities. When you manipulate an equation, your hands are more or less tied with each step: something done to one side of the equation must be exactly done to the other. Inequalities are much weaker statements, and so you have a much wider variety of options. Consider the following inequality:
If this inequality is true, then you will likely believe that so are
and
However, it may surprise you that we can also infer
and
as well as
and
If we (say) add \(5\) to \(x\) on the left, there are infinitely many things we can do to \(y\) on the right to preserve a true inequality! The sheer amount of choice on our hands can make it difficult to find the next step in a proof by induction. We will address that later. For now, let's write down the appropriate theorem about manipulating inequalities.
Theorem 8.3.1.
Suppose that there are real numbers \(x\) and \(y\) such that
Then, if \(a\) and \(b\) are real numbers with \(0 \le a \le b\text{,}\) then
as well as
The following statement may clarify things, or make them more confusing. When we add \(a\) and \(b\) respectively to the left and right sides of an equation, the equation is still true if and only if \(a=b\text{.}\) When we add \(a\) and \(b\) to the left and right sides of an inequality, the inequality is still true if and only if \(a \le b\text{.}\) The “rules of math” (whatever those are) haven't changed; the relation we're talking about has!
Now, how to deal with all this choice when writing the proof? The answer is simple: we will cheat. It is logically invalid to prove \(P(k) \to P(k+1)\) by assuming \(P(k+1)\) and working backward to \(P(k)\text{,}\) meaning that if you prove \(P(k+1)\to P(k)\text{,}\) you have just proven a different sentence. You have done the dishes when asked to take out the trash. However, suppose that all of the steps you used to show \(P(k+1) \to P(k)\) could be reversed. Then, you'd have a proof of \(P(k) \to P(k+1)\text{,}\) wouldn't you?
The trick is to—on a separate piece of paper, or on a clearly separate section of the same paper—write down some “scratch work” where you assume \(P(k+1)\) is true, cancel the appropriate values, and reveal what needs to be added to the left and right sides of the inductive hypothesis. Then—and this part is very important— you must write the proof in the other direction, as if the reader cannot see your scratch work at all. All the scratch work does is it reveals to you (the proof writer) which of the infinitely many things to add to your inequality is the correct thing.
(“Scratch work” is widely used in other areas of mathematics. For example, in “real analysis” (the subject where the theorems of calculus and probability are proven) many statements start with “For all \(\varepsilon > 0\) (that's “epsilon”), there exists a \(\delta > 0\) (“delta”) such that...” Standard operating procedure is to assume the \(\varepsilon\) and then solve for the appropriate value of \(\delta\) in terms of \(\varepsilon\text{.}\))
Enough talk, let's have an example.
Theorem 8.3.2.
If \(n \ge 5\text{,}\) then \(2n^2 + 4n + 1 \le 3n^2\text{.}\)
Note that this statement is really saying that \(2n^2+4n+1 = O(n^2)\text{,}\) because we have chosen the witnesses \(k=5\) and \(C=3\text{.}\)
Once again, let's talk through the proof before writing it down.
We will check the base case when \(n=5\text{,}\) we will declare our inductive hypothesis that
and we will claim that
The difficulty is that there is something that must be added to \(2k^2+4k+1\text{,}\) and something else that must be added to \(3k^2\text{,}\) to result in the desired inequality. We have no idea what those needed expressions are. So, let's do some scratch work. Start with the desired inequality
and expand, but do not simplify:
Some familiar-looking terms have appeared. We have assumed that \(2k^2+4k+1 \le 3k^2\text{.}\) If we cancel the terms in the inductive hypothesis from the desired statement, that leaves us with
Now it is okay to simplify:
If this statement is true, we are done, because we can “add back” the terms from the inductive hypothesis in our proof. To see that this statement is true, solve for \(k\text{.}\)
is good enough, because we know that \(2k \ge 10\) (since \(k \ge 5\)). If you really want, you can instead divide through by \(2\text{:}\)
which is still true because we have assumed \(k \ge 5\text{.}\)
We have the appropriate starting statement, and now we are ready to write a proof.
Proof.
Let \(n=5\text{.}\) Then since
the desired statement is true in the base case.
Suppose that there exists an integer \(k \ge 5\) such that
We claim
Because \(k \ge 5\text{,}\) we can infer
which is equivalent to saying
Since we have assumed that \(2k^2 + 4k + 1 \le 3k^2\text{,}\) we can conclude
which was our claim. Therefore, by induction, \(2n^2 + 4n + 1 \le 3n^2\) for all integers \(n \ge 5\text{.}\)
Notice how the statement \(3 \le 2k\) seems to come out of nowhere. When you encounter a statement in a proof that appears to come out of the blue, it is likely the result of having worked backwards first. However, the proof reads purely forwards: assume \(P(k)\text{,}\) make a sequence of valid inferences, conclude \(P(k+1)\text{.}\) The scratch work is nowhere to be seen, only its fruits.
The previous statement we proved was additive in the sense that all the recurrences involved addition. Let's do one more example that is multiplicative in nature.
Example 8.3.3.
Prove that \(2^n \le n!\) for all integers \(n \ge 4\text{.}\) (This is a proof that \(2^n = O(n!)\) for \(k=4\) and \(C=1\text{.}\))
Try the scratch work and the proof yourself first. Then read ahead for the scratch work, followed by the proof.
Here is the scratch work:
by canceling (dividing by) the terms in the assumption that \(2^k \le k!\text{.}\) The statement \(2 \le k+1\) is blatantly true since \(k\) is at least \(4\text{.}\)
Proof.
Let \(n=4\text{.}\) Then, since
the statement is true in the base case. Next, assume there is some integer \(k \ge 4\) for which
We want to show that
Since \(2 \le k+1\) and \(2^k \le k!\) by assumption, we conclude
as desired.
Thus, by mathematical induction, \(2^n \le n!\) for all integers \(n \ge 4\text{.}\)