Welcome to the World of Proof! (FP1)

Hello future Further Mathematicians! This chapter, Proof, is perhaps the most fundamental part of advanced mathematics. It’s where you stop just calculating answers and start showing why the answers must be true.

In Further Pure Mathematics 1 (FP1), we focus almost exclusively on one powerful technique: Proof by Mathematical Induction. Don't worry if this sounds intimidating; it’s just a structured way of proving statements that hold true for all positive whole numbers (integers).

Why is Proof Important?

Think of mathematics as a magnificent building. Calculations are the bricks and mortar, but proof is the architectural blueprint that guarantees the building won't collapse. Proof provides the absolute certainty that distinguishes mathematical truths from mere hypotheses.

Section 1: The Foundation – What Are We Proving?

When we prove something using induction, we are typically dealing with a statement, let's call it \(P(n)\), that depends on a positive integer \(n\).

Example: The statement \(P(n)\) could be "The sum of the first \(n\) positive integers is given by the formula \(\frac{1}{2}n(n+1)\)". We need to prove this formula works whether \(n\) is 1, 10, 1000, or any other positive integer.

Review: Direct Proof vs. Induction

In standard A-Level math, you primarily used Direct Proof (starting with known facts and logically deducing the conclusion) or Proof by Contradiction.

Induction is different. You cannot check every single positive integer (because there are infinitely many!). Instead, we use a clever logical leap.

Analogy: The Domino Effect

Imagine you have an infinitely long line of dominos, numbered 1, 2, 3, ... \(n\), and so on. To prove they will all fall, you only need to show two things:

  • 1. The First Domino Falls: You push the first domino (the base case).
  • 2. The Chain Reaction Works: You prove that if *any* domino (\(k\)) falls, it will definitely knock over the *next* domino (\(k+1\)).
If both conditions are met, then the entire infinite line must fall! That's exactly how Mathematical Induction works.

Section 2: Proof by Mathematical Induction (PMI)

Mathematical Induction requires a strict, four-step structure. You must follow these steps precisely to earn full marks.

The Four Essential Steps of PMI

Step 1: The Base Case (The Start)

We must prove the statement \(P(n)\) is true for the smallest possible integer. Usually, this is \(n=1\). (Sometimes, the question specifies starting at \(n=2\) or \(n=3\), so always check the question!)

  • Action: Substitute the starting value (usually \(n=1\)) into both sides of the equation (LHS and RHS) or into the statement.
  • Goal: Show that LHS = RHS, or that the statement holds true.
Step 2: The Assumption (The Hypothesis)

This is the crucial logical leap. We assume the statement is true for some arbitrary positive integer \(k\).

  • Action: State clearly: "Assume \(P(k)\) is true for some positive integer \(k\)."
  • Goal: Write out the statement \(P(k)\). This is the key equation you will use in Step 3.
Step 3: The Inductive Step (The Chain Reaction)

This is the main mathematical work. We must use the assumption from Step 2 to prove that the statement is also true for the next integer, \(n=k+1\).

  • Action: Look at the statement \(P(k+1)\). Your aim is to manipulate the expression for \(P(k+1)\) until you can substitute the entire expression for \(P(k)\) into it.
  • Goal: Show that \(P(k+1)\) holds true.
Step 4: The Conclusion (The Final Link)

You must formally write out the final conclusion, linking Step 1 and Step 3 using the principle of induction. This demonstrates that you understand the domino logic. Do not skip this step!

Standard Wording: "Since \(P(1)\) is true, and we have shown that if \(P(k)\) is true, then \(P(k+1)\) is also true, by the Principle of Mathematical Induction, \(P(n)\) is true for all positive integers \(n\)."

Quick Review: The PMI Mnemonic

Use the acronym BAPC to remember the steps:

  • Base Case (\(n=1\))
  • Assumption (\(n=k\))
  • Prove (\(n=k+1\))
  • Conclusion (The final statement)

Section 3: Applications of Mathematical Induction

In FP1, Induction is generally applied to three types of problems: Series Summation, Divisibility, and Matrices.

Application Type A: Proof for Sums of Series (Sums)

These proofs involve showing that a given formula calculates the sum of the first \(n\) terms of a sequence, often involving \(\sum\) notation.

Key Insight for Step 3 (The Inductive Step)

If \(S_n\) is the formula for the sum of \(n\) terms, then the sum of \(k+1\) terms, \(S_{k+1}\), is just the sum of \(k\) terms plus the \((k+1)\)-th term:
\(S_{k+1} = S_k + (k+1)\)-th term

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

Step 2 (Assumption): Assume \(\sum_{r=1}^{k} r^2 = \frac{1}{6}k(k+1)(2k+1)\).

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

The LHS is: \(\sum_{r=1}^{k+1} r^2 = \sum_{r=1}^{k} r^2 + (k+1)^2\)

Substitute the assumption (the bracketed term is \(S_k\)):
\(= \left[ \frac{1}{6}k(k+1)(2k+1) \right] + (k+1)^2\)

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

(After simplification and factorising the quadratic \(2k^2+7k+6 = (2k+3)(k+2)\)):
\(= \frac{1}{6}(k+1)(k+2)(2k+3)\)

