Proving inequalities

Induc­tion proves inequal­i­ties as well as equa­tions. The induc­tive step is a lit­tle dif­fer­ent: instead of reach­ing the tar­get exactly, you show that the $(k + 1)$ side is at least as big as some­thing you already know is big enough. Some inequal­i­ties are only true from a cer­tain num­ber onwards, so this les­son also shows how to start the induc­tion at a num­ber other than 1.

Work­ing with inequal­i­ties#

Two rules are used all the time:

• If $a > b$ and $c > 0$, then $ca > cb$. Mul­ti­ply­ing both sides by a pos­i­tive num­ber keeps the inequal­ity the same way round.
• If $a > b$ and $b \ge c$, then $a > c$. Inequal­i­ties can be chained.

The usual plan for the induc­tive step is: start from the left side of $P(k + 1)$, use the hypoth­e­sis to replace it by some­thing smaller (or larger), and then show that this is still at least the right side of $P(k + 1)$.

Exam­ple 1#

Prove that $2^n > n$ for every nat­ural num­ber $n$.

Base step. For $n = 1$: $2 > 1$. True.

Hypoth­e­sis. Assume $2^k > k$.

Induc­tive step. We must show $2^{k+1} > k + 1$. Mul­ti­ply the hypoth­e­sis by 2:

$$2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$$

The last step uses $k \ge 1$. So $2^{k+1} > k + 1$.

Con­clu­sion. By induc­tion, $2^n > n$ for all nat­ural num­bers $n$.

Exam­ple 2#

Prove that $3^n \ge 2n + 1$ for every nat­ural num­ber $n$.

Base step. For $n = 1$: $3 \ge 3$. True.

Hypoth­e­sis. Assume $3^k \ge 2k + 1$.

Induc­tive step. We must show $3^{k+1} \ge 2k + 3$.

$$3^{k+1} = 3 \cdot 3^k \ge 3(2k + 1) = 6k + 3 \ge 2k + 3$$

since $6k \ge 2k$ for pos­i­tive $k$. By induc­tion the result holds for all $n$.

Start­ing from a num­ber other than 1#

Some state­ments are false for small $n$ but true from some point on. Com­pare $2^n$ with $n^2$:

$2^n > n^2$ is true for $n = 1$, false for $n = 2, 3, 4$, and appears true from $n = 5$ on. Induc­tion can still prove this, using a slightly more gen­eral prin­ci­ple:

If $P(m)$ is true, and $P(k)$ implies $P(k + 1)$ for every $k \ge m$, then $P(n)$ is true for every $n \ge m$.

The domi­noes sim­ply start at posi­tion $m$ instead of posi­tion 1. In the base step you check $P(m)$, and in the induc­tive step you may use $k \ge m$.

Exam­ple 3#

Prove that $2^n > n^2$ for every nat­ural num­ber $n \ge 5$.

Base step. For $n = 5$: $32 > 25$. True.

Hypoth­e­sis. Assume $2^k > k^2$ for some $k \ge 5$.

Induc­tive step. We must show $2^{k+1} > (k + 1)^2 = k^2 + 2k + 1$.

$$2^{k+1} = 2 \cdot 2^k > 2k^2 = k^2 + k^2$$

So it is enough to show $k^2 \ge 2k + 1$ when $k \ge 5$. Since $k \ge 5$, $k^2 = k \cdot k \ge 5k = 2k + 3k \ge 2k + 15 > 2k + 1$. Hence $2^{k+1} > k^2 + 2k + 1 = (k + 1)^2$.

Con­clu­sion. By induc­tion, $2^n > n^2$ for all $n \ge 5$.

Fac­to­ri­als#

The prod­uct of the first $n$ nat­ural num­bers is called $n$ fac­to­r­ial, writ­ten $n!$:

$$n! = 1 \times 2 \times 3 \times \cdots \times n$$

So $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$. The key fact for induc­tion is $(k + 1)! = (k + 1) \times k!$.

Exam­ple 4#

Prove that $n! > 2^n$ for every nat­ural num­ber $n \ge 4$.

