Elementary Discrete Mathematics

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.

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!

We will employ the transitivity of inequality. (This is arguably the most important word in Part IV, but we'll borrow it here.) If \(x \le y\) and \(y \le z\text{,}\) then \(x \le z\) as well. This means that we can substitute some terms of an expression with terms we know are bigger, and the resulting expression will also be bigger. For instance, suppose we know that \(x \le y\text{.}\) Then, we also know that \(x+2 \le y+3\text{.}\) To prove that, we can do a sequence of substitutions:

The first line relies on our “obvious” knowledge that \(2 \le 3\text{.}\) If this statement were something non-“obvious”, we should justify it, as well. The second statement relies on our prior assumption that \(x \le y\text{.}\) Together, we have proven \(x + 2 \le y + 3\text{.}\) This is basically how our proofs of inequalities will proceed. Let's have our first full example.

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

for some integer \(k \ge 5\text{,}\) and we will claim that

The hard part is getting from the first statement to the second. We will proceed by starting with the left-hand expression \(2(k+1)^2 + 4(k+1) + 1\) and, through a sequence of inequalities and equalities, prove it must be less than \(3(k+1)^2\text{.}\) (Students who have had trigonometry may recall a similar approach to establishing trigonometric identities.)

Let's start by “following our noses”: seeing something like \(2(k+1)^2\) begs us to multiply it out and distribute the \(2\text{.}\) Let's do that, then.

This is where the recursive element comes in. We recognize the terms \(2k^2 + 4k + 1\) from our inductive hypothesis, and we have assumed that together they are less than \(3k^2\text{.}\) We will invoke that hypothesis here. Notice that you must supress your urge to “combine like terms” as it is actually the opposite of helpful in this case.

Now it is getting a little easier to see how we arrive at \(3(k+1)^2\text{.}\) Working backwards a little bit, we know that \(3(k+1)^2\) is equal to \(3k^2 + 6k + 3\text{.}\) Therefore, our last step must be to substitute the \(4k+6\) with \(6k+3\text{.}\) Being that this is a proof, we must be able to justify that indeed \(4k+6 \le 6k+3\text{.}\)

Since we are just sketching the proof, we are free to work backwards and forwards to fill in the missing pieces. The proof itself, however, can only flow forwards. Let's work backwards to make sure our inequality is indeed true.

Subtract \(4k\) and \(3\) from both sides.

We could go one step further and divide everything by \(2\text{,}\) but this isn't necessary. Recall our assumption that \(k \ge 5\) in the first place! Therefore, \(2k\) is at least \(10\text{,}\) so \(3 \le 2k\) is true as long as \(k \ge 5\text{.}\)

We are ready to stitch together the entire calculation into one piece.

Remember, in the proof we will be clear to explain why these substitutions are appropriate.

Let us have another example. This time, try to write the proof yourself (using the above example to guide you) before looking at the solution.

The previous statements we proved were additive in the sense that all the recurrences involved addition. Let's do one more example that is multiplicative in nature.

The previous example is a proof that that \(2^n = O(n!)\) for witnesses \(k=4\) and \(C=1\text{.}\) By the way, the \(k\) that witnesses a big-\(O\) relationship is not the same as the \(k\) we use in an inductive proof!