Proof by induction
Proof by induction
- Mathematical induction proves a result for every positive integer $n$ in two steps:
- Base case: show it's true for $n = 1$.
- Inductive step: assume it's true for $n = k$, then prove it for $n = k + 1$.
- If both work, the result holds for all $n$.
Practice
The two steps of proof by induction are the base case and the:
Induction needs a base case plus an inductive step from k to k+1.
Practice
The base case usually shows the result is true for:
The base case checks the smallest value, usually n = 1.
Practice
If both the base case and the inductive step hold, the result is true for all positive integers n.
That is exactly what the principle of induction guarantees.
Conjecture then prove
- Often you make a conjecture (a sensible guess) from a few cases, then confirm it by inductive proof.
You've got it
Key idea
- induction = base case ($n=1$) + inductive step ($n=k \Rightarrow n=k+1$)
- both steps together prove it for all positive integers
- often conjecture from cases, then prove by induction