Dokaz da su susedni Fibonačijevi brojevi uzajamno prosti
- Преузми линк
- X
- Имејл адреса
- Друге апликације
Pozdrav svima. Danas ćemo dokazati da su susedni Fibonačijevi brojevi uzajamno prosti. Kao dokazni metod koristićemo metod matematičke indukcije.
Teorema: Neka \(F_n\) predstavlja n-ti Fibonačijev broj. Tada važi: \[\forall n \ge 2 , \quad \operatorname{NZD}\left(F_n,F_{n+1}\right)=1\]
Dokaz:
1. Baza indukcije (n=2)
\[\operatorname{NZD}\left(F_2,F_{3}\right)=\operatorname{NZD}(1,2)=1\]
2. Induktivna hipoteza (n=m)
Pretpostavimo da važi:
\[\operatorname{NZD}\left(F_m,F_{m+1}\right)=1\]
3. Induktivni korak (n=m+1)
Koristeći pretpostavku iz drugog koraka dokažimo da važi:
\[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=1\]
Kako je najveći zajednički delilac bilo kojih prirodnih brojeva \(a\) i \(b\) jednak najvećem zajedničkom deliocu bilo koje linearne kombinacije brojeva \(a\) i \(b\) imamo da je \(\operatorname{NZD}(a,b)=\operatorname{NZD}(a,b-a)\) . Imajući ovo u vidu možemo zapisati sledeću jednakost: \[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m+1},F_{m+2}-F_{m+1}\right)\]
Dalje, kako je po definiciji Fibonačijevog niza \(F_{m+2}=F_{m}+F_{m+1}\) imamo da je: \[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m+1},F_{m}\right)\]\[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m},F_{m+1}\right)=1\]
\(\blacksquare\)
- Преузми линк
- X
- Имејл адреса
- Друге апликације
Коментари
Постави коментар