Twierdzenie Zeckendorfa

Reprezentacja Zeckendorf pierwszych 89 liczb całkowitych. Szerokości prostokątów to liczby Fibonacciego , podczas gdy odpowiadające im wysokości mają . Prostokąty tego samego koloru są przystające.

F_i

{\ displaystyle F_ {i-1}}

Twierdzenie Zeckendorf zwany sposób z matematyka belgijskim Edouard Zeckendorf , to twierdzenie w dodatku teorii liczb , które gwarantuje, że dowolna liczba naturalna może być reprezentowany w sposób szczególny, jako suma Fibonacciego oddzielania i nie odbywa się kolejno. Ta reprezentacja jest nazywany reprezentacji Zeckendorf się . $NIE$ $NIE$

Oświadczenie i przykład

Twierdzenie Zeckendorfa - dla każdej naturalnej liczby całkowitej istnieje unikalna sekwencja liczb całkowitych , z i , taka, że $NIE$ ${\ displaystyle c_ {0}, \ ldots, c_ {k}}$ ${\ displaystyle c_ {0} \ geq 2}$ ${\ displaystyle c_ {i + 1}> c_ {i} +1}$

{\ Displaystyle N = \ suma _ {i = 0} ^ {k} F_ {c_ {i}}}

gdzie jest -ta liczba Fibonacciego. $F_ {n}$ $nie$

Na przykład jest reprezentowana przez pustą sumę . Przedstawienie liczby w Zeckendorfie to ${\ displaystyle 0}$ $100$

{\ displaystyle 100 = 89 + 8 + 3}

Liczba ma inne reprezentacje jako suma liczb Fibonacciego. Więc : $100$

{\ displaystyle 100 = 89 + 8 + 2 + 1}

{\ Displaystyle 100 = 89 + 5 + 3 + 2 + 1}

{\ Displaystyle 100 = 55 + 34 + 8 + 3}

{\ Displaystyle 100 = 55 + 34 + 8 + 2 + 1}

{\ Displaystyle 100 = 55 + 34 + 5 + 3 + 2 + 1}

{\ Displaystyle 100 = 55 + 21 + 13 + 8 + 3}

ale te reprezentacje zawierają kolejne liczby Fibonacciego. Do dowolnej reprezentacji liczby całkowitej kojarzymy słowo binarne, którego -ta litera to jeśli występuje w reprezentacji, a jeśli nie. Tak więc z przedstawieniami powyższego związane są słowa: $NIE$ $nie$ $1$ $F_ {n}$ $NIE$ ${\ displaystyle 0}$ $100$

{\ displaystyle 1000010100}

{\ displaystyle 1000010011}

{\ displaystyle 1000001111}

{\ displaystyle 110010100}

{\ displaystyle 110010011}

{\ displaystyle 110001111}

{\ displaystyle 101110100}

Zbiór słów binarnych związanych z przedstawieniami Zeckendorfa tworzy język racjonalny : są to puste słowa i słowa rozpoczynające się od dwóch następujących po sobie i niezawierające tych słów . Wyrażenie regularne tego języka jest $1$ $1$

{\ Displaystyle 0 + 1 (0 + 01) ^ {*}}

Kodowania Fibonacciego od liczby całkowitej jest z definicji słowo binarne związanego z reprezentacji, zwrócony a następnie symbolu . Tak więc kodowanie liczby Fibonacciego to . $1$ $100$ ${\ displaystyle 00101000011}$

Uwaga historyczna

Zeckendorf opublikował swój dowód twierdzenia w 1972 roku, kiedy to stwierdzenie było znane jako „twierdzenie Zeckendorfa” przez długi czas. Ten paradoks wyjaśniono we wstępie do artykułu Zeckendorfa: inny matematyk, Gerrit Lekkerkerker (en) , napisał dowód twierdzenia (i inne wyniki) po przemówieniu Zeckendorfa i opublikowanym w 1952 r., Przypisując autorstwo Zeckendorfowi. Według Clarka Kimberlinga był to artykuł Davida E. Daykina, opublikowany w prestiżowym czasopiśmie, który pomógł upublicznić wynik i jego autora.

