Compositions into ones and twos are counted by Fibonacci numbers
ProvedAnalyticCombinatorics.Ch1.counts_seq_parts12analytic-combinatoricsformal-power-serieslean4symbolic-method
Let be the combinatorial class with one object of size , one object of size , and no objects of any other size. For every natural number , including , the number of finite ordered sequences of -objects of total size is
where and define the initial Fibonacci numbers. The size-zero sequence is the empty sequence. This identifies a concrete sequence construction with a familiar counting sequence.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Fibonacci
import Mathlib.Data.Nat.Fib.Basic
import Mathlib.Algebra.BigOperators.NatAntidiagonal
import Mathlib.RingTheory.PowerSeries.Inverse
import Mathlib.RingTheory.PowerSeries.NoZeroDivisors
import Mathlib.Combinatorics.Enumerative.Composition
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch1 §I.3 — Fibonacci numbers as compositions into parts `1` and `2`
Flajolet & Sedgewick, Part A, Chapter I, §I.3. Let `D` be the class with one
object of size `1` and one of size `2`. Then `SEQ(D)` enumerates compositions of
`n` into parts of size `1` and `2`, and
* `counts_seq_parts12` — there are `F_{n+1}` of them (`Nat.fib (n+1)`), via the
convolution recursion `counts_seq_succ`, which here is the Fibonacci recurrence;
* `ogf_parts12` / `ogf_seq_parts12` — `D(z) = z + z²` and the OGF is
`1/(1 - z - z²)`, the Fibonacci generating function.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.counts_seq_parts12 (n : ℕ) :
CombClass.parts12.seq.counts n = Nat.fib (n + 1) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).