McIntyre MathsMathematics Extension 2
Extension 2 › Proof › Lesson 8

Lesson 8 · Further induction II: inequalities

Mathematics Extension 2 · Proof · Outcome ME2-12-01 · Term 4 · Week 4
Learning intentionTo prove inequalities by mathematical induction.
Success criteria · I can…
  • write the inductive step as a chain LHS(k+1)>⋯≥RHS(k+1)\text{LHS}(k+1) > \dots \ge \text{RHS}(k+1)
  • prove the “gap” part separately, for example 2k2≥(k+1)22k^2\ge(k+1)^2 for k≥3k\ge3
  • choose the correct first value of nn by testing
  • use a given or earlier result inside the inductive step

Lesson flow

LaunchWarm-upSlide 2Key ideasInduction with inequalitiesSlide 3ExamplesExample 2 · Factorials and powersSlide 4HSC-styleHSC practice · A lemma firstSlide 5HSC-styleHSC practice · Powers and factorialsSlide 6HSC-styleHSC practice · A binomial coefficientSlide 7HSC-styleHSC practice · A sumSlide 8ExamplesExample 3 · A sum with square rootsSlide 9ThinkSpot the flaw · An induction inequalitySlide 10Exit ticketExit ticketSlide 11

Warm-up

Slide 2
(a) For which positive integers nn is n2>2n+1n^2>2n+1?
Show answerHide answer
Answer
n≥3n\ge3.
Why
n2>2n+1  ⟺  (n−1)2>2n^2>2n+1\iff (n-1)^2>2, which needs n−1≥2n-1\ge2 for a positive integer, so n≥3n\ge3. Check: n=2n=2 gives 4>54>5, false; n=3n=3 gives 9>79>7, true.
(b) Show that 2k2−(k+1)2=(k−1)2−22k^2-(k+1)^2=(k-1)^2-2.
Show answerHide answer
Answer
Both sides equal k2−2k−1k^2-2k-1.
Why
LHS: 2k2−(k2+2k+1)=k2−2k−12k^2-(k^2+2k+1)=k^2-2k-1. RHS: (k2−2k+1)−2=k2−2k−1(k^2-2k+1)-2=k^2-2k-1.
(c) If A>BA>B and B≥CB\ge C, what can you conclude?
Show answerHide answer
Answer
A>CA>C.
Why
A strict inequality followed by a non-strict one still gives a strict result. This is the idea behind the chain layout used in this lesson.
(d) Test 2n>n22^n>n^2 for n=1,2,3,4,5,6n=1,2,3,4,5,6.
Show answerHide answer
Answer
True for n=1n=1, false for n=2,3,4n=2,3,4, true for n=5,6n=5,6. So claim n≥5n\ge5.
Why
2>12>1 yes; 4=44=4 no; 8<98<9 no; 16=1616=16 no; 32>2532>25 yes; 64>3664>36 yes. The claim holds from n=5n=5 on, so the first value of nn must be chosen with care.

Induction with inequalities

Slide 3

The set-out is the same four steps as before, but the inductive step is a chain of inequalities and each link must be justified.

Method
The inductive step for an inequality
  1. Write the target: need LHS(k+1)>RHS(k+1)\text{LHS}(k+1)>\text{RHS}(k+1).
  2. Write LHS(k+1)\text{LHS}(k+1) using LHS(k)\text{LHS}(k), and apply the assumption.
  3. Prove separately that (expression in kk) ≥RHS(k+1)\ge\text{RHS}(k+1), usually a difference ≥0\ge0, using k≥k\ge the first value.
  4. Chain: LHS(k+1)>⋯≥RHS(k+1)\text{LHS}(k+1)>\dots\ge\text{RHS}(k+1). ∴P(k+1)\therefore P(k+1) is true whenever P(k)P(k) is true.
Watch out

Never start from the result you want and work backwards unless every step is reversible. Start from LHS(k+1)\text{LHS}(k+1) and build the chain towards RHS(k+1)\text{RHS}(k+1). Also check small values: the first value of nn is not always 1.

Example 1

Prove by induction that 2n>n22^n>n^2 for all integers n≥5n\ge5.
Show answerHide answer
Answer
Let P(n)P(n): 2n>n22^n>n^2.
Step 1. P(5)P(5): 25=32>25=522^5=32>25=5^2. ∴P(5)\therefore P(5) is true.
Step 2. Assume 2k>k22^k>k^2 for some integer k≥5k\ge5.
Step 3. Need 2k+1>(k+1)22^{k+1}>(k+1)^2. 2k+1=2⋅2k>2k2≥(k+1)2.2^{k+1}=2\cdot2^k>2k^2\ge(k+1)^2. The last step holds because 2k2−(k+1)2=(k−1)2−2≥16−2>02k^2-(k+1)^2=(k-1)^2-2\ge16-2>0 for k≥5k\ge5. ∴P(k+1)\therefore P(k+1) is true whenever P(k)P(k) is true.
Step 4. By mathematical induction, 2n>n22^n>n^2 for all integers n≥5n\ge5.
Why
The assumption gives the first link. The “gap” 2k2≥(k+1)22k^2\ge(k+1)^2 is proved separately (Warm-up (b)), and it is where k≥5k\ge5 is used. Without a large enough kk the gap fails, for example at k=2k=2.