Demonstracja

Dowód twierdzenia składa się z dwóch części:

1. Istnienie : Istnienie reprezentacji jest udowodnione przez użycie algorytmu zachłannego lub przez indukcję . $NIE$

Dwa dowody istnienia Pierwszy dowód Rozumujemy przez indukcję dobrze opartą na liczbie naturalnej . Jeśli wynosi zero, jest reprezentowane przez pustą sumę. W przeciwnym razie, z największą liczbą Fibonacciego mniejszą lub równą i albo . Zgodnie z hipotezą indukcyjną ma reprezentację. Tak więc, dla dowolnej liczby tej reprezentacji, dlatego . Reprezentacja , powiększona o , jest zatem rzeczywiście reprezentacją .

NIE

NIE

F_ {k}

{\ displaystyle k \ geq 2}

NIE

{\ displaystyle M = N-F_ {k}}

M

{\ displaystyle F _ {\ ell}}

{\ Displaystyle F_ {k} + F _ {\ ell} \ równoważnik F_ {k} + M = N <F_ {k + 1} = F_ {k} + F_ {k-1}}

{\ displaystyle F _ {\ ell} <F_ {k-1}}

M

F_ {k}

NIE

Drugi dowód Rozumujemy przez indukcję na rozpatrywanej liczbie całkowitej n . Istnienie jest łatwe do zweryfikowania dla małych wartości n . Załóżmy, że jest to prawda dla danej liczby całkowitej n i zdekomponuj tę liczbę, porządkując liczby Fibonacciego w porządku rosnącym. Należy rozważyć kilka przypadków:

Jeśli z i , to: ${\ Displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}$ ${\ displaystyle 4 \ leq i_ {1}}$ ${\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}$ ${\ Displaystyle n + 1 = F_ {2} + F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}$
Jeśli z i (i prawdopodobnie w takim przypadku warunki nie istnieją). Więc : ${\ Displaystyle n = F_ {3} + F_ {5} + \ cdots + F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}$ ${\ displaystyle i_ {r} \ geq 2r + 2}$ ${\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}$ ${\ displaystyle i_ {s} = 2r-1}$ ${\ Displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}$ ${\ Displaystyle n + 1 = F_ {2r} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}$
Jeśli z i (i prawdopodobnie w takim przypadku warunki nie istnieją). Więc : ${\ Displaystyle n = F_ {2} + F_ {4} + \ cdots + F_ {2r-2} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}$ ${\ displaystyle i_ {r} \ geq 2r + 1}$ ${\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}$ ${\ displaystyle i_ {s} = 2r-2}$ ${\ Displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}$ ${\ Displaystyle n + 1 = F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}$

W ten sposób przyznaje się również do rozkładu.

n + 1

2. Wyjątkowość : w tej części używamy następującego lematu:

Lemat - suma dowolnego niepustego zbioru odrębnych i niekolejnych liczb Fibonacciego, których największym elementem jest , jest ściśle mniejsza niż . $F_ {j}$ ${\ displaystyle F_ {j + 1}}$

Dwa dowody lematu Pierwsza demonstracja Rozumujemy prostą indukcją na liczbie elementów takiego zbioru . Inicjalizacja jest natychmiastowa. Ze względu na dziedziczność, jeśli ma więcej niż jeden element, usuńmy . Zgodnie z hipotezą indukcyjną suma pozostałych elementów jest ściśle mniejsza niż , zatem suma całkowita jest ściśle mniejsza niż .

S

S

F_ {j}

{\ displaystyle F_ {j-1}}

{\ Displaystyle F_ {j-1} + F_ {j} = F_ {j + 1}}

Druga demonstracja Jeśli z . Więc :

{\ Displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}

{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}

