Twierdzenie Zeckendorfa

Twierdzenie Zeckendorfa (od nazwiska belgijskiego lekarza Edouarda Zeckendorfa) – twierdzenie o reprezentacji liczb całkowitych jako sum liczb Fibonacciego.

Twierdzenie Zeckendorfa mówi, że każda dodatnia liczba całkowita może być przedstawiona jednoznacznie jako suma jednej lub więcej różnych liczb Fibonacciego w taki sposób, że owa suma nie zawiera żadnych dwóch kolejnych liczb Fibonacciego. Czyli, jeżeli $N$ jest dowolną dodatnią liczbą całkowitą, istnieją takie liczby całkowite $c_{i}\geqslant 2$ spełniające $c_{i+1}>c_{i}+1,$ że:

$N=\sum _{i=0}^{k}F_{c_{i}},$

gdzie $F_{n}$ jest n-tą liczbą Fibonacciego. Taką sumę nazywamy reprezentacją Zeckendorfa liczby $N.$

Na przykład reprezentacja Zeckendorfa dla liczby 100 to:

100 = 89 + 8 + 3.

Są także inne sposoby przedstawienia liczby 100 jako sumy liczb Fibonacciego, na przykład:

100 = 89 + 8 + 2 + 1,

100 = 55 + 34 + 8 + 3.

ale nie są one reprezentacjami Zeckendorfa, gdyż 1 i 2 są kolejnymi liczbami Fibonacciego, podobnie jak 34 i 55.

Dla każdej dodatniej liczby całkowitej reprezentacja, która spełnia warunki twierdzenia Zeckendorfa, może być znaleziona poprzez użycie algorytmu zachłannego, poprzez wybór największej możliwej liczby Fibonacciego przy każdym kroku.

Bibliografia

• Eric W.E.W. Weisstein Eric W.E.W., Zeckendorf Representation, [w:] MathWorld, Wolfram Research [dostęp 2009-02-10]  (ang.).
• D.E. Knuth: Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57–60.
• E. Zeckendorf: Representation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179–182, 1972.