🌟 Further Pure Mathematics 1 (9231) Study Notes 🌟

Chapter 1.7: Proof by Induction

Welcome to one of the most powerful and satisfying topics in pure mathematics: Proof by Induction!

Don't worry if this seems tricky at first—it’s just a clever method for proving that a statement is true for an infinite number of cases, typically all positive integers \(n\). Think of it as setting up a perfect line of dominoes!

What is Mathematical Induction? (The Domino Analogy)

Imagine you have an infinite line of dominoes, numbered \(n=1, n=2, n=3,\) and so on. To prove that all the dominoes will fall, you only need to demonstrate two things:

  1. The Starting Push (Base Case): You knock over the first domino (the \(n=1\) case).
  2. The Chain Reaction (Inductive Step): You prove that if any domino (say, the \(k\)th domino) falls, it will definitely knock over the very next one (the \((k+1)\)th domino).

If you establish these two facts, then every single domino, all the way to infinity, must fall! This is the essence of mathematical induction.

Key Takeaway

Proof by induction allows us to prove a formula or statement is true for all integers greater than or equal to a starting value (usually 1).

The Four Essential Steps of Inductive Proof

Every successful induction proof must follow these four mandatory steps. Missing any step will result in an incomplete proof!

Step 1: The Base Case (\(n=n_{min}\))

You must show that the statement \(P(n)\) is true for the smallest possible integer, \(n_{min}\).

  • Usually, \(n_{min} = 1\), but check the question carefully (sometimes it starts at \(n=0\) or \(n=2\)).
  • Substitute \(n_{min}\) into both sides of the equation (LHS and RHS) and show they are equal, or demonstrate the property holds.

Step 2: The Inductive Hypothesis (Assumption)

Assume the statement \(P(n)\) is true for an arbitrary positive integer \(k\).

  • Write down the hypothesis clearly: Assume \(P(k)\) is true.
  • Example: If proving \(\sum_{r=1}^n r = \frac{1}{2}n(n+1)\), you write:
    Assume true for \(n=k\): \(\sum_{r=1}^k r = \frac{1}{2}k(k+1)\).

Step 3: The Inductive Step (The Proof for \(n=k+1\))

This is the core of the proof. You must prove that if \(P(k)\) is true (your assumption from Step 2), then the statement \(P(k+1)\) must also be true.

  • Start with the expression for \(P(k+1)\).
  • Crucial Technique: Manipulate the expression for \(P(k+1)\) so that you can substitute your assumed statement \(P(k)\) into it.
  • Show, using algebraic manipulation, that the resulting expression matches the formula \(P(n)\) with \(n\) replaced by \((k+1)\).

🚨 Common Mistake Alert! 🚨

Do NOT start by writing out the statement for \(n=k+1\) and trying to prove it by working backwards or assuming it is true. You MUST start from one side (usually LHS of \(P(k+1)\)) and arrive at the other side (RHS of \(P(k+1)\)).

Step 4: The Conclusion (Formal Write-up)

The final step is formalizing the logical chain. This must be present in your answer.

  • State that since \(P(n)\) is true for \(n=n_{min}\) (Step 1), and since the truth of \(P(k)\) implies the truth of \(P(k+1)\) (Step 3), the statement \(P(n)\) is true for all integers \(n \ge n_{min}\) by the principle of mathematical induction.
Key Takeaway

Think of Step 2 (Assumption) as your key tool. The goal of Step 3 is simply to create an opportunity to use that tool.

Applying Induction to Different Problem Types

The syllabus requires induction to prove results relating to summation, recurrence relations, divisibility, matrices, and derivatives. The structure remains the same, but Step 3 requires specific manipulation techniques for each type.

1. Proofs Involving Summation of Series

This is the most common type, often using standard results like \(\sum r^3\).

