Mathematics
Principle of Mathematical Induction
Quick fact
Mathematical induction works by proving two things: the base case (often n=0 or n=1) and the inductive step (if the statement holds for n, it holds for n+1). This is enough to prove the statement for all natural numbers, even though there are infinitely many.
Why this is interesting
Imagine lining up dominoes so that knocking the first one topples the second, and each topples the next—then all fall. But how do you know they all fall without actually watching an infinite line? Mathematical induction gives a proof that they do, using just two steps.
Read the full explanation
Understanding Principle of Mathematical Induction
Think of a statement you want to prove for every natural number—say, the formula for the sum of the first n integers: 1+2+...+n = n(n+1)/2. You can check it for n=1: both sides equal 1. That's the base case. Then you assume it's true for some arbitrary k, and using that assumption, you prove it for k+1. If you can do that, you've built a chain: true for 1, so true for 2; true for 2, so true for 3; and so on. The assumption is called the 'inductive hypothesis.' It's not a circular proof—it's a conditional step: 'if it works for k, then it works for k+1.' Combined with the base, it creates an infinite chain of implications.
A deeper explanation
The principle of mathematical induction is a formal proof technique for statements of the form 'for all natural numbers n, P(n) holds.' It consists of two steps: (1) Base case: verify P(0) or P(1). (2) Inductive step: prove that for any k, if P(k) is true, then P(k+1) must also be true. The validity of this method rests on the well-ordering principle: every nonempty set of natural numbers has a least element. Suppose the statement is false for some natural number. Then the set of counterexamples has a smallest element m. Since the base case is true, m cannot be the base case; so m-1 is a natural number for which the statement holds. But the inductive step then forces the statement to hold for m, a contradiction. Therefore no counterexample exists. Induction is not just for sums; it's used to prove properties of sequences, divisibility, inequalities, and to prove correctness of recursive algorithms. In discrete mathematics, it's a bridge between recursive definitions and closed-form expressions, and it's a cornerstone of algorithmic reasoning.