Check small cases first: $3! = 6 < 8 = 2^3$, but $4! = 24 > 16 = 2^4$. So we start at 4.

Base step. For $n = 4$: $24 > 16$. True.

Hypoth­e­sis. Assume $k! > 2^k$ for some $k \ge 4$.

Induc­tive step. We must show $(k + 1)! > 2^{k+1}$.

$$(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}$$

using $k + 1 > 2$, which is true since $k \ge 4$. By induc­tion the result holds for all $n \ge 4$.

Exam­ple 5: Bernoul­li's inequal­ity#

Prove that $(1 + x)^n \ge 1 + nx$ for every nat­ural num­ber $n$, where $x > -1$.

Base step. For $n = 1$: $1 + x \ge 1 + x$. True.

Hypoth­e­sis. Assume $(1 + x)^k \ge 1 + kx$.

Induc­tive step. Since $x > -1$, the num­ber $1 + x$ is pos­i­tive, so we may mul­ti­ply the hypoth­e­sis by it with­out revers­ing the inequal­ity:

$$(1 + x)^{k+1} = (1 + x)^k (1 + x) \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x$$

because $kx^2 \ge 0$. By induc­tion the result holds for all $n$.

For exam­ple, with $x = 0.1$ and $n = 10$ it says $1.1^{10} \ge 2$. (In fact $1.1^{10}$ is about 2.59.)

Prac­tice#

Prove each state­ment by induc­tion.

1. $3^n > n$ for every nat­ural num­ber $n$.
2. $2^n \ge n + 1$ for every nat­ural num­ber $n$.
3. $4^n \ge 3n + 1$ for every nat­ural num­ber $n$.
4. $2^n > 2n$ for every nat­ural num­ber $n \ge 3$.
5. $3^n > n^2$ for every nat­ural num­ber $n$.
6. $n! \ge 2^{n-1}$ for every nat­ural num­ber $n$.
7. $2^n > n^3$ for every nat­ural num­ber $n \ge 10$. (You may use $k^3 \ge 3k^2 + 3k + 1$ for $k \ge 4$.)
8. Find the small­est nat­ural num­ber $m$ such that $3^n > 2^n + 10$ for all $n \ge m$, and prove it.

Answers#

In each answer the base step and the key line of the induc­tive step are given.

1. Base: $3 > 1$. Step: $3^{k+1} = 3 \cdot 3^k > 3k \ge k + 1$.
2. Base: $2 \ge 2$. Step: $2^{k+1} \ge 2(k + 1) = 2k + 2 \ge k + 2$.
3. Base: $4 \ge 4$. Step: $4^{k+1} \ge 4(3k + 1) = 12k + 4 \ge 3k + 4$.
4. Base: $8 > 6$. Step: $2^{k+1} > 4k = 2k + 2k \ge 2k + 2$ for $k \ge 1$.
5. Base: $3 > 1$; also check $n = 2$: $9 > 4$. Step for $k \ge 2$: $3^{k+1} > 3k^2 = k^2 + 2k^2 \ge k^2 + 2k + 1$, because $2k^2 \ge 2k + 1$ when $k \ge 2$ ($2k^2 - 2k = 2k(k - 1) \ge 4$).
6. Base: $1 \ge 1$. Step: $(k + 1)! = (k + 1) \cdot k! \ge (k + 1) \cdot 2^{k-1} \ge 2 \cdot 2^{k-1} = 2^k$.
7. Base: $2^{10} = 1024 > 1000$. Step: $2^{k+1} > 2k^3 = k^3 + k^3 \ge k^3 + 3k^2 + 3k + 1 = (k + 1)^3$.
8. $3^2 = 9 < 14 = 2^2 + 10$ but $3^3 = 27 > 18 = 2^3 + 10$, so $m = 3$. Step: $3^{k+1} = 3 \cdot 3^k > 3(2^k + 10) = 3 \cdot 2^k + 30 > 2 \cdot 2^k + 10 = 2^{k+1} + 10$.