Mastering Proof by Induction: Series and Divisibility

Introduction to Mathematical Induction

Mathematical induction is a cornerstone of advanced mathematics, particularly within the UK Further Maths curriculum. It provides a rigorous framework to prove that a statement $P(n)$ is true for all natural numbers $n \ge a$. Think of it like a row of dominoes: if you can knock over the first one (the base case) and prove that any falling domino will inevitably knock over the next one (the inductive step), then every domino in the infinite line must fall.

For students, mastering this technique is essential not just for exam success, but for developing the logical precision required for university-level mathematics. Whether you are summing complex series or proving divisibility properties, the structure of an inductive proof remains your most reliable tool. This guide will walk you through the mechanics of these proofs, ensuring you can tackle them with confidence.

The Anatomy of an Inductive Proof

Every formal proof by induction must follow a strict, logical structure. Deviating from this structure often leads to lost marks in examinations. The process consists of three distinct phases:

1. The Base Case: Verify that the statement $P(n)$ holds for the smallest value of $n$ (usually $n=1$ or $n=0$).
2. The Inductive Hypothesis: Assume that the statement is true for some arbitrary positive integer $k$. That is, assume $P(k)$ is true.
3. The Inductive Step: Use the assumption $P(k)$ to prove that the statement must also be true for $n = k+1$. If you successfully show that $P(k) \implies P(k+1)$, the proof is complete.

Proving Series by Induction

Proving series identities involves showing that a summation formula holds for all $n$. The key is to express the sum of $k+1$ terms as the sum of $k$ terms plus the $(k+1)$-th term.

Example: Prove that $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$.

• Base Case ($n=1$): LHS $= 1^2 = 1$. RHS $= \frac{1(2)(3)}{6} = 1$. The base case holds.
• Hypothesis: Assume $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$.
• Inductive Step: We must show $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$. LHS $= \sum_{i=1}^{k} i^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$. Factorise out $\frac{k+1}{6}$: $\frac{k+1}{6} [k(2k+1) + 6(k+1)] = \frac{k+1}{6} [2k^2 + 7k + 6]$. Factorising the quadratic: $\frac{k+1}{6} (k+2)(2k+3)$. This matches the RHS for $n=k+1$.

Proving Divisibility by Induction

Divisibility proofs require you to show that an expression is a multiple of a certain integer. The trick is to manipulate the expression for $k+1$ so that it contains the expression for $k$, allowing you to substitute your hypothesis.

Example: Prove that $7^n - 1$ is divisible by 6 for all $n \ge 1$.

• Base Case ($n=1$): $7^1 - 1 = 6$, which is divisible by 6. True.
• Hypothesis: Assume $7^k - 1 = 6m$ for some integer $m$. Thus, $7^k = 6m + 1$.
• Inductive Step: Consider $7^{k+1} - 1$. $7^{k+1} - 1 = 7(7^k) - 1$. Substitute the hypothesis: $7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6$. Factorise: $6(7m + 1)$. Since $7m+1$ is an integer, the expression is divisible by 6.

Common Mistakes to Avoid

1. Neglecting the Base Case: Never skip the base case. It is the foundation of the entire proof. If the base case is false, the entire argument collapses.
2. Circular Reasoning: Do not assume what you are trying to prove. Ensure your inductive step clearly uses the hypothesis $P(k)$ to reach $P(k+1)$.
3. Algebraic Slips: When dealing with series, ensure you correctly identify the $(k+1)$-th term. A common error is adding the wrong term to the sum.
4. Weak Conclusion: Always explicitly state that since the base case is true and $P(k) \implies P(k+1)$, the statement is true for all $n$ by the principle of mathematical induction.

Frequently Asked Questions

• Can I start induction at $n=0$ or $n=5$? Yes, the base case must simply match the starting value specified in the problem.
• What is strong induction? Strong induction allows you to assume the statement is true for all values up to $k$, rather than just $k$ itself. It is useful for sequences defined by recurrence relations.
• Do I need to write out the full conclusion? Yes, examiners look for a clear concluding sentence that references the principle of mathematical induction.

Conclusion

Proof by induction is a powerful, systematic method that transforms complex problems into manageable algebraic steps. By consistently applying the base case, hypothesis, and inductive step, you can solve even the most challenging series and divisibility problems. Ready to see these concepts in motion? Visit MathInstructor AI to generate a free, narrated animated lesson on proof by induction and watch these proofs unfold step-by-step.