Mathematical Induction: A Deep Dive into Inequalities

Problem Statement

Mathematical Induction is a powerful technique for proving that a statement is true for an infinite sequence of integers. It relies on the "domino effect":

1. Base Case: Prove the first domino falls (the statement is true for the starting integer, usually $n=1$).
2. Assumption Step: Assume a specific domino falls (assume the statement is true for $n=k$).
3. Inductive Step: Prove that if the $k$-th domino falls, it forces the next domino to fall (use the assumption to prove the statement is true for $n=k+1$).

In Extension 1, induction is mostly used for algebraic series (e.g., $1+2+3...$). In Extension 2, we frequently apply induction to inequalities. Inequality inductions are conceptually harder because instead of substituting and simplifying an equation, you must construct a chain of logical "greater thans" to bridge the gap.

Consider the inequality: Prove by mathematical induction that $3^n > n^2$ for all integers $n \ge 1$.

(a) Prove the base case for $n=1$.

(b) State the inductive assumption for $n=k$. What is the goal you need to prove for $n=k+1$?

(c) Prove the inductive step. (Hint: You will need to show that $2k^2 > 2k + 1$ for $k \ge 1$ along the way).

Hints

• Part (a): Substitute $n=1$ into the Left Hand Side (LHS) and Right Hand Side (RHS). Show that $\text{LHS} > \text{RHS}$.
• Part (b): The assumption is simply swapping $n$ for $k$. The goal is swapping $n$ for $k+1$. Write the goal down explicitly so you know what algebraic form you are aiming for.
• Part (c): Start with the LHS of your goal for $n=k+1$, which is $3^{k+1}$. Break this down into $3 \times 3^k$. Now, use your assumption from part (b) to replace the $3^k$ term, creating a "greater than" inequality. Expand the resulting expression and show that it is greater than the RHS of your goal: $(k+1)^2 = k^2 + 2k + 1$.

Solutions

Part (a): The Base Case

1. Let $n = 1$.
2. $\text{LHS} = 3^1 = 3$
3. $\text{RHS} = 1^2 = 1$
4. Since $3 > 1$, the statement is true for $n=1$.

Part (b): Assumption and Goal

1. Assume the statement is true for some integer $n=k$, where $k \ge 1$. Assumption: $3^k > k^2$
2. Goal: We need to prove the statement is true for $n=k+1$. Required to Prove (RTP): $3^{k+1} > (k+1)^2$ Which expands to: $3^{k+1} > k^2 + 2k + 1$.

Part (c): The Inductive Step

1. Start with the LHS of our goal: $\text{LHS} = 3^{k+1}$
2. Use index laws to split the base: $\text{LHS} = 3 \times 3^k$
3. Now, use the inductive assumption ($3^k > k^2$). We can replace $3^k$ with $k^2$, but we must change the equals sign to a "greater than" sign: $3 \times 3^k > 3 \times k^2$ So, $3^{k+1} > 3k^2$.
4. We now need to connect $3k^2$ to our required RHS of $(k^2 + 2k + 1)$. Let's break $3k^2$ apart: $3k^2 = k^2 + 2k^2$
5. We need to show that this is greater than $k^2 + 2k + 1$. Since they both share a $k^2$, we just need to show that $2k^2 > 2k + 1$ for all $k \ge 1$. Let's test this sub-inequality:
   • For $k=1$: $2(1)^2 = 2$. $2(1)+1 = 3$. Wait, $2$ is not greater than $3$.
   • Let's check the original inequality for $n=2$: $3^2 > 2^2 \implies 9 > 4$. This is true. Let's re-evaluate our proof strategy. The standard induction step requires $k \ge 1$, but perhaps the algebraic bounding only works for $k \ge 2$. Let's prove a sub-case for $k \ge 2$.
   • If $k \ge 2$: $k^2 \ge 2k$ (multiply both sides by $k$) $k^2 \ge 4$
   • Let's rewrite $3k^2$: $3k^2 = k^2 + k^2 + k^2$
   • Since $k \ge 2$, $k^2 \ge 2k$. And $k^2 \ge 4 > 1$.
   • Therefore, $k^2 + k^2 + k^2 > k^2 + 2k + 1 = (k+1)^2$.
6. Alternative simpler approach for step 5: We want to show $3k^2 > k^2 + 2k + 1$. Consider the difference: $3k^2 - (k^2 + 2k + 1) = 2k^2 - 2k - 1$. We need to show this quadratic is $>0$ for $k \ge 1$. Roots are $k = \frac{2 \pm \sqrt{4 - 4(2)(-1)}}{4} = \frac{2 \pm \sqrt{12}}{4}$. The positive root is approx 1.36. So the difference is positive for integers $k \ge 2$.
7. Because our algebra only holds strongly for $k \ge 2$, we must manually verify $n=2$ as a secondary base case. For $n=2$: $\text{LHS} = 3^2 = 9$, $\text{RHS} = 2^2 = 4$. $9 > 4$. True.
8. Now we can conclude: $3^{k+1} > 3k^2 = k^2 + 2k^2 > k^2 + 2k + 1$ (for $k \ge 2$) $3^{k+1} > (k+1)^2$
9. Conclusion: The statement is true for $n=1$ and $n=2$. If true for $n=k$, it is true for $n=k+1$. Therefore, by the principle of mathematical induction, $3^n > n^2$ for all integers $n \ge 1$.

Takeaways

• The Inequality Chain: Unlike equations where you aim for $\text{LHS} = \text{RHS}$, inequality proofs require building a chain: $\text{LHS} > \text{Expression 1} > \text{Expression 2} > \text{RHS}$.
• The "Sub-Proof": It is extremely common in inequality inductions to hit a point where you need to prove a smaller, secondary inequality (like $2k^2 > 2k+1$) to bridge the gap to the RHS.
• Multiple Base Cases: If your algebraic bounding in the inductive step only works for larger values of $k$, you must manually prove the lower values as additional base cases to maintain the unbroken "domino" chain.

Further Readings

• HSC Proofs: https://vumaths.com/booklets/hsc-proofs/
• HSC Inequalities: https://vumaths.com/booklets/hsc-inequalities/
• HSC Polynomials: https://vumaths.com/booklets/hsc-polynomials/

Connect with me

Induction is the workhorse of mathematical proofs. To master the art of chaining inequalities, check out the booklets on Vu's Maths Hub. I walk through complex HSC exam induction questions on my YouTube channel. Follow my Instagram for daily maths tips, and subscribe to my Substack to learn how induction applies to algorithms!