This final expression is exactly the required formula with \((k+1)\) substituted for \(n\). Success!

🔥 Tip for Sums: Always factorise the common bracket term early! This simplifies the resulting fraction manipulation drastically.

Application Type B: Proof for Divisibility

These proofs show that an expression (e.g., \(4^n - 1\)) is always divisible by a specific number (e.g., 3).

Key Insight for Step 2 (The Assumption)

If a statement \(P(k)\) is divisible by a number \(D\), we must write the assumption in terms of \(D\) and an integer multiple \(m\).
\(P(k) = Dm\), where \(m\) is an integer.

Key Insight for Step 3 (The Inductive Step)

When dealing with \(P(k+1)\), you must isolate the expression for \(P(k)\) so you can substitute \(Dm\) into it. Exponent rules are essential here.

Example Setup: Prove that \(9^n - 1\) is divisible by 8 for all \(n \geq 1\).

Step 2 (Assumption): Assume \(P(k)\) is true, so \(9^k - 1\) is divisible by 8. We write: \(9^k - 1 = 8m\) (where \(m\) is an integer).

Rearranging this assumption is vital: \(9^k = 8m + 1\).

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

The expression for \(P(k+1)\) is: \(9^{k+1} - 1\).

Use exponent rules: \(9^{k+1} - 1 = 9 \cdot 9^k - 1\)
Substitute the expression for \(9^k\) from the assumption:
\(= 9(8m + 1) - 1\)
\(= 72m + 9 - 1\)
\(= 72m + 8\)

Factor out the required divisor (8):
\(= 8(9m + 1)\)

Since \(m\) is an integer, \(9m+1\) must also be an integer. Therefore, \(P(k+1)\) is a multiple of 8, so it is divisible by 8. Success!

⚠️ Common Mistake: When dealing with powers (like \(a^{k+1}\)), remember that \(a^{k+1} = a \cdot a^k\). Always use this identity to introduce the term \(a^k\), which you can then substitute using your assumption.

Application Type C: Proof for Matrices

These proofs involve showing that applying a square matrix \(A\) repeatedly (finding \(A^n\)) results in a predictable formula based on \(n\).

Key Insight for Step 3 (The Inductive Step)

To find the matrix for \(n=k+1\), you must multiply the assumed matrix \(A^k\) by the original matrix \(A\).
\(A^{k+1} = A^k \times A\) (Order matters!)

Example Setup: Given matrix \(A\), show \(A^n = \begin{pmatrix} 1 & 2n \\ 0 & 1 \end{pmatrix}\).

Step 2 (Assumption): Assume \(A^k = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix}\).

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

We calculate \(A^{k+1}\): \(A^{k+1} = A^k A = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}\)

Perform matrix multiplication (Row by Column):
Element (1,1): \((1)(1) + (2k)(0) = 1\)
Element (1,2): \((1)(2) + (2k)(1) = 2 + 2k = 2(k+1)\)
Element (2,1): \((0)(1) + (1)(0) = 0\)
Element (2,2): \((0)(2) + (1)(1) = 1\)

The resulting matrix is: \(A^{k+1} = \begin{pmatrix} 1 & 2(k+1) \\ 0 & 1 \end{pmatrix}\)

This is exactly the required form of \(A^n\) with \(n\) replaced by \((k+1)\). Success!

Key Takeaway for PMI: The power of induction comes from the structure. You must clearly state your assumption (Step 2) and actively use it to prove the truth for the next case (Step 3). Without using the \(P(k)\) statement, your proof is incomplete.

Section 4: Advanced Tips and Accessibility

Understanding the Inequality Proofs (Less Common but Important)

Occasionally, you may need to prove an inequality (e.g., \(2^n > n^2\)). These are often slightly harder in Step 3 because you cannot simply rearrange terms; you must compare expressions.

The Trick: To prove \(P(k+1)\) (e.g., show \(LHS_{k+1} > RHS_{k+1}\)), start with the inequality you assumed in \(P(k)\). Add the necessary extra terms to both sides, and then prove that the resulting expression is still greater than the required \(RHS_{k+1}\).

Example approach: You want to show \(A > C\). You know from your assumption that \(A > B\). If you can show that \(B \geq C\), then logically \(A > C\).

Common Mistakes to Avoid!

  1. Failing the Conclusion: Omitting the final formal statement (Step 4) will cost you marks. Examiners need to see the linkage (Domino Logic).
  2. Not Using the Assumption: In Step 3, you must explicitly use the assumed statement \(P(k)\). If you prove \(P(k+1)\) independently without referencing \(P(k)\), it is not a proof by induction!
  3. Algebraic Sloppiness: Especially with series summation, factoring and fraction manipulation must be perfect. If your Step 3 algebra is wrong, you won't match the required \(P(k+1)\) form.
  4. Mistaking the Starting Point: If the question says "Prove true for \(n \geq 3\)", your base case must be \(n=3\), not \(n=1\).

Did You Know?

The Principle of Mathematical Induction was formally introduced by the French mathematician Blaise Pascal in the 17th century, though the concept had been used in ancient Greek mathematics. It remains one of the most reliable and fundamental tools in number theory and computer science today.