ciąg \Fibonacciego

[alfred0]

Może już był dowód tego twierdzenia ale nie mogę goznaleźć.
|Tw: jeśli numer n dzieli się przez k, to liczba \(\displaystyle{ F_n}\) dzieli się przez \(\displaystyle{ F_k.}\)

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego

[Premislav]

To ja od razu proponuję wykazać, że
\(\displaystyle{ \NWD(F_k,F_n)=F_{\NWD(k,n)}}\)

Można również na chama zastosować wzór Bineta i wzór na różnicę p-tych potęg, gdzie bierzemy \(\displaystyle{ p= \frac{n}{k}}\)

[alfred0]

To ja od razu proponuję wykazać, że
\(\displaystyle{ \NWD(F_k,F_n)=F_{\NWD(k,n)}}\)

a jak to pokazac?

[dec1]

To może tak:

Lematy:
1) \(\displaystyle{ F_n}\) i \(\displaystyle{ F_{n+1}}\) są względnie pierwsze
2) \(\displaystyle{ F_{a+b}=F_aF_{b-1}+F_bF_{a+1}}\)

Stąd \(\displaystyle{ \mathrm{NWD}(F_a, F_b)=\mathrm{NWD}(F_a, F_{b-a})}\)

Teraz rekurencja (podobna do algorytmu Euklidesa, tylko zamiast liczby mamy indeks w ciągu Fibonacciego) i koniec

Używając mojego drugiego lematu można też naszą tezę wykazać indukcyjnie

[bakala12]

dec1, masz błąd oczywiście.
Powinno być:
\(\displaystyle{ F_{a+b} = F_{a}F_{b-1} + F_{a+1}F_{b}}\)

[dec1]

Racja, dzięki