Względna pierwszość liczb Fibonacciego.

[studciak123]

Wykaż, że dwie kolejne liczby Fibonacciego są względnie pierwsze.

[Premislav]

Zastosuj algorytm Euklidesa. Zauważ, że \(\displaystyle{ F_{n+1}-F_n=F_{n-1}}\) itd.

[studciak123]

Ok, zrobiłem indukcyjnie tak:
I Baza -- zgadza się dla dwóch pierwszych elementów ciągu Fibonacciego
II Krok indukcyjny:
\(\displaystyle{ F_{n} = a + b}\)
\(\displaystyle{ F_{n+1} = 2a + b}\)

Z algorytmu Euklidesa(wersja z odejmowaniem) dostałem:
\(\displaystyle{ NWD((2a+b),(a+b)) = ... = NWD(a,b)}\) -- a to są elementy dla których zachodzi założenie indukcyjne.

Może tak być?

[Premislav]

Jak najbardziej można indukcyjnie, jeszcze jak. Co to jest \(\displaystyle{ a}\)?
Na oko \(\displaystyle{ a=F_{n-1}, \ b=F_{n-2}}\)..
Wtedy jednak sprecyzuj schemat indukcji, którego używasz:
pokazujesz, że jeśli \(\displaystyle{ \NWD(F_{n-1}, F_{n-2})=1}\)
dla pewnego \(\displaystyle{ n \in \NN^+, \ n>2}\), to także \(\displaystyle{ \NWD(F_{n+1}, F_{n})=1}\). Czyli z prawdziwości \(\displaystyle{ T(n-2)}\) chcesz wywnioskować prawdziwość \(\displaystyle{ T(n)}\).

No i jeszcze o bazę indukcji trzeba zadbać. Z uwagi na powyższe trzeba sprawdzić dla dwóch małych \(\displaystyle{ n}\), a nie dla jednego.