Example 2 · Factorials and powers

Slide 4

Set out each proof with all four steps.

(a) Prove by induction that n!>2nn!>2^n for all integers n≥4n\ge4.
Show answerHide answer
Answer
Step 1. n=4n=4: 4!=24>16=244!=24>16=2^4.
Step 2. Assume k!>2kk!>2^k for some integer k≥4k\ge4.
Step 3. Need (k+1)!>2k+1(k+1)!>2^{k+1}. (k+1)!=(k+1) k!>(k+1)2k≥2⋅2k=2k+1,(k+1)!=(k+1)\,k!>(k+1)2^k\ge2\cdot2^k=2^{k+1}, since k+1≥2k+1\ge2.
Step 4. True for n=4n=4 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥4n\ge4 by induction.
Why
Write (k+1)!=(k+1)k!(k+1)!=(k+1)k! so the assumption can be used. The factor (k+1)(k+1) is at least 2, which turns 2k2^k into 2k+12^{k+1}. Check: n=3n=3 gives 6>86>8, false, which is why the base case is n=4n=4.
(b) Prove by induction that 3n≥1+2n3^n\ge1+2n for all integers n≥1n\ge1.
Show answerHide answer
Answer
Step 1. n=1n=1: 31=3≥1+2=33^1=3\ge1+2=3.
Step 2. Assume 3k≥1+2k3^k\ge1+2k for some integer k≥1k\ge1.
Step 3. Need 3k+1≥1+2(k+1)=2k+33^{k+1}\ge1+2(k+1)=2k+3. 3k+1=3⋅3k≥3(1+2k)=3+6k≥3+2k=1+2(k+1),3^{k+1}=3\cdot3^k\ge3(1+2k)=3+6k\ge3+2k=1+2(k+1), since 4k≥04k\ge0.
Step 4. True for n=1n=1 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥1n\ge1 by induction.
Why
Multiply the assumption by 3 (positive, so the inequality direction is preserved). The gap is 3+6k−(3+2k)=4k≥03+6k-(3+2k)=4k\ge0. The base case gives equality, so the inequality is ≥\ge rather than >>.

HSC practice · A lemma first

Slide 5

Wording adapted from the paper.

2023 HSC Q13(b)

(i) Show that k2−2k−3≥0k^2-2k-3\ge0 for all integers k≥3k\ge3.
Show answerHide answer
Answer
k2−2k−3=(k−3)(k+1)≥0k^2-2k-3=(k-3)(k+1)\ge0 for k≥3k\ge3.
Why
For k≥3k\ge3 both factors are non-negative: k−3≥0k-3\ge0 and k+1>0k+1>0.
(ii) Hence prove by induction that 2n≥n2−22^n\ge n^2-2 for all integers n≥3n\ge3.
Show answerHide answer
Answer
Step 1. P(3)P(3): 8≥9−2=78\ge9-2=7. True.
Step 2. Assume 2k≥k2−22^k\ge k^2-2 for some integer k≥3k\ge3.
Step 3. Then 2k+1=2⋅2k≥2k2−42^{k+1}=2\cdot2^k\ge2k^2-4. Need 2k+1≥(k+1)2−2=k2+2k−12^{k+1}\ge(k+1)^2-2=k^2+2k-1. Now 2k2−4−(k2+2k−1)=k2−2k−3≥02k^2-4-(k^2+2k-1)=k^2-2k-3\ge0 by (i), so 2k+1≥2k2−4≥(k+1)2−22^{k+1}\ge2k^2-4\ge(k+1)^2-2.
Step 4. True for n=3n=3 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥3n\ge3 by induction.
Why
Part (i) is exactly the gap between 2k2−42k^2-4 and the target (k+1)2−2(k+1)^2-2. Look for the given result inside the inductive step.

HSC practice · Powers and factorials

Slide 6

Wording adapted from the papers.

Question A

