Podzielność w ciągu Fibonacciego

[matematykapj]

Witam, mam takie zadanie:
Udowodnij stosując zasadę indukcji matematycznej, że ciąg Fibonacciego \(\displaystyle{ F(0)=0, F(1)=1}\) i \(\displaystyle{ F(n)=F(n-1)+F(n-2)}\) dla \(\displaystyle{ n>1}\), posiada następującą właściwość: jeśli \(\displaystyle{ 2|F(n)}\), to \(\displaystyle{ 3|n}\).

Nie wiem kompletnie jak się do tego zabrać, przekopałem internet i nie znalazłem nic. Z góry dziękuje za pomoc

[Jan Kraszewski]

A samemu próbowałeś?

Tak naprawdę prawdziwa jest silniejsza własność: \(\displaystyle{ (\forall n\in\NN)(2\mid F(n) \Leftrightarrow 3\mid n).}\)

Można to robić różnie: nie wprost, korzystając z Zasady Minimum albo zauważyć, że powyższa własność jest równoważna takiej

\(\displaystyle{ (\forall k\in\NN)(2\mid F(3k)\land 2\nmid F(3k+1)\land 2\nmid F(3k+2)),}\)

którą to własność dowodzimy indukcyjnie według schematu

\(\displaystyle{ \varphi(o)\land\varphi(1)\land(\forall k\in\NN)(\varphi(k)\land\varphi(k+1) \Rightarrow \varphi(k+2)) \Rightarrow (\forall k\in\NN)\varphi(k)}\)

albo jeszcze inaczej.

JK

[matematykapj]

Rozpisałem sobie klasycznie przykład, załozenie, teze dla \(\displaystyle{ n=k+1}\) ale w dowodzie się zatrzymałem i kompletnie nie wiem jak ruszyc, to co Pan napisał jest dla mnie troche niezrozumiałe

[Premislav]

Ogólnie \(\displaystyle{ \NWD(F_m, F_n)=F_{NWD(m,n)}}\), tutaj wystarczy wziąć \(\displaystyle{ n=3}\).

Por.

Kod: Zaznacz cały

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

[Jan Kraszewski]

Rozpisałem sobie klasycznie przykład, załozenie, teze dla \(\displaystyle{ n=k+1}\) ale w dowodzie się zatrzymałem i kompletnie nie wiem jak ruszyc,

Bo klasyczna indukcja tu nie wystarczy. Napisałem, że niezbędny jest inny schemat indukcji:

\(\displaystyle{ \varphi(0)\land\varphi(1)\land(\forall k\in\NN)(\varphi(k)\land\varphi(k+1) \Rightarrow \varphi(k+2)) \Rightarrow (\forall k\in\NN)\varphi(k)}\)

czyli w kroku bazowym musisz sprawdzić tezę dla \(\displaystyle{ n=0}\) i \(\displaystyle{ n=1}\), a w kroku indukcyjnym ustalić dowolne \(\displaystyle{ n}\) i założyć prawdziwość własności dla \(\displaystyle{ n}\) i \(\displaystyle{ n+1}\), a potem wywnioskować stąd prawdziwość własności dla \(\displaystyle{ n+2}\).

to co Pan napisał jest dla mnie troche niezrozumiałe

A konkretnie?

Ogólnie \(\displaystyle{ \NWD(F_m, F_n)=F_{NWD(m,n)}}\), tutaj wystarczy wziąć \(\displaystyle{ n=3}\).

Ha, ha.
O ile wcześniej dowiedziesz tę ogólniejszą własność...

JK

[Premislav]

Podałem link do miejsca, w którym zostało to zrobione. Chyba lepiej udowadniać ogólniejsze własności niż jakieś szczególne przypadki?

[Jan Kraszewski]

Podałem link do miejsca, w którym zostało to zrobione.

Słusznie.

Chyba lepiej udowadniać ogólniejsze własności niż jakieś szczególne przypadki?

To zależy.

JK

[a4karo]

A ja mam taki pomysł: Niech \(\displaystyle{ F(1)=F(2)=1}\) i \(\displaystyle{ Q(n)=\frac{2}{\sqrt{3}}\sin\left(\frac{2n\pi}{3}\right)}\)

Pokażemy, że wszystkie wyrazy ciągu \(\displaystyle{ F(n)-Q(n)}\) są parzyste.

Łatwo sprawdzamy, że teza jest prawdziwa dla \(\displaystyle{ n=1,2}\)

\(\displaystyle{ F(n+1)-Q(n+1)=F(n)+F(n-1)-\frac{2}{\sqrt{3}}\sin\left(\frac{2(n+1)\pi}{3}\right)\\
=F(n)+F(n-1)-\frac{2}{\sqrt{3}}\left[\sin\left(\frac{2n\pi}{3}\right)\cos\left(\frac{2\pi}{3}\right)+\cos\left(\frac{2n\pi}{3}\right)\sin\left(\frac{2\pi}{3}\right)\right]\\
=F(n)+F(n-1)-\frac{2}{\sqrt{3}}\left[-\sin\left(\frac{2n\pi}{3}\right)-\sin\left(\frac{2n\pi}{3}\right)\cos\left(\frac{2\pi}{3}\right)+\cos\left(\frac{2n\pi}{3}\right)\sin\left(\frac{2\pi}{3}\right)\right]\\
=F(n)+F(n-1)-\frac{2}{\sqrt{3}}\left[-\sin\left(\frac{2n\pi}{3}\right)-\sin\left(\frac{2(n-1)\pi}{3}\right)\right]\\
=F(n)+Q(n)+F(n-1)+Q(n-1)=F(n)-Q(n)+F(n-1)-Q(n-1)+2Q(n)+2Q(n-1)}\)
jest parzyste na mocy zasady indukcji