summaryrefslogtreecommitdiff
path: root/proofs/Fib.lean
diff options
context:
space:
mode:
authorJohannes Hofmann <Johannes.Hofmann@gmx.de>2026-11-10 09:13:35 +0100
committerJohannes Hofmann <Johannes.Hofmann@gmx.de>2026-11-10 09:13:35 +0100
commit45a4b80a3d44f054a471cd417c7c2698f4770599 (patch)
tree7785b86ed5a6999202c39616936556d8982d49f1 /proofs/Fib.lean
parent0b0663e0c9dc664f35ffead3b395ffd2009fd98c (diff)
proofs: Lean transcriptions + flaw-finding, with a Rust referee
Gipfel.lean verifies the structural invariants (mark_duplicates keeps hill indices stable). GipfelFind.lean hunts flaws: exact Int model for the general fact, Float grid search for concrete IEEE witnesses, every witness re-checked against the real code by rust-check/. Findings: 1 fixed on master (is_visible azimuth wrap), 2 proven benign via project_point (all witnesses NaN via 0*inf; residual near-zero denominators documented), 3 open but cosmetic, 4 already handled by the stitch caller. GipfelMathlib.lean.txt stays an unchecked sketch, kept as .txt so it cannot pass for a verified artifact. Verified from this location: lean checks both files clean, rust-check runs against the workspace gipfel-core via path dependency.
Diffstat (limited to 'proofs/Fib.lean')
-rw-r--r--proofs/Fib.lean88
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)