Ciąg Fibbonaciego podzielność

[MaTTematyk]

Ciąg określony jest wzorem rekurencyjnym:

\(\displaystyle{ a _{1}= 1}\),\(\displaystyle{ a _{2}=1}\) , \(\displaystyle{ a _{n} = a _{n-2} + a _{n-1}}\) dla \(\displaystyle{ n \ge 3}\) . Wyznacz resztę z dzielenia przez \(\displaystyle{ 2}\) liczby \(\displaystyle{ a _{2008}}\).
Jak to ładnie zapisać dowód tego? Ja kombinowałem z dodawaniem liczb nieparzystych i parzystych, że co 3-cia liczba ciągu febbonaciego jest parzysta, ale jakoś nie podoba mi się moje rozwiązanie. Z czego skorzystać czy może moje myślenie jest dobre?

[matmatmm]

Twoje rozumowanie jest dobre. Jeśli chodzi o ładny zapis, to bym próbował indukcyjnie pokazać, że dla każdego \(\displaystyle{ k\in\NN}\) liczby \(\displaystyle{ a_{3k-2},a_{3k-1}}\) są nieparzyste i liczba \(\displaystyle{ a_{3k}}\) jest parzysta.

[MaTTematyk]

kurcze udowodniłem indukcyjnie że \(\displaystyle{ a _{3k}}\)jest podzielna przez 2 ale nie mogę sobie poradzić z tym ze \(\displaystyle{ a _{k-2}}\) jest nieparzysta a w moim przypadku \(\displaystyle{ a _{3k}}\) niewiele daje

[matmatmm]

Pokaż, jak to robisz, bo ja miałem na myśli dowód wszystkich trzech za jednym zamachem.
Przypadek \(\displaystyle{ k=1}\) oczywisty.
I potem ustalamy \(\displaystyle{ k \in\NN}\) i zakładamy, że \(\displaystyle{ a_{3k-2},a_{3k-1}}\) są nieparzyste oraz \(\displaystyle{ a_{3k}}\) jest parzysta.
No i mamy do pokazania, że \(\displaystyle{ a_{3k+1},a_{3k+2}}\) są nieparzyste i \(\displaystyle{ a_{3k+3}}\) jest parzysta.

[MaTTematyk]

\(\displaystyle{ f \left( 3k \right) = \frac{1}{\sqrt{5}} \left[ \left( 2+ \frac{18 \sqrt{5}}{8} \right) ^k - \left( 2- \frac{18 \sqrt{5}}{8} \right) ^k \right] = \\ = \frac{1}{\sqrt{5}} \left[ \left( 2 \left( 1+ \frac{9 \sqrt{5}}{8} \right) \right) ^k - \left( 2 \left( 1 - \frac{9 \sqrt{5}}{8} \right) \right) ^k \right] = \\ = \frac{1}{\sqrt{5}} \left[ 2^k \left( 1+ \frac{9 \sqrt{5}}{8} \right) ^k - 2^k \left( 1 - \frac{9 \sqrt{5}}{8} \right) ^k \right] = \\ = \frac{2^k}{\sqrt{5}} \left[ \left( 1+ \frac{9 \sqrt{5}}{8} \right) ^k - \left( 1 - \frac{9 \sqrt{5}}{8} \right) ^k \right]}\)
no i niby wyciągnięcie \(\displaystyle{ 2^{k}}\) załatwia sprawę ale teraz myślę jeszcze czy to w nawiasie jest liczbą naturalną...

[gryxon]

\(\displaystyle{ f(3k) = \frac{1}{\sqrt{5}}[ (2+ \frac{18 \sqrt{5}}{8})^k - (2- \frac{18 \sqrt{5}}{8})^k ] = \\ = \frac{1}{\sqrt{5}}[ (2(1+ \frac{9 \sqrt{5}}{8}))^k - (2(1 - \frac{9 \sqrt{5}}{8}))^k ] = \\ = \frac{1}{\sqrt{5}}[ 2^k(1+ \frac{9 \sqrt{5}}{8})^k - 2^k(1 - \frac{9 \sqrt{5}}{8})^k ] = \\ = \frac{2^k}{\sqrt{5}}[ (1+ \frac{9 \sqrt{5}}{8})^k - (1 - \frac{9 \sqrt{5}}{8})^k ]}\)
no i niby wyciągnięcie \(\displaystyle{ 2^{k}}\) załatwia sprawę ale teraz myślę jeszcze czy to w nawiasie jest liczbą naturalną...

