Fibonacci numbers are sums of binomial coefficients along shallow diagonals
ProvedFamousTheorems.fibonacci_shallow_diagonal_binomial_7bFibonacci numbers are sums along the shallow diagonals of Pascal's triangle. For every ,
where , and .
This connection between Fibonacci numbers and Pascal's triangle was noted by Lucas and appears already in Indian prosody. Both sides count the tilings of a strip of length by squares and dominoes: a tiling with dominoes uses tiles, and there are ways to place the dominoes among them.
Formalization note. Mathlib's Nat.fib_succ_eq_sum_choose. The sum runs over pairs of natural numbers with , and when .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem fibonacci_shallow_diagonal_binomial_7b (n : ℕ) : Nat.fib (n + 1) = ∑ p ∈ Finset.HasAntidiagonal.antidiagonal n, p.1.choose p.2 := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.fib_succ_eq_sum_choose`. Proof here reduces to that Mathlib result.