NWD i ciąg Fibonacciego

[frej]

\(\displaystyle{ (F_n, F_m)=F_{(n,m)}}\)
\(\displaystyle{ F_{n+1} F_m +F_n F_{m-1}=F_{n+m}}\)

Pewnie jakoś indukcyjnie pójdzie, ale mam niestety małe doświadczenie z ciągiem Fibonacciego i nie wiem jak to ugryźć...

[Sylwek]

Co do drugiego zadania wystarczy zrobić dwie indukcje: po zmiennej n i po zmiennej m. Przykładowo krok po zmiennej n:

\(\displaystyle{ F_{n+2}F_m + F_{n+1}F_{m-1}=(F_{n+1}F_m + F_n F_{m-1}) + (F_{n} F_{m} + F_{n-1} F_{m-1}) = \\ = F_{n+m}+F_{n+m-1}=F_{n+m+1}}\)

[frej]

Ok, dzięki. Pierwsza równość jest ogólnie znana, ale niestety jakoś nie mogłem znaleźć w necie dowodu...
Może jednak komuś się uda

[xiikzodz]

Kroki:

1

\(\displaystyle{ (f_n,f_{n+1})=1}\)

2

\(\displaystyle{ f_{t+u}=f_tf_{u-1}+f_uf_{t-1}}\)

3

\(\displaystyle{ (f_t, f_{t+u}) =
(f_t, f_tf_{u-1} + f_uf_{t-1}) =
(f_t, f_uf_{t-1}) \stackrel{1}{=}
(f_t, f_u)}\)

4. Argument konczy algorytm Euklidesa.

Powinno byc jasne teraz.

[Sylwek]

Bardzo fajny dowód

[frej]

Wielkie dzięki.

[szymonides]

Mógłby ktoś wyjaśnić ostatnie przejście:

\(\displaystyle{ \left( f_{t}, f _{u}f _{t-1} \right) \stackrel{1}{=} \left( f_{t}, f _{u} \right)}\)

?

[Ponewor]

Korzysta się tu z pierwszego kroku w tamtym rozumowaniu.