Doing Induction on Natural Numbers
After finishing this section, you will be able to prove propositions of the form "holds for all natural numbers n". The sumTo_formula that was unreadable in the first section — by the end of this section, you will be able to read it yourself.
What You Will Be Able to Do
- State the two parts of an induction proof
- Understand what the induction hypothesis
ihis and where it can be used - Write out a complete induction proof using
induction n with
Why Induction Is Needed
The decide from the previous section can only compute concrete numbers. "For all n" has infinitely many cases — you can never finish computing them.
The approach of induction is to prove only two things:
- It holds when n is 0.
- If it holds for k, then it also holds for k + 1.
With these two facts, 0 holds, so 1 holds, so 2 holds, and so on — every natural number gets its turn. It's like knocking over a row of dominoes: the first one falls, and each one knocks over the next.
In Lean, these two facts correspond to two branches:
induction n with
| zero => prove the case where n is 0
| succ k ih => prove the case where n is k + 1, and you may use ihih is the "if it holds for k" part of item 2. It is a hypothesis, whose content is the proposition with n replaced by k.
Hands-on: 0 + n = n
This proposition seems to need no proof. But Lean's addition is defined layer by layer on the second number: n + 0 can compute n directly, while 0 + n cannot. Try it and you'll see:
example (n : Nat) : 0 + n = n := by
rflis not definitionally equal to the right-hand sideSo we use induction. Walk through it yourself, and pay attention to what ih looks like in the second branch:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]
Written as code:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]This uses a ready-made theorem; look up what it says:
#check @Nat.add_succNat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succm.succ is just m + 1. This theorem says: n + (m + 1) equals (n + m) + 1. After rewriting with it, 0 + k appears in the goal, which is exactly the left-hand side of ih, so you can rewrite once more using ih.
That's the pattern of an induction proof: reshape the k + 1 case into a form where the k case is visible, then use the induction hypothesis.
- I finished proving
zero_add'in the exercise - I can state the content of
ihin this proof:0 + k = k
Back to the Summation Formula
The function and theorem from the first section:
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaNow you can read it:
induction n with: induction on n.zerobranch: n is 0, both sides compute to 0,rfl.succ k ihbranch:ihis2 * sumTo k = k * (k + 1).simp [sumTo]: expandsumTo (k + 1)intosumTo k + (k + 1)by definition.rw [Nat.mul_add, ih]: multiply 2 into the parentheses,2 * sumTo kappears, and is replaced usingih.- Last two lines: what remains is pure arithmetic — expand the multiplication and hand it over to
omega.
The pattern hasn't changed: expand the definitions, expose the k case, use ih, and hand the rest over to automation tactics.
- I can point out which step in
sumTo_formulauses the induction hypothesis
Quiz timeIn the succ k ih branch, what does the induction hypothesis ih say?
Checkpoint
- I can state the two parts of an induction proof: the 0 case, and going from k to k + 1
- I can write out the structure of
induction n with | zero => … | succ k ih => … - I know that
ihis a hypothesis, not a goal - I understood what every line of
sumTo_formuladoes
Didn't Succeed?
In the succ branch, you don't know what to do next. Check whether the left-hand side of ih appears in the goal. If not, first expand definitions or rewrite until it does.
The branch names are written wrong. The two branches for natural numbers are fixed as zero and succ. k and ih are names you choose yourself.
Next Section
Induction isn't only for numbers. The next section does induction on lists, and for the first time you'll encounter the situation of "the proof gets stuck, and you need to prove a helper first".