Własność ciągu Fibonacci'ego

Poszukujaca · Post autor: **Poszukujaca** » 10 sie 2016, o 20:05

Czy ktoś słyszał tutaj o własności ciągu Fibonacci'ego, która mówi o tym, że jeżeli \(\displaystyle{ U_n}\) jest jego n- tym wyrazem, \(\displaystyle{ n, m \in \NN}\), to \(\displaystyle{ (U_n, U_m)= U_{(n,m)}}\).

Czy ktoś zna jej dowód?

dec1 · Post autor: **dec1** » 10 sie 2016, o 20:14

Hint:
Udowodnij takie dwa lematy:
1) \(\displaystyle{ F_n}\) i \(\displaystyle{ F_{n+1}}\) są względnie pierwsze.
2) \(\displaystyle{ F_{n+m}=F_nF_{m-1}+F_mF_{n+1}}\)

bartek118 · Post autor: **bartek118** » 10 sie 2016, o 21:06

A z tych lematów, działa to dokładnie tak jak algorytm Euklidesa.

Poszukujaca · Post autor: **Poszukujaca** » 10 sie 2016, o 23:07

Dzięki za wskazówki, spróbuje się tym pobawić