ciąg Fibonacciego
-
wiosna
- Użytkownik
- Posty: 98
- Rejestracja: 2 maja 2008, o 14:01
- Płeć: Kobieta
- Lokalizacja: poznań
- Podziękował: 20 razy
- Pomógł: 1 raz
ciąg Fibonacciego
Jak udowodnić, że w ciągu Fibonacciego \(\displaystyle{ F _{n}}\) istnieje \(\displaystyle{ a}\) takie, że \(\displaystyle{ F _{a}}\) jest podzielne przez 2009?
-
Piotr Rutkowski
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
ciąg Fibonacciego
Udowodnimy dużo mocniejsze twierdzenie:
\(\displaystyle{ \forall_{k\in \mathbb{N}}\exists_{a\in \mathbb{N}} \ k|F_{a}}\)
Weźmy naszą liczbę naturalną \(\displaystyle{ k}\)
Rozważmy ciąg \(\displaystyle{ a_{n}}\) będący ciągiem reszt z dzielenia \(\displaystyle{ F_{n}}\) przez k.
Rozważmy też ciąg par kolejnych wyrazów ciągu \(\displaystyle{ b_{n}=\{a_{n},a_{n+1}\}}\)
Z dokładnością co do kolejności para wyrazów \(\displaystyle{ a_[n},a_{n+1}}\) może przyjmować co najwyżej \(\displaystyle{ n^{2}}\) różnych wartości. Oczywiście ciąg \(\displaystyle{ b_{n}}\) jest nieskończony, zatem z zasady szufladkowej Dirichleta otrzymujemy:
\(\displaystyle{ \exists_{l\in \mathbb{N}} \ b_{n}=b_{n+l}}\)
Zatem \(\displaystyle{ ((1) \ a_{n+1}=a_{n+l+1})\wedge ((2) \ a_{n}=a_{n+l})}\)
Pokażemy, że takie \(\displaystyle{ l}\) spełnia warunek \(\displaystyle{ a_{l}=0}\)
Najpierw udowodnijmy, że \(\displaystyle{ \forall_{c\in \{1,2,...,n\}}a_{n-c}=a_{n+l-c}}\)
Jest to oczywisty fakt, który otrzymujemy po odjęciu stronami naszych równań \(\displaystyle{ (1)-(2)}\)
Dostajemy \(\displaystyle{ (3)\ a_{n-1}=a_{n+l-1}}\). I tak po \(\displaystyle{ c-1}\) krokach polegających na tworzeniu i odejmowaniu równań stronami \(\displaystyle{ (1)-(2),(2)-(3),...,(c-2)-(c-1)}\) otrzymujemy naszą tezę. Wstawiając \(\displaystyle{ c=n}\) otrzymujemy \(\displaystyle{ a_{0}=a_{n-n}=a_{n+l-n}=a_{l}}\) co dowodzi postulowanej tezy i kończy zadanie
Q.E.D.
\(\displaystyle{ \forall_{k\in \mathbb{N}}\exists_{a\in \mathbb{N}} \ k|F_{a}}\)
Weźmy naszą liczbę naturalną \(\displaystyle{ k}\)
Rozważmy ciąg \(\displaystyle{ a_{n}}\) będący ciągiem reszt z dzielenia \(\displaystyle{ F_{n}}\) przez k.
Rozważmy też ciąg par kolejnych wyrazów ciągu \(\displaystyle{ b_{n}=\{a_{n},a_{n+1}\}}\)
Z dokładnością co do kolejności para wyrazów \(\displaystyle{ a_[n},a_{n+1}}\) może przyjmować co najwyżej \(\displaystyle{ n^{2}}\) różnych wartości. Oczywiście ciąg \(\displaystyle{ b_{n}}\) jest nieskończony, zatem z zasady szufladkowej Dirichleta otrzymujemy:
\(\displaystyle{ \exists_{l\in \mathbb{N}} \ b_{n}=b_{n+l}}\)
Zatem \(\displaystyle{ ((1) \ a_{n+1}=a_{n+l+1})\wedge ((2) \ a_{n}=a_{n+l})}\)
Pokażemy, że takie \(\displaystyle{ l}\) spełnia warunek \(\displaystyle{ a_{l}=0}\)
Najpierw udowodnijmy, że \(\displaystyle{ \forall_{c\in \{1,2,...,n\}}a_{n-c}=a_{n+l-c}}\)
Jest to oczywisty fakt, który otrzymujemy po odjęciu stronami naszych równań \(\displaystyle{ (1)-(2)}\)
Dostajemy \(\displaystyle{ (3)\ a_{n-1}=a_{n+l-1}}\). I tak po \(\displaystyle{ c-1}\) krokach polegających na tworzeniu i odejmowaniu równań stronami \(\displaystyle{ (1)-(2),(2)-(3),...,(c-2)-(c-1)}\) otrzymujemy naszą tezę. Wstawiając \(\displaystyle{ c=n}\) otrzymujemy \(\displaystyle{ a_{0}=a_{n-n}=a_{n+l-n}=a_{l}}\) co dowodzi postulowanej tezy i kończy zadanie
Q.E.D.