na pewno nie jest :p
Gdyby tak było to \(\displaystyle{ f(3k)}\) byłoby liczbą niewymierną.

[MaTTematyk]

nie napisałem jeszcze pierwszej ważnej liniki sorki która wyjaśnia skąd to sie wzięło
\(\displaystyle{ f \left( 3k \right) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+ \sqrt{5} }{2} \right) ^{3k} - \left( \frac{1- \sqrt{5} }{2} \right) ^{3k} \right]}\)i ze wzorów skróconego mnożenia wychodzi to:
\(\displaystyle{ f \left( 3k \right) = \frac{1}{\sqrt{5}} \left[ \left( 2+ \frac{8 \sqrt{5}}{8} \right) ^k - \left( 2- \frac{8 \sqrt{5}}{8} \right) ^k \right] = \\ = \frac{1}{\sqrt{5}} \left[ \left( 2 \left( 1+ \frac{ \sqrt{5}}{2} \right) \right) ^k - \left( 2 \left( 1 - \frac{ \sqrt{5}}{2} \right) \right) ^k \right] = \\ = \frac{1}{\sqrt{5}} \left[ 2^k \left( 1+ \frac{ \sqrt{5}}{2} \right) ^k - 2^k \left( 1 - \frac{ \sqrt{5}}{2} \right) ^k \right] = \\ = \frac{2^k}{\sqrt{5}} \left[ \left( 1+ \frac{ \sqrt{5}}{2} \right) ^k - \left( 1 - \frac{ \sqrt{5}}{2} \right) ^k \right]}\)
podpowie ktoś w jaki sposób rozwiązac to zadanie indukcyjnie lub inaczej?

[gryxon]

Wiem skąd to się wzięło ale mówię Ci że to w nawiasie nie jest liczbą naturalną.
Nie jest nawet wymierną. ;p
EDIT:
Patrz dodaj sobie jeden element pomocniczy(jego dodanie nie wpływa na dalsze elementy) do twojego ciągu:
\(\displaystyle{ a_{0}=0 \\
a_{1}=1 \\
a_{2}=1 \\}\)
Teza indukcyjna:
\(\displaystyle{ 2|a_{3k}, \\ 2\not|a_{3k+1}, \\ 2\not|a_{3k+2}}\)

Dowód indukcyjny sam przeprowadź ;p

[pyzol]

Wiem skąd to się wzięło ale mówię Ci że to w nawiasie nie jest liczbą naturalną.
Nie jest nawet wymierną. ;p

Uważasz, że ten ciąg nie ma wyrazów naturalnych?-- 13 mar 2014, o 19:57 --MaTTematyk, skąd u ciebie \(\displaystyle{ 18\sqrt{5}}\)

[MaTTematyk]

ah sorki błąd w liczeniu już poprawiam

[pyzol]

Także gryxon też prawdę napisał :p
Pobaw się indukcją tak jak napisał...

[gryxon]

MaTTematyk napisał, że nie wie czy ten nawias jest naturalny (obliczeń nie sprawdzałem )

\(\displaystyle{ \left[ \left( 1+ \frac{ \sqrt{5}}{2} \right) ^k - \left( 1 - \frac{ \sqrt{5}}{2} \right) ^k \right]}\)

Powyższe wyrażenie nie jest wymierne.

[MaTTematyk]

Mógłby ktoś pomóc bo nie mogę sobie poradzić

[gryxon]

Dowód dla \(\displaystyle{ n=k+1}\) :

\(\displaystyle{ a_{3(k+1)}=a_{3k+3}=a_{3k+2}+a_{3k+1}

a_{3(k+1)+1}=a_{3k+4}=a_{3k+3}+a_{3k+2}

a_{3(k+1)+2}=a_{3k+5}=a_{3k+4}+a_{3k+3}}\)

Sprawdzasz kolejno podzielności tych wyrazów ciągu przez dwa.

[MaTTematyk]

I za te wyrazy mam podstawić ten wzór z \(\displaystyle{ \sqrt{5}}\)?