Example: Prove that \(\sum_{r=1}^n r^3 = \frac{1}{4}n^2(n+1)^2\).

  • Assumption (P(k)): \(\sum_{r=1}^k r^3 = \frac{1}{4}k^2(k+1)^2\).
  • Inductive Step (P(k+1)):

    We start with the sum up to \((k+1)\) terms:
    \( \sum_{r=1}^{k+1} r^3 = \left( \sum_{r=1}^k r^3 \right) + (k+1)^3 \)

    Now, substitute the assumption \(P(k)\):
    \( = \frac{1}{4}k^2(k+1)^2 + (k+1)^3 \)

    Factor out the common term \((k+1)^2\):
    \( = (k+1)^2 \left[ \frac{1}{4}k^2 + (k+1) \right] \)

    Simplify the bracket:
    \( = (k+1)^2 \left[ \frac{k^2 + 4k + 4}{4} \right] = (k+1)^2 \left[ \frac{(k+2)^2}{4} \right] \)

    Rearrange to match the RHS of the original formula with \(n=(k+1)\):
    \( = \frac{1}{4}(k+1)^2 (k+2)^2 \)

    Since this matches \(P(k+1)\), the step is complete.

2. Proofs Involving Divisibility

These proofs require showing that \(P(k+1)\) can be written as the sum of a multiple of \(P(k)\) and a term that is also divisible by the required number.

Example: Prove that \(3^{2n} + 2 \times 5^n - 3\) is divisible by 8 for all positive integers \(n\).

  • Assumption (P(k)): Assume \(3^{2k} + 2 \times 5^k - 3 = 8M\), where \(M\) is an integer.
  • Inductive Step (P(k+1)): We need to examine \(3^{2(k+1)} + 2 \times 5^{k+1} - 3\).

    We rewrite the expression using index laws to extract the assumed term \(3^{2k}\):
    \( P(k+1) = 3^{2k} \times 3^2 + 2 \times 5^k \times 5 - 3 \)
    \( P(k+1) = 9 \times 3^{2k} + 10 \times 5^k - 3 \)

    From the assumption, we know \(3^{2k} = 8M - 2 \times 5^k + 3\). Substitute this into \(P(k+1)\):
    \( P(k+1) = 9(8M - 2 \times 5^k + 3) + 10 \times 5^k - 3 \)
    \( P(k+1) = 72M - 18 \times 5^k + 27 + 10 \times 5^k - 3 \)
    \( P(k+1) = 72M - 8 \times 5^k + 24 \)

    Factor out 8 from the result:
    \( P(k+1) = 8(9M - 5^k + 3) \)

    Since \(9M - 5^k + 3\) is an integer, \(P(k+1)\) is divisible by 8.


3. Proofs Involving Recurrence Relations

Recurrence relations define a sequence based on previous terms (e.g., \(u_{n+1} = f(u_n)\)). You must prove that the sequence can also be defined by a general formula \(u_n\).

Example: A sequence is defined by \(u_1 = 1\) and \(u_{n+1} = 3u_n - 1\). Prove that \(u_n = \frac{1}{2}(1 + 3^{n-1})\).

  • Assumption (P(k)): Assume \(u_k = \frac{1}{2}(1 + 3^{k-1})\).
  • Inductive Step (P(k+1)):

    Use the definition of the recurrence relation for \(u_{k+1}\):
    \( u_{k+1} = 3u_k - 1 \)

    Substitute the assumption \(u_k\):
    \( u_{k+1} = 3 \left( \frac{1}{2}(1 + 3^{k-1}) \right) - 1 \)

    Simplify:
    \( u_{k+1} = \frac{3}{2} + \frac{3 \times 3^{k-1}}{2} - 1 \)
    \( u_{k+1} = \frac{1}{2} + \frac{3^k}{2} \)
    \( u_{k+1} = \frac{1}{2}(1 + 3^k) \)

    This matches the target formula \(\frac{1}{2}(1 + 3^{n-1})\) when \(n\) is replaced by \((k+1)\). (Since \(3^{(k+1)-1} = 3^k\)).

4. Proofs Involving Matrices

Induction is often used to find the \(n\)th power of a matrix, \(M^n\).

