diff options
Diffstat (limited to 'proofs/Fib.lean')
| -rw-r--r-- | proofs/Fib.lean | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/proofs/Fib.lean b/proofs/Fib.lean new file mode 100644 index 0000000..c49a209 --- /dev/null +++ b/proofs/Fib.lean @@ -0,0 +1,88 @@ +/- + Fibonacci numbers in plain Lean 4 (no Mathlib needed). + Compile / check with: lean Fib.lean +-/ + +-- ───────────────────────────────────────────────────────────── +-- 1. The definition (structural recursion on `Nat`) +-- ───────────────────────────────────────────────────────────── + +/-- The `n`-th Fibonacci number: 0, 1, 1, 2, 3, 5, 8, 13, ... -/ +def fib : Nat → Nat + | 0 => 0 + | 1 => 1 + | n + 2 => fib (n + 1) + fib n + +-- A quick sanity check. `#eval` runs the compiler; `#print` shows the +-- equation lemmas Lean derived from the definition. +#eval (List.range 11 |>.map fib) -- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] + +-- ───────────────────────────────────────────────────────────── +-- 2. The property: every Fibonacci number is the sum of the two +-- that precede it. +-- ───────────────────────────────────────────────────────────── + +-- Stated with `n + 2`, this is *literally* the definition: `rfl` proves it, +-- because both sides reduce to the same thing. +theorem fib_succ_two (n : Nat) : fib (n + 2) = fib (n + 1) + fib n := rfl + +-- Stated the way we normally write it on paper (with subtraction) it needs a +-- real proof, because Lean must first know `n - 1` and `n - 2` are not +-- truncated at zero. +/-- For every `n ≥ 2`, `fib n` is the sum of its two predecessors. -/ +theorem fib_two_predecessors (n : Nat) (h : 2 ≤ n) : + fib n = fib (n - 1) + fib (n - 2) := by + match n with + | 0 | 1 => omega -- excluded by `h : 2 ≤ n` + | k + 2 => + -- goal: fib (k + 2) = fib (k + 2 - 1) + fib (k + 2 - 2) + show fib (k + 2) = fib (k + 1) + fib k + rfl -- exactly `fib_succ_two k` + +-- The same fact phrased as "the next one is the sum of the two before it". +theorem fib_next (n : Nat) : fib (n + 2) = fib (n + 1) + fib n := rfl + +-- ───────────────────────────────────────────────────────────── +-- 3. Bonus: a fast (tail-recursive) version, proved correct. +-- The naive `fib` above is exponential; `fibLoop` is linear. +-- ───────────────────────────────────────────────────────────── + +/-- Iterative Fibonacci: `a` holds `fib (b+1)`, `b` holds `fib b`. -/ +def fibLoop : Nat → Nat → Nat → Nat + | 0, a, _ => a + | n + 1, a, b => fibLoop n (a + b) a + +/-- Correctness of the loop, proved for *any* starting pair `(fib (b+1), fib b)`. + Generalizing over `b` is what makes the induction go through: in the step we + need the hypothesis one position further along the sequence. -/ +theorem fibLoop_correct (n : Nat) : ∀ b, fibLoop n (fib (b + 1)) (fib b) = fib (n + b + 1) := by + induction n with + | zero => intro b; simp [fibLoop] + | succ n ih => + intro b + -- one step of the recurrence, in the direction we need + have step : fib b + fib (b + 1) = fib (b + 2) := by + show fib b + fib (b + 1) = fib (b + 1) + fib b + rw [Nat.add_comm] + show fibLoop (n + 1) (fib (b + 1)) (fib b) = fib ((n + 1) + b + 1) + -- unfold one loop step, reorder the sum, fold it into `fib (b + 2)`, + -- then use the induction hypothesis at `b + 1` + rw [show fibLoop (n + 1) (fib (b + 1)) (fib b) = fibLoop n (fib (b + 1) + fib b) (fib (b + 1)) from rfl, + Nat.add_comm (fib (b + 1)) (fib b), step, ih (b + 1)] + apply congrArg fib -- remaining goal is pure arithmetic + omega + +/-- `fibLoop` computes the same numbers as `fib`. -/ +theorem fib_succ_eq_fibLoop (n : Nat) : fib (n + 1) = fibLoop n 1 0 := by + have h := fibLoop_correct n 0 -- fibLoop n (fib 1) (fib 0) = fib (n + 0 + 1) + simp [fib] at h -- reduces `fib 1` to `1`, `fib 0` to `0`, `n + 0 + 1` to `n + 1` + exact h.symm + +#eval fib 30 -- 832040 (slow: exponential) +#eval fibLoop 29 1 0 -- 832040 (fast: linear; note fibLoop n 1 0 = fib (n+1)) +#eval fibLoop 40 1 0 -- 165580141 +#eval List.range 21 |>.map fun n => fib n + +-- Using the proved property as a rewrite rule: +example : fib 10 = fib 9 + fib 8 := fib_two_predecessors 10 (by omega) +example : fib 100 = fib 99 + fib 98 := fib_two_predecessors 100 (by omega) |