2021 HSC Q12(d)Prove by induction that 2n<n!2^n<\sqrt{n!} for all integers n≥9n\ge9.
Show answerHide answer
Answer
Step 1. P(9)P(9): 29=5122^9=512 and 9!=362 880≈602.4\sqrt{9!}=\sqrt{362\,880}\approx602.4, so 512<602.4512<602.4. True.
Step 2. Assume 2k<k!2^k<\sqrt{k!} for some integer k≥9k\ge9.
Step 3. 2k+1=2⋅2k<2k!<k+1 k!=(k+1)!,2^{k+1}=2\cdot2^k<2\sqrt{k!}<\sqrt{k+1}\,\sqrt{k!}=\sqrt{(k+1)!}, since k+1≥10>2\sqrt{k+1}\ge\sqrt{10}>2.
Step 4. True for n=9n=9 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥9n\ge9 by induction.
Why
Split (k+1)!=k+1k!\sqrt{(k+1)!}=\sqrt{k+1}\sqrt{k!} so the assumption can be used, then compare the factor k+1\sqrt{k+1} with 2. This is where k≥9k\ge9 is needed. For the base case, 6022=362 404<9!=362 880602^2=362\,404<9!=362\,880, so 9!>602>512\sqrt{9!}>602>512.

Question B

2021 HSC Q15(d)Prove by induction that 2n+3n<5n2^n+3^n<5^n for all integers n≥2n\ge2.
Show answerHide answer
Answer
Step 1. P(2)P(2): 4+9=13<254+9=13<25. True.
Step 2. Assume 2k+3k<5k2^k+3^k<5^k for some integer k≥2k\ge2.
Step 3. 2k+1+3k+1=2⋅2k+3⋅3k<3(2k+3k)<3⋅5k<5k+1.2^{k+1}+3^{k+1}=2\cdot2^k+3\cdot3^k<3\left(2^k+3^k\right)<3\cdot5^k<5^{k+1}.
Step 4. True for n=2n=2 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥2n\ge2 by induction.
Why
Replace both multipliers by the larger one, 3, so the bracket 2k+3k2^k+3^k from the assumption appears. Then 3⋅5k<5⋅5k3\cdot5^k<5\cdot5^k. A non-induction proof expands (2+3)n(2+3)^n by the binomial theorem (Lesson 3).

HSC practice · A binomial coefficient

Slide 7

Wording adapted from the paper.

2024 HSC Q14(b)Prove by induction that (2nn)<22n−2\dbinom{2n}{n}<2^{2n-2} for all integers n≥5n\ge5.
Hint: (2k+2k+1)=2(2k+1)k+1(2kk)\dbinom{2k+2}{k+1}=\dfrac{2(2k+1)}{k+1}\dbinom{2k}{k}.
Show answerHide answer
Answer
Step 1. P(5)P(5): (105)=252<28=256\binom{10}{5}=252<2^8=256. True.
Step 2. Assume (2kk)<22k−2\binom{2k}{k}<2^{2k-2} for some integer k≥5k\ge5.
Step 3. (2k+2k+1)=2(2k+1)k+1(2kk)<4(2kk)<4⋅22k−2=22(k+1)−2,\binom{2k+2}{k+1}=\frac{2(2k+1)}{k+1}\binom{2k}{k}<4\binom{2k}{k}<4\cdot2^{2k-2}=2^{2(k+1)-2}, since 2k+1k+1<2\dfrac{2k+1}{k+1}<2.
Step 4. True for n=5n=5 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥5n\ge5 by induction.
Why
The hint comes from (2k+2k+1)=(2k+2)(2k+1)(k+1)(k+1)(2kk)\binom{2k+2}{k+1}=\dfrac{(2k+2)(2k+1)}{(k+1)(k+1)}\binom{2k}{k} using the factorial formula; prove it first if it is not given. The ratio 2(2k+1)k+1=4−2k+1\dfrac{2(2k+1)}{k+1}=4-\dfrac2{k+1} is less than 4, and (2kk)>0\binom{2k}{k}>0 keeps the inequality direction.

HSC practice · A sum

Slide 8

Wording adapted from the paper.

