summaryrefslogtreecommitdiff
path: root/proofs/Fib.lean
blob: c49a2098e6fcbd24c592ded1e86ba1f697e321c2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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)