jeśli jest parzysta: $jest$ ${\ Displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} \ równoważnik F_ {i_ {s} -2} + F_ {i_ {s} - 4} + \ cdots + F_ {2}}$ w związku z tym : ${\ Displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} <F_ {i_ {s} -2} + F_ {i_ {s} -4 } + \ cdots + F_ {2} + 1 = F_ {i_ {s} -1}}$
jeśli jest dziwne: $jest$ ${\ Displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} \ równoważnik F_ {i_ {s} -2} + F_ {i_ {s} - 4} + \ cdots + F_ {3}}$ w związku z tym : ${\ Displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} <F_ {i_ {s} -2} + F_ {i_ {s} -4 } + \ cdots + F_ {3} + 1 = F_ {i_ {s} -1}}$

W każdym razie

{\ Displaystyle F_ {i_ {s}} \ równoważnik n <F_ {i_ {s}} + F_ {i_ {s} -1} = F_ {i_ {s} +1}}

Dowód wyjątkowości

Rozumujemy przez indukcję dobrze opartą na liczbie naturalnej . Zgodnie z lematem, w dekompozycji , największy indeks, dla którego występuje (jeśli dekompozycja jest niepusty, tj. Jeśli ) jest w całości określony przez . Zgodnie z hipotezą indukcyjną, rozkład (stąd reszta rozkładu ) jest również wyjątkowa. $NIE$ $NIE$ $k$ $F_ {k}$ $N \ neq 0$ ${\ Displaystyle F_ {k} \ równoważnik N <F_ {k + 1}}$ ${\ displaystyle N-F_ {k}}$ $NIE$

Reprezentacja liczb całkowitych pierwszych

W tabeli oznacza reprezentację słowa binarnego. ${\ Displaystyle R (N)}$ $NIE$

$NIE$	${\ Displaystyle R (N)}$
0	0
1	1
2	10
3	100
4	101
5	1000
6	1001
7	1010
8	10 000
9	10001
10	10010
11	10100

Naprzemienność 0 i 1 w każdej z kolumn odpowiada brakowi lub obecności prostokąta na rysunku u góry strony. Sekwencja ostatnich cyfr to

{\ displaystyle 010010100100 \ cdots}

To jest początek słowa Fibonacciego . Rzeczywiście, n- ty symbol słowa Fibonacciego to 0 lub 1 w zależności od tego, czy n to „parzysty Fibonacciego” czy „nieparzysty Fibonacciego”.

Wariacje

Reprezentacja liczbami Fibonacciego ujemnych indeksów

Ciąg liczb Fibonacciego można rozszerzyć na indeksy ujemne, ponieważ relacja

{\ Displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}

pozwala obliczyć zi od . Mamy (patrz odpowiednia sekcja artykułu o liczbach Fibonacciego ): $F _ {{n-2}}$ $F_ {n}$ $F _ {{n-1}}$

{\ Displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}

Kompletną sekwencją jest Donald Knuth zauważył, że każda względna liczba całkowita jest sumą liczb Fibonacciego ściśle ujemnych indeksów, które nazywa „Negafibonacci”, a reprezentacja jest unikalna, jeśli dwie użyte liczby nie są następujące po sobie. Na przykład : ${\ Displaystyle \ ldots, -8,5, -3,2, -1,1,0,1,1,2,3,5,8, \ ldots}$

${\ Displaystyle -11 = F _ {- 4} + F _ {- 6} = (- 3) + (- 8)}$ ;
${\ Displaystyle 12 = F _ {- 2} + F _ {- 7} = (- 1) +13}$ ;
${\ Displaystyle 24 = F _ {- 1} + F _ {- 4} + F _ {- 6} + F _ {- 9} = 1 + (- 3) + (- 8) + 34}$ ;
${\ Displaystyle -43 = F _ {- 2} + F _ {- 7} + F _ {- 10} = (- 1) + 13 + (- 55)}$ .

