Twierdzenie Zeckendorfa

Twierdzenie Zeckendorfa, od nazwiska belgijskiego matematyka Edouarda Zeckendorfa, jest twierdzeniem 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

• Zeckendorf representation - Wolfram MathWorld (ang.). [dostęp 10.02.2009 r.].
• 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. Liege 41, 179-182, 1972