How would you prove that \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\) holds for every natural number? Checking case by case is impossible: there are infinitely many naturals. We need a different argument, one that covers every case at once.
That is the central question of this series, and the answer is the Principle of Mathematical Induction.
What you will learn #
The article Mathematical Induction: Proving Properties for All Naturals presents the classic structure of a proof by induction (base case, inductive hypothesis and step) with complete examples of sums, products and divisibility. It also covers the generalized version with base \(n_0 \neq 1\).
The article Strong Induction: When the Step Needs More Context extends the classic method to situations where step \(k+1\) depends on several previous cases. The Fibonacci sequence, the proof of prime factorization and Binet’s formula show when and why the stronger hypothesis is needed.
Finally, the article Recurrence Relations: Defining Sequences by Themselves generalizes the idea of recurrence: how to set up the equation that describes a sequence and how to solve it by substitution to get closed-form formulas. The Tower of Hanoi, valid arithmetic expressions and the ovals in the plane problem are the central examples. The article also presents the characteristic equation, a systematic technique for solving second-order recurrences (those in which each term depends on the two previous ones, like Fibonacci), and divide-and-conquer recurrences, with the Master Theorem.
The diagram below shows how the three articles build on each other: strong induction starts from mathematical induction, and recurrence relations use both to verify the closed-form formulas they find.
flowchart LR A["Mathematical Induction
base, hypothesis and step"] -->|"stronger hypothesis"| B["Strong Induction
all previous cases"] A -->|"verifies the
closed-form formulas"| C["Recurrence Relations
substitution, characteristic
equation and
divide and conquer"] B -->|"verifies the
second-order ones"| C
Why induction and recurrence? #
Mathematical induction and recurrence relations show up in practically all of the rest of discrete mathematics:
- Algorithm analysis: the complexity of MergeSort satisfies \(T(n) = 2T(n/2) + n\), a recurrence that shows the algorithm is \(O(n \log n)\), as the section on divide and conquer of the article on recurrence relations shows.
- Combinatorics: the combination formulas and the coefficients of the binomial theorem have natural proofs by induction.
- Graphs: properties of trees (number of edges, paths) are proved by induction on the number of vertices.
- Number theory: divisibility, prime factorization and the very structure of the naturals depend on the inductive principle.
Mastering these tools is essential to reason precisely about discrete structures.
Prerequisites #
Familiarity with natural numbers, basic algebra and summation notation (\(\sum\)). The previous series, The Language of Sets, covers the foundations of set theory, but it is not a strict prerequisite for this material.
If you want to understand the overall plan of the Discrete Mathematics series on the site (which topics will be covered, why they were chosen and the motivation behind them), the article Discrete Mathematics: Introduction and Roadmap lays out the complete map of the four planned series.
See you next time!
