← ICARM tutorials

Factorials, Binomials, Fibonacci

This tutorial runs a version of Lean in the cloud, using live.lean-lang.org.

Working in the browser. Each link opens a new tab. Close the previous tab when you open the next exercise, to avoid overloading the server. Each file starts with the solutions to the earlier ones. The editor keeps your code in the address bar, so to save your work, bookmark the page or copy the address.

Session 1: Define, compute, conjecture

Recursion

0! = 1
(n + 1)! = (n + 1) · n!

A recursive definition gives the value at n + 1 in terms of the value at n. The base case is 0.

def fact : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * fact n

Many values at once. List.range 11 is the list [0, 1, ..., 10], and (List.range 11).map fact applies fact to each entry, giving [fact 0, fact 1, ..., fact 10]. To apply a function that has no name, write it with fun: fun n => 2 * n + 1 is the function n ↦ 2n + 1, so (List.range 5).map fun n => 2 * n + 1 gives [1, 3, 5, 7, 9].

Open demo in Lean

Exercise 1: Factorial and sums

Prove fact 6 = 720 two ways, complete sumTo, and add up odd numbers.

Open Exercise 1 in Lean

Binomial coefficients

C(n, k) is the number of ways to choose k items from a collection of n.

C(n, 0) = 1
C(0, k + 1) = 0
C(n + 1, k + 1) = C(n, k) + C(n, k + 1)

Pascal's rule. To choose k + 1 items from n + 1, consider the first one. Either we choose it, and then we choose k more from the other n, or we don't, and we choose all k + 1 from the other n.

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
def choose : Nat → Nat → Nat
  | _, 0 => 1
  | 0, _ + 1 => 0
  | n + 1, k + 1 => choose n k + choose n (k + 1)

Fibonacci numbers have two base cases.

F0 = 0,   F1 = 1,   Fn+2 = Fn + Fn+1

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Open demo in Lean

Exercise 2: Experiments

Print Pascal's triangle, compute, and write down conjectures.

Open Exercise 2 in Lean
Conjectures (do Exercise 2 before looking at these)

Proof by induction

To prove P(n) for every n:

  1. Base case. Prove P(0).
  2. Induction step. Assume P(n) (the induction hypothesis) and prove P(n + 1).

Example: 1 + 3 + ⋯ + (2n − 1) = n2.

Base: the empty sum is 0 = 02.
Step: [1 + 3 + ⋯ + (2n − 1)] + (2n + 1) = n2 + 2n + 1 = (n + 1)2.

theorem sum_odds (n : Nat) : sumTo (fun i => 2 * i + 1) n = n * n := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [sumTo]   -- split off the last term
    rw [ih]      -- use the induction hypothesis
    grind        -- do the algebra

Each line is one step of the proof on paper. Put the cursor after each line to see the goal change.

Open demo in Lean

Exercise 3: First proofs

Gauss's formula, the sum of Fibonacci numbers, and 0 < fact n.

Open Exercise 3 in Lean

Session 2: Prove

Proofs about choose

In the next demo, cases n is similar to induction n, but it splits the proof into cases n = 0 and n = m + 1 without an induction hypothesis. t1 <;> t2 means “do t1, then t2 in every resulting case.”

We also need a strengthened version of induction. Suppose the goal is to prove C(n, k) = 0 when n < k. Pascal's rule needs the hypothesis for both k and k + 1.

  | succ k =>
    rw [choose]                 -- choose n k + choose n (k + 1) = 0
    rw [ih k (by grind)]        -- 0 + choose n (k + 1) = 0
    rw [ih (k + 1) (by grind)]  -- done

ih k (by grind) applies the induction hypothesis to k, and grind proves the side condition n < k.

Open demo in Lean

Exercise 4: Binomial coefficients

Prove choose n 1 = n and choose n n = 1.

Open Exercise 4 in Lean

A better implementation of the Fibonacci numbers

fib computes the same values over and over:

fib 5
├── fib 3
│   ├── fib 1
│   └── fib 2
│       ├── fib 0
│       └── fib 1
└── fib 4
    ├── fib 2
    │   ├── fib 0
    │   └── fib 1
    └── fib 3
        ├── fib 1
        └── fib 2
            ├── fib 0
            └── fib 1

A faster way: carry two consecutive values along, replacing (a, b) by (b, a + b) at each step.

def fibLoop : Nat → Nat → Nat → Nat
  | 0, a, _ => a
  | n + 1, a, b => fibLoop n b (a + b)

def fastFib (n : Nat) : Nat := fibLoop n 0 1
steps leftab
501
411
312
223
135
058

So fastFib 5 = 5. To prove fastFib n = fib n for all n, we prove something stronger: if the loop starts from Fm and Fm+1, then after n steps it returns Fn+m.

theorem fibLoop_eq (n m : Nat) :
    fibLoop n (fib m) (fib (m + 1)) = fib (n + m)
Open demo in Lean

Exercise 5: Fast Fibonacci is correct

Prove fibLoop_eq, then deduce fastFib n = fib n.

Open Exercise 5 in Lean

The big theorems

Row sums. By Pascal's rule, each entry of row n contributes to exactly two entries of row n + 1. So each row sum is twice the one before, and

C(n, 0) + C(n, 1) + ⋯ + C(n, n) = 2n.

The committee identity. Choose a committee of k + 1 from n + 1 people, then its chair. Or choose the chair first, then the other k members from the remaining n.

C(n + 1, k + 1) · (k + 1) = (n + 1) · C(n, k)

The factorial formula, by induction on n:

C(n, k) · k! · (n − k)! = n!    for k ≤ n

C(n+1, k+1) · (k+1)! · (n−k)!
  = C(n+1, k+1) · (k+1) · k! · (n−k)!
  = (n+1) · C(n, k) · k! · (n−k)!
  = (n+1) · n!
  = (n+1)!

We state it with multiplication because division on Nat rounds down.

Open all the proofs in Lean

Exercise 6: Choose a challenge

Open Exercise 6 in Lean

Further reading