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
#eval fact 5computes a value.example : fact 5 = 120 := by rflstates a fact, and Lean checks it.
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].
Exercise 1: Factorial and sums
Prove fact 6 = 720 two ways, complete sumTo, and add up odd numbers.
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 LeanExercise 2: Experiments
Print Pascal's triangle, compute, and write down conjectures.
Open Exercise 2 in LeanConjectures (do Exercise 2 before looking at these)
- Row sums: C(n, 0) + ⋯ + C(n, n) = 2n
- C(n, 1) = n, C(n, n) = 1, C(n, k) = 0 when n < k
- C(n, k) = n! / (k! (n − k)!)
- F0 + F1 + ⋯ + Fn−1 + 1 = Fn+1
- 1 + 3 + 5 + ⋯ + (2n − 1) = n2
- The shallow diagonals of Pascal's triangle add up to Fibonacci numbers.
Proof by induction
To prove P(n) for every n:
- Base case. Prove P(0).
- 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.
rw [f]unfolds the definition offonce.rw [h], whereh : a = b, replacesabybin the goal.rw [← h]replacesbbya.simpsimplifies the goal. It may finish the proof or leave a simpler goal.exact hfinishes a goal that is exactlyh.grindfinishes off the arithmetic.
Exercise 3: First proofs
Gauss's formula, the sum of Fibonacci numbers, and 0 < fact n.
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.
induction n: the hypothesis is P(n, k) for this one k. Not enough.induction n generalizing k: the hypothesis is P(n, k) for every k.
| 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.
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 left | a | b |
|---|---|---|
| 5 | 0 | 1 |
| 4 | 1 | 1 |
| 3 | 1 | 2 |
| 2 | 2 | 3 |
| 1 | 3 | 5 |
| 0 | 5 | 8 |
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.
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.
Exercise 6: Choose a challenge
- prove the committee identity.
- finish Exercises 4 and 5.
- Pascal's diagonals, on paper.
- your own conjecture.