Jak wyżej, kojarzy nam się z reprezentacją liczby całkowitej w binarnym słowo , którego Ith list jest , jeśli pojawia się w reprezentacji i inaczej. Tak więc jest reprezentowane przez słowo . Obserwujemy, że liczba całkowita jest dodatnia wtedy i tylko wtedy, gdy długość skojarzonego słowa jest nieparzysta. $NIE$ $nie$ $1$ $F_ {n}$ $NIE$ ${\ displaystyle 0}$ $24$ ${\ displaystyle 100101001}$ $NIE$

Mnożenie Fibonacciego

Donald Knuth uważa operacji mnożenia naturalnymi liczbami całkowitymi i zdefiniowany w następujący sposób: ze względu na reprezentacje i produkt Fibonacciego jest liczbą całkowitą . ${\ displaystyle a \ circ b}$ $w$ $b$ ${\ Displaystyle a = \ suma _ {i = 0} ^ {k} F_ {c_ {i}} \; (c_ {i} \ geq 2)}$ ${\ Displaystyle b = \ suma _ {j = 0} ^ {l} F_ {d_ {j}} \; (d_ {j} \ geq 2)}$ ${\ displaystyle a \ circ b = \ sum _ {i = 0} ^ {k} \ sum _ {j = 0} ^ {l} F_ {c_ {i} + d_ {j}}}$

Na przykład jak i mamy . ${\ displaystyle 2 = F_ {3}}$ ${\ displaystyle 4 = F_ {4} + F_ {2}}$ ${\ Displaystyle 2 \ circ 4 = F_ {3 + 4} + F_ {3 + 2} = 13 + 5 = 18}$

Knuth udowodnił zaskakujący fakt, że ta operacja ma charakter skojarzeniowy .

Inne apartamenty

Zeckendorf udowadnia warunkowo istnienie i wyjątkowość reprezentacji liczby Lucasa .

Knuth wspomina, że twierdzenie Zeckendorfa pozostaje prawdziwe dla ciągów k-bonacciego , pod warunkiem, że nie użyjemy k kolejnych liczb takiego ciągu.

Aviezri Fraenkel podał ogólne stwierdzenie, które rozszerza poprzednie twierdzenia: Niech będzie szeregiem liczb całkowitych. Wszystko naturalne ma dokładnie jedną reprezentację formy ${\ displaystyle 1 = u_ {0} <u_ {1} <u_ {2} <\ cdots}$ $NIE$

{\ Displaystyle N = d_ {k} u_ {k} + d_ {k-1} u_ {k-1} + \ cdots + d_ {1} u_ {1} + d_ {0} u_ {0}}

gdzie są liczby naturalne, pod warunkiem, że ${\ displaystyle d_ {k}, \ ldots, d_ {0}}$

{\ Displaystyle d_ {i} u_ {i} + d_ {i-1} u_ {i-1} + \ cdots + d_ {0} u_ {0} <u_ {i + 1}}

dla . $i \ geq 0$

Ostrowskiego

Każda liczba nieracjonalna dopuszcza ciągły ułamkowy wzrost . Jeśli stawiamy , , , i , że był . Poniższa tworzy podstawę dla systemu numeracji : $\alfa$ ${\ displaystyle \ alpha = [a_ {0}, a_ {1}, a_ {2}, \ ldots]}$ ${\ displaystyle p _ {- 2} = 0}$ ${\ displaystyle p _ {- 1} = 1}$ ${\ displaystyle q _ {- 2} = 1}$ ${\ displaystyle q _ {- 1} = 0}$ ${\ displaystyle p_ {n} = a_ {n} p_ {n-1} + p_ {n-2}}$ ${\ displaystyle q_ {n} = a_ {n} q_ {n-1} + q_ {n-2}}$ ${\ displaystyle p_ {n} / q_ {n} = [a_ {0}, \ ldots, a_ {n}]}$ ${\ displaystyle (q_ {n})}$