2020 HSC Q14(c)Prove by induction that 122+132+⋯+1n2<n−1n\frac1{2^2}+\frac1{3^2}+\dots+\frac1{n^2}<\frac{n-1}n for all integers n≥2n\ge2.
Show answerHide answer
Answer
Step 1. P(2)P(2): 14<12\dfrac14<\dfrac12. True.
Step 2. Assume ∑r=2k1r2<k−1k\displaystyle\sum_{r=2}^{k}\frac1{r^2}<\frac{k-1}k for some integer k≥2k\ge2.
Step 3. ∑r=2k+11r2<k−1k+1(k+1)2\displaystyle\sum_{r=2}^{k+1}\frac1{r^2}<\frac{k-1}k+\frac1{(k+1)^2}. Need this to be at most kk+1\dfrac k{k+1}. Now kk+1−k−1k=1k(k+1)>1(k+1)2,\frac k{k+1}-\frac{k-1}k=\frac1{k(k+1)}>\frac1{(k+1)^2}, so k−1k+1(k+1)2<kk+1\dfrac{k-1}k+\dfrac1{(k+1)^2}<\dfrac k{k+1}.
Step 4. True for n=2n=2 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥2n\ge2 by induction.
Why
Add the next term to the assumption, then compare with the target by looking at the difference. Since k(k+1)<(k+1)2k(k+1)<(k+1)^2, we have 1k(k+1)>1(k+1)2\frac1{k(k+1)}>\frac1{(k+1)^2}. Non-induction alternative: 1r2<1r(r−1)=1r−1−1r\frac1{r^2}<\frac1{r(r-1)}=\frac1{r-1}-\frac1r, which telescopes.

Example 3 · A sum with square roots

Slide 9
Prove by induction that 11+12+⋯+1n≥n\frac1{\sqrt1}+\frac1{\sqrt2}+\dots+\frac1{\sqrt n}\ge\sqrt n for all integers n≥1n\ge1.
Show answerHide answer
Answer
Step 1. n=1n=1: LHS =1≥1=1=1\ge1=\sqrt1.
Step 2. Assume Sk≥kS_k\ge\sqrt k for some integer k≥1k\ge1.
Step 3. Need Sk+1≥k+1S_{k+1}\ge\sqrt{k+1}. Sk+1=Sk+1k+1≥k+1k+1.S_{k+1}=S_k+\frac1{\sqrt{k+1}}\ge\sqrt k+\frac1{\sqrt{k+1}}. Now k+1k+1≥k+1\sqrt k+\dfrac1{\sqrt{k+1}}\ge\sqrt{k+1} because, multiplying by k+1>0\sqrt{k+1}>0, this is equivalent to k(k+1)+1≥k+1\sqrt{k(k+1)}+1\ge k+1, that is k2+k≥k\sqrt{k^2+k}\ge k, which is true.
Step 4. True for n=1n=1 and true for n=k⇒n=k+1n=k\Rightarrow n=k+1, so true for all integers n≥1n\ge1 by induction.
Why
The gap inequality is a small separate problem. It is safe to multiply by k+1\sqrt{k+1} because it is positive, and every step is reversible, so the gap inequality really does follow from the true statement k2+k≥k\sqrt{k^2+k}\ge k (as k2+k≥k2k^2+k\ge k^2).

Spot the flaw · An induction inequality

Slide 10

A student wrote this. Find the flaw, explain why it matters, then write a correct version.

Claim

2n>n22^n>n^2 for all integers n≥1n\ge1.

  1. n=1n=1: 2>12>1, true.
  2. Assume 2k>k22^k>k^2. Then 2k+1=2⋅2k>2k22^{k+1}=2\cdot2^k>2k^2.
  3. Also 2k2≥(k+1)22k^2\ge(k+1)^2, so 2k+1>(k+1)22^{k+1}>(k+1)^2. Hence true for all n≥1n\ge1.
Task Find the flaw, explain why it matters, then write a correct version.
Show answerHide answer
Answer
Flaw: line 3 is not justified. 2k2−(k+1)2=(k−1)2−22k^2-(k+1)^2=(k-1)^2-2, which is ≥0\ge0 only for k≥3k\ge3 (k=1k=1: 2<42<4; k=2k=2: 8<98<9). The claim is also false for n=2,3,4n=2,3,4 (4=44=4, 8<98<9, 16=1616=16).
Correct version: Example 1. Start at n=5n=5 (32>2532>25) and prove the gap step for k≥5k\ge5.
Why
Prove the “gap” inequality for every kk the step needs, and test small cases before choosing the first value.

Exit ticket

Slide 11

For the inequality 4n>3n+104^n>3n+10:

(a) Find the smallest positive integer nn for which it is true (and so the correct base case).
Show answerHide answer
Answer
n=3n=3.
Why
n=1n=1: 4>134>13 false. n=2n=2: 16>1616>16 false. n=3n=3: 64>1964>19 true.
(b) Assume 4k>3k+104^k>3k+10 for some integer k≥3k\ge3. Write only the inductive step (Step 3) as a chain of inequalities.
Show answerHide answer
Answer
4k+1=4⋅4k>4(3k+10)=12k+40>3k+13=3(k+1)+10.4^{k+1}=4\cdot4^k>4(3k+10)=12k+40>3k+13=3(k+1)+10.
Why
The gap is 12k+40−(3k+13)=9k+27>012k+40-(3k+13)=9k+27>0. Each link is justified: the first by the assumption, the second because 9k+27>09k+27>0.