Mathematical Induction Inequality

Mathematical Induction Inequality is being used for proving inequalities. It is quite often applied for subtraction and/or greatness, using the assumption in step 2. Let’s take a look at the following hand-picked examples.

Basic Mathematical Induction Inequality

Prove $4^{n-1} \gt n^2$ for $n \ge 3$ by mathematical induction.

Step 1:  Show it is true for $n=3$.
LHS $=4^{3-1} = 16$
RHS $=3^2=9$
LHS > RHS
Therefore it is true for $n=3$.
Step 2:  Assume that it is true for $n=k$.
That is, $4^{k-1} > k^2$.
Step 3:  Show it is true for $n=k+1$.
That is, $4^{k} > (k+1)^2$.
\begin{aligned} \displaystyle \require{ASMSymbols} \require{color} \text{LHS } &= 4^k \\ &= 4^{k-1+1} \\ &= 4^{k-1} \times 4 \\ &\gt k^2 \times 4 &\color{red}{ \text{by the assumption } 4^{k-1} > k^2} \\ &= k^2 + 2k^2 + k^2 &\color{red}{2k^2 > 2k \text{ and } k^2 > 1 \text{ for } k \ge 3} \\ &\gt k^2 + 2k + 1 \\ &= (k+1)^2 \\ &=\text{RHS} \\ \text{LHS } &\gt \text{ RHS} \end{aligned}
Therefore it is true for $n=k+1$, assuming that it is true for $n=k$.
Therefore $4^{n-1} \gt n^2$ is true for $n \ge 3$.

Mathematical Induction Inequality using Differences

Prove $n^2 \lt 2^n$ for $n \ge 5$ by mathematical induction.

It is quite often used to prove $A > B$ by $A-B >0$.

Step 1:  Show it is true for $n=5$.
LHS $= 5^2 = 25$
RHS $= 2^5 = 32$
LHS $\lt$ RHS
It is true for $n=5$.
Step 2:  Assume that it is true for $n=k$.
That is, $k^2 \lt 2^k$.
Step 3:  Show it is true for $n=k+1$.
That is, $(k+1)^2 \lt 2^{k+1}.$
\begin{aligned} \displaystyle \require{ASMSymbols} \require{color} \text{RHS } – \text{ LHS } &= 2^{k+1}-(k+1)^2 \\ &= 2 \times 2^k-(k^2+2k+1) \\ &\gt 2 \times k^2-(k^2+2k+1) &\color{red}{\text{ by the assumption from Step 2}} \\ &= k^2-2k-1 \\ &= (k-1)^2-2 \\ &\gt 0 &\color{red}{\text{since } k \ge 5 \text{ and so } (k-1)^2 \ge 16} \\ 2^{k+1}-(k+1)^2 &\gt 0 \\ (k+1)^2 &\lt 2^{k+1} \\ \end{aligned}
Therefore it is true for $n=k+1$, assuming it is true for $n=k$.
Therefore it is true for $n=k+1$ is true for $n \ge 5$.