Two challenging induction proofs with inequalities (aiming for a 7)

Ask any IB Maths AA HL student which proof they dread most, and induction with inequalities is near the top of the list. The steps can look like terms appear and vanish out of nowhere. They don't — there's a logic behind every move. In this post we work through two of the hardest types you can be asked, one with factorials and one with binomial coefficients, so you're in a strong position to aim for a 7, whether in a school assessment or the real IB exam.

The five steps (every induction proof, every time)

Every induction proof is the same five steps:

1. Propositional function P(n) — restate what you're proving.
2. Base case — test the first valid value.
3. Inductive hypothesis — assume P(k) is true for some k.
4. Inductive step — prove P(k+1) from P(k). (the hard part for inequalities)
5. Conclusion — the standard closing statement.

Steps 1–3 are roughly 30% of the marks and there's no excuse to drop them. The real difficulty lives in step 4.

The one idea that makes inequality induction click

With inequalities, step 4 means starting from P(k) and manipulating it without breaking the inequality until you reach P(k+1). Only two moves are ever needed, and neither breaks an inequality:

• Make the larger side larger, or the smaller side smaller. If A ≥ B, then replacing B with anything smaller keeps the inequality, and replacing A with anything larger keeps it too.
• Multiply both sides by the same positive number.

Every "magic" substitution below is just one of these two moves — nothing comes out of nowhere.

Example 1 — induction with factorials

Prove by induction that (2n)! ≥ 2ⁿ(n!)² for all positive integers n.

Step 1 — Propositional function

$P(n): (2n)! \ge 2^{n}(n!)^{2}, \quad n \in \mathbb{Z}^{+}$

Step 2 — Base case (n = 1)

$\text{LHS} = (2\cdot 1)! = 2! = 2 \qquad \text{RHS} = 2^{1}(1!)^{2} = 2\cdot 1 = 2$

Since LHS ≥ RHS, the base case holds.

Step 3 — Inductive hypothesis

Assume P(k) is true for some positive integer k:

$(2k)! \ge 2^{k}(k!)^{2}$

Step 4 — Inductive step

We want to reach P(k+1):

$[2(k+1)]! \ge 2^{k+1}\big[(k+1)!\big]^{2}$

Notice that [2(k+1)]! = (2k+2)! = (2k+2)(2k+1)(2k)!. So multiply both sides of P(k) by (2k+1)(2k+2) — both positive, so the inequality is safe:

$(2k+2)(2k+1)(2k)! \ge 2^{k}(k!)^{2}(2k+1)(2k+2)$

The left side is now exactly (2k+2)!:

$(2k+2)! \ge 2^{k}(k!)^{2}(2k+1)(2k+2)$

Write 2k+2 = 2(k+1) and split (k!)² into (k!)(k!):

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

Group k!(k+1) = (k+1)! on one factor:

$(2k+2)! \ge 2^{k+1}(k!)(2k+1)(k+1)!$

The right side is the smaller side, so we're allowed to replace a term with something smaller. Since 2k+1 > k+1, replace 2k+1 with k+1:

$(2k+2)! \ge 2^{k+1}(k!)(k+1)(k+1)! = 2^{k+1}(k+1)!\,(k+1)!$

(using k!(k+1) = (k+1)! again). Therefore:

$[2(k+1)]! \ge 2^{k+1}\big[(k+1)!\big]^{2}$

which is exactly P(k+1).

Step 5 — Conclusion

Since P(1) is true and P(k+1) is true whenever P(k) is true for some positive integer k, by the principle of mathematical induction P(n) is true for all positive integers n.

Example 2 — induction with binomial coefficients

Prove by induction that C(2n, n) < 2^(2n−2) for all positive integers n ≥ 5.

Step 1 — Propositional function

$P(n): \binom{2n}{n} < 2^{\,2n-2}, \quad n \in \mathbb{Z}^{+},\ n \ge 5$

Step 2 — Base case (n = 5)

$\text{LHS} = \binom{2\cdot 5}{5} = \binom{10}{5} = 252 \qquad \text{RHS} = 2^{\,2\cdot 5 - 2} = 2^{8} = 256$

Since 252 < 256, we have LHS < RHS and the base case holds.

Step 3 — Inductive hypothesis

Assume for some positive integer k ≥ 5:

$\binom{2k}{k} < 2^{\,2k-2}$

Step 4 — Inductive step

The goal, P(k+1), is:

$\binom{2(k+1)}{k+1} < 2^{\,2(k+1)-2} = 2^{\,2k}$

Convert to factorials using the formula

$\binom{p}{q} = \frac{p!}{q!\,(p-q)!}$

The hypothesis becomes

$\binom{2k}{k} = \frac{(2k)!}{k!\,k!} < 2^{\,2k-2}$

and the goal becomes

$\frac{(2k+2)!}{(k+1)!\,(k+1)!} < 2^{\,2k}$

Starting from P(k), we build (2k+2)! on top and (k+1)!(k+1)! on the bottom. Since (2k+2)! = (2k+2)(2k+1)(2k)!, multiply both sides by (2k+1)(2k+2) / [(k+1)(k+1)] — positive, so safe:

$\frac{(2k+2)(2k+1)(2k)!}{(k+1)(k+1)\,k!\,k!} < 2^{\,2k-2}\cdot \frac{(2k+1)(2k+2)}{(k+1)(k+1)}$

The left side is now (2k+2)! / [(k+1)!(k+1)!]. On the right, write 2k+2 = 2(k+1) and cancel one (k+1):

$\frac{(2k+2)!}{(k+1)!\,(k+1)!} < 2^{\,2k-1}\cdot \frac{2k+1}{k+1}$

This is the larger side, so we may replace a term with something larger. Is (2k+1)/(k+1) < 2? Yes — as a function of k it has a horizontal asymptote at 2 and approaches it from below, so (2k+1)/(k+1) < 2 for every valid k. Replacing it with 2:

$\frac{(2k+2)!}{(k+1)!\,(k+1)!} < 2^{\,2k-1}\cdot 2 = 2^{\,2k}$

That is C(2(k+1), k+1) < 2^(2k) = 2^(2(k+1)−2), which is exactly P(k+1).

Step 5 — Conclusion

Since P(5) is true and P(k+1) is true whenever P(k) is true for some positive integer k, by the principle of mathematical induction P(n) is true for all positive integers n ≥ 5.

Key takeaways

• It's always the same five steps — lock in steps 1–3 for the easy ~30% of the marks.
• For inequalities, turn P(k) into P(k+1) using only safe moves: make the bigger side bigger, the smaller side smaller, or multiply through by a positive number.
• Factorials grow by multiplying consecutive integers, (m+1)! = (m+1)·m! — that's how you "build" the factorial you need on each side.

Practise this until it's automatic

Watching a proof is not the same as being able to produce one under exam pressure. ▶ Watch the full video walkthrough, then download the free induction-proofs exercise list to practise these step by step. When you're ready to test yourself under real conditions, the graded mock exams will tell you whether you're genuinely sitting at a 7.