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 ${\displaystyle N}$ jest dowolną dodatnią liczbą całkowitą, istnieją takie liczby całkowite ${\displaystyle c_{i}\geqslant 2}$ spełniające ${\displaystyle c_{i+1}>c_{i}+1,}$ że:

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

gdzie ${\displaystyle F_{n}}$ jest n-tą liczbą Fibonacciego. Taką sumę nazywamy reprezentacją Zeckendorfa liczby ${\displaystyle 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 [online], 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.