Twierdzenie Ostrowskiego - Niech będzie liczbą niewymierną i będzie ciągiem mianowników zbieżności ułamka ciągłego . Każda dodatnia liczba całkowita jest jednoznacznie zapisywana jako $\alfa$ ${\ displaystyle (q_ {n})}$ $\alfa$ $NIE$

{\ Displaystyle N = b_ {k} q_ {k} + \ cdots + b_ {0} q_ {0}}

gdzie są liczbami całkowitymi spełniającymi następujące trzy warunki: $bi}$

${\ displaystyle 0 \ leq b_ {0} <a_ {1}}$ ;
${\ Displaystyle 0 \ równoważnik b_ {i} \ równoważnik a_ {i + 1}}$ dla ; $i> 0$
Bo jeśli , to . $i> 0$ ${\ displaystyle b_ {i} = a_ {i + 1}}$ ${\ displaystyle b_ {i-1} = 0}$

Do złotej proporcji , są wszystkie 1, są liczby Fibonacciego i trzy warunki oznaczają, że warunki sumy są różne i nie sobie. $mieć}$ $q_n$

Uwagi i odniesienia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu Wikipedii w języku angielskim zatytułowanego „ Twierdzenie Zeckendorfa ” ( zobacz listę autorów ) .

Édouard Zeckendorf, „ Reprezentacja liczb naturalnych przez sumę liczb Fibonacciego lub liczb Lucasa ”, Bull. Soc. Roy. Sci. Liège , vol. 41,1972, s. 179-182.
(nl) Cornelis Gerrit Lekkerkerker, „ Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci ” [„Reprezentacja liczb naturalnych przez sumę liczb Fibonacciego”], Simon Stevin , t. 29,1952, s. 190-195.
(w) Clark Kimberling, „ Edouard Zeckendorf [1901-1983] ” , Fibonacci Quart. , vol. 36 N O 5, 1998, s. 416–418.
(w) OF Daykin, „ Reprezentacja liczb naturalnych ma sumy uogólnionych liczb Fibonacciego ” , J. London Math. Soc. , vol. 35,1960, s. 143 -60.
(w) Donald Knuth, „Negafibonacci Numbers and the Hyperbolic Plane” referat przedstawiony na dorocznym spotkaniu MAA , The Fairmont Hotel, San Jose, CA. 2008-12-11 [ prezentacja online ] .
(w) Donald E. Knuth , " Mnożenie Fibonacciego " , Applied Mathematics Letters , t. 1, N O 1,1988, s. 57-60 ( DOI 10.1016 / 0893-9659 (88) 90176-0 )
Ćwiczenie 5.4.2-10 w (w) Donald E. Knuth , The Art of Computer Programming , Vol. 3: Sortowanie i wyszukiwanie ,1998, 2 II wyd. [ szczegóły wydania ].
(w) Aviezri S. Fraenkel, „ Systems of Numeration ” , Amer. Matematyka. Miesięcznie , vol. 92 N O 21985, s. 105-114.
To twierdzenie przypisuje się Aleksandrowi Ostrowskiemu (1922). Zobacz: (en) Jean-Paul Allouche i Jeffrey Shallit , Automatic Sequences: Theory, Applications, Generalizations , Cambridge, Cambridge University Press ,2003, 571 str. ( ISBN 0-521-82332-3 , Recenzje matematyczne 1997038 , czytaj online ), Sekcja 3.9.

Zobacz też

Powiązane artykuły

Linki zewnętrzne

(en) Eric W. Weisstein , „ Twierdzenie Zeckendorfa ” , o MathWorld
(en) Eric W. Weisstein , „ Zeckendorf Representation ” , na MathWorld
Odwrotność twierdzenia Zeckendorfa : twierdzenie Zeckendorfa o miejscu przecięcia węzła
(en) „Przedstawienie Zeckendorf” , Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN 978-1556080104 , czytaj online )
W następstwie A101330 z OEIS opisane mnożenia Fibonacciego