Proof — Edexcel A-Level Study Guide

## Overview  Proof by Mathematical Induction is a cornerstone of A-Level Further Mathematics and a powerful tool for proving statements about all positive integers. It's a formal, logical argument that functions like a chain of dominoes: if you can prove the first one falls (the **base case**), and that any domino falling will knock over the next one (the **inductive step**), you can conclude that all the dominoes will fall. In your exam, this topic appears in the Core Pure papers and typically accounts for 5-7 marks per question. Examiners are looking for a highly structured, rigorous argument, so precision is key. This topic has strong synoptic links with Series, Matrices, and Number Theory, making it a crucial concept to master. ## Key Concepts ### The Four-Step Induction Framework Mathematical induction follows a rigid four-step structure. Missing any of these steps will result in lost marks, particularly the final conclusion. Candidates must present their argument clearly, showing each logical stage.  1. **Base Case (n=1)**: First, you must prove the statement is true for the smallest possible value of n, which is usually n=1. This is the 'first domino'. You must explicitly substitute n=1 into both sides of the statement and show they are equal. A B1 mark is awarded for this. 2. **Inductive Hypothesis**: Next, you assume the statement is true for some arbitrary positive integer, n=k. You are not proving anything here; you are simply stating the assumption that will be used in the next step. This is often written as "Assume the result is true for n=k". An M1 mark is often given for this statement. 3. **Inductive Step (n=k+1)**: This is the core of the proof and where most algebraic manipulation occurs. You must prove that if the statement is true for n=k, then it must also be true for n=k+1. The goal is to manipulate the expression for n=k+1 until you can substitute the n=k assumption into it. This demonstrates that one domino falling causes the next to fall. This step attracts the majority of the method (M) and accuracy (A) marks. 4. **Conclusion**: Finally, you must write a concluding statement that ties everything together. This statement must be precise and reference the previous steps. A typical Edexcel-style conclusion is: "Since the statement is true for n=1, and if it is true for n=k then it is true for n=k+1, by the principle of mathematical induction, the statement is true for all positive integers n." This secures the final A1 cso (Correct Solution Only) mark. ### Types of Induction Proofs #### 1. Summation of Series This is the most common type of induction question. You will be asked to prove a formula for the sum of a series up to n terms.  **Example**: Prove that for all positive integers n, $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$. In the inductive step, you would start with the sum to k+1 terms, split it into the sum to k terms plus the (k+1)th term, and then substitute your assumption for the sum to k terms. #### 2. Divisibility These proofs require you to show that a function f(n) is divisible by a certain integer for all n. The key is to relate f(k+1) to f(k).  **Example**: Prove that $f(n) = 3^{2n} - 1$ is divisible by 8 for all positive integers n. In the inductive step, you would analyse f(k+1) and try to express it in the form of f(k) plus another term that is clearly divisible by 8. A common technique is to consider f(k+1) - f(k). #### 3. Powers of Matrices For these questions, you will be asked to prove a formula for the nth power of a given matrix.  **Example**: Given the matrix $M = \begin{pmatrix} 2 & 1 \ 0 & 1 \end{pmatrix}$, prove that $M^n = \begin{pmatrix} 2^n & 2^n-1 \ 0 & 1 \end{pmatrix}$ for all positive integers n. In the inductive step, you must show that $M^{k+1} = M^k imes M$. You substitute the assumed formula for $M^k$ and perform the matrix multiplication. Credit is given for explicitly showing the multiplication, not just stating the result.