Zeckendorf's theorem
ProvedFamousTheorems.zeckendorfZeckendorf's theorem.
Every natural number has a unique representation as a sum of non-consecutive Fibonacci numbers. Packaged as a bijection:
For example , using — no two of them adjacent in the Fibonacci sequence. Existence comes from the greedy algorithm (repeatedly subtract the largest Fibonacci number not exceeding what remains, which automatically skips the next one down); uniqueness is the substantial half, and follows from the identity bounding what the smaller terms can contribute.
The non-consecutiveness condition is exactly what pins the representation down: without it already has two forms. The resulting digit string is the Fibonacci numeration system, and reading it as a word gives the Fibonacci-word and golden-ratio dynamics of the Zeckendorf shift.
Named for Edouard Zeckendorf, who published in 1972, though Lekkerkerker proved it in 1952.
Formalization note. l.IsZeckendorfRep says the list of Fibonacci indices is strictly
decreasing with gaps at least two and bounded below appropriately, so the subtype is the set
of valid representations; the bijection is data, hence Nonempty. The result is Mathlib's
Nat.zeckendorfEquiv.
import Mathlib
namespace FamousTheorems
open Filter Set Topology
theorem zeckendorf : Nonempty (ℕ ≃ {l : List ℕ // l.IsZeckendorfRep}) := by sorry
end FamousTheorems