Skip to content

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 ih is 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:

  1. It holds when n is 0.
  2. 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:

text
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 ih

ih 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:

lean
example (n : Nat) : 0 + n = n := by
  rfl
text
is not definitionally equal to the right-hand side

So we use induction. Walk through it yourself, and pay attention to what ih looks like in the second branch:

Prove it yourselfFirst inductive proof: 0 + n = nStatus and errors are handled by Lean 4.35.0 Generate
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:

lean
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:

lean
#check @Nat.add_succ
text
Nat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succ

m.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 ih in this proof: 0 + k = k

Back to the Summation Formula ​

The function and theorem from the first section:

lean
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]
    omega

Now you can read it:

  • induction n with: induction on n.
  • zero branch: n is 0, both sides compute to 0, rfl.
  • succ k ih branch: ih is 2 * sumTo k = k * (k + 1).
    • simp [sumTo]: expand sumTo (k + 1) into sumTo k + (k + 1) by definition.
    • rw [Nat.mul_add, ih]: multiply 2 into the parentheses, 2 * sumTo k appears, and is replaced using ih.
    • 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_formula uses 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 ih is a hypothesis, not a goal
  • I understood what every line of sumTo_formula does

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".

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.