Example: Given \(M = \begin{pmatrix} 4 & -1 \\ 6 & 1 \end{pmatrix}\), prove that \(M^n = \frac{1}{3} \begin{pmatrix} 3 \times 2^n - 2 & 1 - 2^n \\ 3 \times 2^{n+1} - 6 & 3 - 2^{n+1} \end{pmatrix}\) for integers \(n \ge 1\).

  • Assumption (P(k)): Assume the formula holds for \(M^k\).
  • Inductive Step (P(k+1)):

    We use the property \(M^{k+1} = M^k M\). (Note: You must multiply the assumed \(M^k\) by the original matrix \(M\)).

    \( M^{k+1} = \frac{1}{3} \begin{pmatrix} 3 \times 2^k - 2 & 1 - 2^k \\ 3 \times 2^{k+1} - 6 & 3 - 2^{k+1} \end{pmatrix} \begin{pmatrix} 4 & -1 \\ 6 & 1 \end{pmatrix} \)

    You must perform the matrix multiplication and simplify the four components (this is typically messy but algebraic). The goal is to show the result equals:
    \( \frac{1}{3} \begin{pmatrix} 3 \times 2^{k+1} - 2 & 1 - 2^{k+1} \\ 3 \times 2^{(k+1)+1} - 6 & 3 - 2^{(k+1)+1} \end{pmatrix} \)

5. Proofs Involving Derivatives (\(n\)th Derivative)

Here, \(P(n)\) is the expression for the \(n\)th derivative, \(\frac{d^n y}{dx^n}\).

Example: Find and prove the \(n\)th derivative of \(y = xe^x\).

  • Conjecture (Pre-Induction): First, find the pattern (see Section 4).
    \( \frac{dy}{dx} = 1e^x + xe^x = (x+1)e^x \) (n=1)
    \( \frac{d^2y}{dx^2} = 1e^x + (x+1)e^x = (x+2)e^x \) (n=2)
    \( \frac{d^3y}{dx^3} = 1e^x + (x+2)e^x = (x+3)e^x \) (n=3)

    The conjecture is: \( \frac{d^n y}{dx^n} = (x+n)e^x \).

  • Assumption (P(k)): Assume \( \frac{d^k y}{dx^k} = (x+k)e^x \).
  • Inductive Step (P(k+1)):

    The \((k+1)\)th derivative is the derivative of the \(k\)th derivative:
    \( \frac{d^{k+1} y}{dx^{k+1}} = \frac{d}{dx} \left[ (x+k)e^x \right] \)

    Use the product rule, noting that \(k\) is a constant:
    \( = \frac{d}{dx}(x+k) \cdot e^x + (x+k) \cdot \frac{d}{dx}(e^x) \)
    \( = 1 \cdot e^x + (x+k) e^x \)
    \( = e^x (1 + x + k) \)
    \( = (x + (k+1))e^x \)

    This matches the formula for \(n=k+1\).

Recognizing Conjectures and Trial Strategy (Syllabus 1.7)

Sometimes, the exam question will not give you the formula (the statement \(P(n)\)) upfront. You are expected to use a limited trial to find the pattern and form a conjecture, which you then prove using induction.

How to Form a Conjecture:

  1. Calculate the First Few Cases: Work out the result for \(n=1, 2, 3,\) and perhaps \(4\).
  2. Look for Patterns:
    • Summations: If the result is a polynomial, look for cubic (\(n^3\)), quadratic (\(n^2\)), or linear (\(n\)) factors.
    • Recurrence: Look for relationships involving powers of the common factor (like \(3^n\) in the earlier example).
    • Derivatives/Matrices: Look at how the coefficients change with \(n\). Often, the change is linear (\(+n\)) or exponential (\(2^n\)).
  3. Write the Conjecture: State the formula clearly in terms of \(n\). This becomes your \(P(n)\) for the subsequent proof by induction.

Did you know?
The step-by-step calculation to find the sum of series like \(\sum_{r=1}^n r \times r!\) (which simplifies to \((n+1)! - 1\)) is a classic example where generating the first few results (conjecture) is essential before applying induction to prove the general closed form.

Quick Review: The Inductive Steps


1. Base Case (n=1): Show LHS = RHS.
2. Assume P(k): Write the equation/statement for k.
3. Prove P(k+1): Start with P(k+1) and use P(k) as a substitution to reach the required form.
4. Conclusion: Formal logical statement.