Zasada szufladkowa ciąg Fibonacciego
Zasada szufladkowa ciąg Fibonacciego
Dowieść wykorzystując ZSD, że dla każdej liczby naturalnej istnieje dodatni wyraz ciągu Fibonacciego, podzielny przez tę liczbę.
-
JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Re: Zasada szufladkowa ciąg Fibonacciego
Niech \(\displaystyle{ F_k}\) będzie \(\displaystyle{ k}\)-tą liczbą Fibonacciego. Chcemy pokazać, że dla każdej liczby naturalnej \(\displaystyle{ n}\) istnieje takie \(\displaystyle{ k}\), że \(\displaystyle{ n|F_k}\), tj. \(\displaystyle{ k}\)-ta liczba Fibonacciego jest podzielna przez \(\displaystyle{ n}\).
Przypomnijmy, że liczba \(\displaystyle{ a}\) dzieli się przez \(\displaystyle{ b}\) wtedy i tylko wtedy, gdy reszta z dzielenia \(\displaystyle{ a}\) przez \(\displaystyle{ b}\) wynosi \(\displaystyle{ 0}\). Zatem zamiast ciągu Fibonacciego wystarczy rozważyć ciąg reszt \(\displaystyle{ F_k}\) przy dzieleniu przez \(\displaystyle{ n}\). Zapiszmy ten ciąg reszt jako \(\displaystyle{ (F'_k)}\).
Zauważmy teraz, że wszystkich możliwych par reszt \(\displaystyle{ (F'_k,F'_{k+1})}\) jest \(\displaystyle{ n^2}\) - bo reszt od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\) jest dokładnie \(\displaystyle{ n}\), a więc par mamy \(\displaystyle{ n^2}\). Skoro ciąg Fibonacciego jest nieskończony, a możliwych par skończenie wiele, ta sama para musi wystąpić po raz kolejny dla pewnej dalszej wartości \(\displaystyle{ k'>k}\) (tu jest moment, z którego korzystamy z zasady szufladkowej). Ponadto z określenia ciągu Fibonacciego, wartość \(\displaystyle{ F'_{k+2}}\) jest określona przez swoje dwie poprzednie wartości (czyli dokładnie parę \(\displaystyle{ (F'_k,F'_{k+1})}\)), co sprawia, że ciąg \(\displaystyle{ (F'_k)}\) jest okresowy.
Pozostaje połączyć teraz prosty fakt, że \(\displaystyle{ F'_0=0}\) oraz \(\displaystyle{ F'_1=1}\).
Reasumując, \(\displaystyle{ F'_0=0}\) oraz \(\displaystyle{ F'_1=1}\) oraz wykazana okresowość ciągu dowodzi, że znajdziemy \(\displaystyle{ F'_l=0}\), gdzie \(\displaystyle{ l>0}\) spełniający warunek \(\displaystyle{ n\,|\, F_l}\).
Swoją drogą, najmniejsza taka dodatnia liczba \(\displaystyle{ l}\) nosi nazwę.
Przypomnijmy, że liczba \(\displaystyle{ a}\) dzieli się przez \(\displaystyle{ b}\) wtedy i tylko wtedy, gdy reszta z dzielenia \(\displaystyle{ a}\) przez \(\displaystyle{ b}\) wynosi \(\displaystyle{ 0}\). Zatem zamiast ciągu Fibonacciego wystarczy rozważyć ciąg reszt \(\displaystyle{ F_k}\) przy dzieleniu przez \(\displaystyle{ n}\). Zapiszmy ten ciąg reszt jako \(\displaystyle{ (F'_k)}\).
Zauważmy teraz, że wszystkich możliwych par reszt \(\displaystyle{ (F'_k,F'_{k+1})}\) jest \(\displaystyle{ n^2}\) - bo reszt od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\) jest dokładnie \(\displaystyle{ n}\), a więc par mamy \(\displaystyle{ n^2}\). Skoro ciąg Fibonacciego jest nieskończony, a możliwych par skończenie wiele, ta sama para musi wystąpić po raz kolejny dla pewnej dalszej wartości \(\displaystyle{ k'>k}\) (tu jest moment, z którego korzystamy z zasady szufladkowej). Ponadto z określenia ciągu Fibonacciego, wartość \(\displaystyle{ F'_{k+2}}\) jest określona przez swoje dwie poprzednie wartości (czyli dokładnie parę \(\displaystyle{ (F'_k,F'_{k+1})}\)), co sprawia, że ciąg \(\displaystyle{ (F'_k)}\) jest okresowy.
Pozostaje połączyć teraz prosty fakt, że \(\displaystyle{ F'_0=0}\) oraz \(\displaystyle{ F'_1=1}\).
Reasumując, \(\displaystyle{ F'_0=0}\) oraz \(\displaystyle{ F'_1=1}\) oraz wykazana okresowość ciągu dowodzi, że znajdziemy \(\displaystyle{ F'_l=0}\), gdzie \(\displaystyle{ l>0}\) spełniający warunek \(\displaystyle{ n\,|\, F_l}\).
Swoją drogą, najmniejsza taka dodatnia liczba \(\displaystyle{ l}\) nosi nazwę
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Pisano_period