Ultimate Guide to Further Proof by Mathematical Induction

Introduction

You were introduced to Mathematical Induction in Extension 1, using it to prove simple divisibility and series sums. In HSC Mathematics Extension 2, the training wheels come off. Further Proof by Mathematical Induction pushes the domino-effect logic of induction to its limits, requiring you to prove complex inequalities, recursive sequence formulas, calculus derivatives, and trigonometric identities.

Executive Summary

This guide covers the advanced applications of Mathematical Induction:

• The Induction Structure: A quick recap of Base Case, Assumption, and Step.
• Induction for Inequalities: Navigating greater-than/less-than signs carefully during the inductive step.
• Recursive Formulas: Proving general formulas for sequences defined by previous terms.
• Calculus & Geometry: Proving general $n$th derivative rules and polygon angle sums.

What is this about?

Mathematical Induction is like setting up an infinite line of dominoes.

1. You prove the first domino falls over (The Base Case, usually $n=1$).
2. You assume that a random domino somewhere down the line falls over (Assume true for $n=k$).
3. You prove that IF the $k$th domino falls, it definitively knocks over the next one (Prove true for $n=k+1$). Conclusion: The whole infinite line falls down.

In Extension 2, the "dominoes" are much heavier. Instead of just proving $LHS = RHS$, you might need to prove that $LHS > RHS$, which requires a combination of induction and the algebraic inequality techniques we learned in the previous guides.

Main Content

1. The Core Structure

Every induction proof MUST contain these explicit steps to get full marks:

1. Show true for $n = 1$ (or the lowest base value). State clearly: "LHS = ... RHS = ... LHS = RHS, therefore true for $n=1$."
2. Assume true for $n = k$ (where $k$ is a positive integer). Write out the equation/inequality with $k$.
3. Prove true for $n = k + 1$. Write down your "Required to Prove" (RTP) goal.
4. The Proof: Start with the LHS of your $k+1$ statement, and mathematically inject your assumption from Step 2 into the algebra.
5. Conclusion: State the standard induction conclusion paragraph.

2. Proving Inequalities

Induction with inequalities requires intense algebraic care. When trying to prove $LHS > RHS$ for $n=k+1$:

1. Start with the assumption: $A > B$ (for $n=k$).
2. Algebraically manipulate BOTH sides to make the left side look like the LHS of your $k+1$ goal.
3. You will now have $LHS_{k+1} > \text{Something}$.
4. Use the techniques from Proof of Inequalities (Part 1) to prove that $\text{Something} > RHS_{k+1}$.
5. By transitivity, if $LHS > \text{Something}$, and $\text{Something} > RHS$, then $LHS > RHS$.

3. Recursive Formulas (Recurrence Relations)

A recursive formula defines the next term in a sequence using the previous term. For example, the Fibonacci sequence: $T_{n} = T_{n-1} + T_{n-2}$. Or a first-order recurrence: $x_{n+1} = 2x_n + 3$, with $x_1 = 1$.

Induction is used to prove that a recursive sequence matches a "closed-form" general formula (e.g. $x_n = 2^{n+1} - 3$). In the $k+1$ step, your LHS will be $x_{k+1}$. You simply substitute the recursive definition (e.g. $2x_k + 3$) and then substitute your $n=k$ assumption for $x_k$ to arrive at the RHS.

4. Calculus and Geometry

Calculus: You can use induction to prove derivative rules like the product rule generalized for $n$ functions, or the formula for the $n$th derivative of $x^n$. The $k+1$ step usually involves differentiating the $k$th assumption using standard Extension 1 derivative rules.

Geometry: Induction can prove facts about $n$-sided polygons. The base case is usually a triangle ($n=3$). To prove the $k+1$ step (a $k+1$ sided polygon), you draw a diagonal to split it into a $k$-sided polygon (your assumption) and a triangle.

Simple Worked Example

Question: A sequence is defined recursively by $u_1 = 2$ and $u_{n+1} = 3u_n - 2$ for $n \ge 1$. Prove by mathematical induction that the general formula is $u_n = 3^{n-1} + 1$ for all integers $n \ge 1$.

Solution: Step 1: Base Case ($n=1$) LHS: The definition says $u_1 = 2$. RHS: Using the formula $3^{1-1} + 1 = 3^0 + 1 = 1 + 1 = 2$. LHS = RHS. The statement is true for $n=1$.

Step 2: Assumption ($n=k$) Assume the formula is true for some positive integer $n=k$: $u_k = 3^{k-1} + 1$

Step 3: Prove for $n=k+1$ Required to Prove (RTP): $u_{k+1} = 3^{(k+1)-1} + 1 = 3^k + 1$.

Step 4: The Proof Start with the recursive definition provided in the question: $u_{k+1} = 3u_k - 2$

Substitute our assumption ($u_k = 3^{k-1} + 1$) into the equation: $u_{k+1} = 3(3^{k-1} + 1) - 2$

Expand the bracket: $u_{k+1} = (3 \times 3^{k-1}) + 3 - 2$

Use index laws ($3^1 \times 3^{k-1} = 3^k$): $u_{k+1} = 3^k + 1$

This matches our RTP!

Step 5: Conclusion Since the statement is true for $n=1$, and if it is true for $n=k$ it is also true for $n=k+1$, it follows by the principle of mathematical induction that the statement is true for all integers $n \ge 1$.

mini-FAQ page

Q: Why do some inequality inductions seem to have a "missing link" step? A: When proving transitivity ($A > B > C$), finding the middle term $B$ is the hardest part. You must creatively add/subtract terms (using your algebraic inequality skills) to bridge the gap between your $k$ assumption and your $k+1$ goal.

Q: Does the base case always have to be $n=1$? A: No! The base case is just the lowest valid number for the theorem. If the question asks you to prove something for all integers $n \ge 4$, your base case MUST be $n=4$. Proving $n=1$ in that scenario will score zero marks.

Common mistakes to avoid

• Forgetting to write the conclusion: Yes, you will lose a mark if you do not write the concluding paragraph. It demonstrates that you understand the logical structure of induction, rather than just doing algebra.
• Faking the algebra: Markers know exactly where the tricky algebra is in the $k+1$ step. If you just write down the assumption, skip three lines, and write down the final answer, you will not receive marks for the proof. You must show the mechanism.

Practice on Vu's Maths Hub

Extension 2 Induction requires flawless algebra and logical stamina.

• Practice the hardest recursive and inequality induction proofs in the HSC Proof Booklet.
• Test your integration limits with calculus induction in the HSC Integration Booklet.

Further Readings

• This concludes our series on the Nature of Proof! Ready for the next challenge? Dive into our 3D Vector series (coming soon).
• Explore more HSC math resources and full worked solutions at Vu's Maths Hub.

Connect with me

Want to master Mathematical Proof and guarantee top marks in HSC Mathematics Extension 2? Visit Vu's Maths Hub for in-depth booklets, rigorous worked solutions, and expert advice to help you ace your exams!