Ciąg Fibonacciego
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Rozkręcam się
- Posty: 49
- Rejestracja: 05 maja 2020, 16:38
- Podziękowania: 4 razy
- Otrzymane podziękowania: 9 razy
- Płeć:
Re: Ciąg Fibonacciego
1. Zauważmy że dla dowolnych względnie pierwszych \(a_1 , a_2\) liczby \(a_1 + a_2\) i \(a_2\) są względnie pierwsze
Dowód:
Załóżmy że \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze.
Jeśli \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze to istnieje takie \(k \in Z_+ , k \neq 1\) że \(k|a_2 \) oraz \(k|a_1 + a_2 \)
Zatem możemy zapisać że:
\(a_2 = lk\)
\(a_1 + a_2 = mk\)
gdzie \(m \in Z_+ , m \neq 1\), \(l \in Z_+ , l \neq 1\)
Zatem:
\(a_1 + a_2 = mk\)
\(a_1 + l * k = mk\)
\(a_1 = mk-lk = k(m-l) \to k|a_1\)
Więc \(NWD(a_1 , a_2 ) \neq 1\) a zatem \(a_1\) i \(a_2 \) nie są względnie pierwsze
2. Określmy ciąg Fibonnaciego jako:
\(a_1 = 1\)
\(a_2 = 1\)
\( a_{n+2}=a_{n+1}+a_{n}\)
Oczywiście \(NWD(a_1 , a_2 ) = 1\) więc \(a_1\), \(a_2\) są względnie pierwsze a co za tym idzie poprzez indukcje wszystkie pozostałe wyrazy ciągu Fibonnacciego
Dowód:
Załóżmy że \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze.
Jeśli \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze to istnieje takie \(k \in Z_+ , k \neq 1\) że \(k|a_2 \) oraz \(k|a_1 + a_2 \)
Zatem możemy zapisać że:
\(a_2 = lk\)
\(a_1 + a_2 = mk\)
gdzie \(m \in Z_+ , m \neq 1\), \(l \in Z_+ , l \neq 1\)
Zatem:
\(a_1 + a_2 = mk\)
\(a_1 + l * k = mk\)
\(a_1 = mk-lk = k(m-l) \to k|a_1\)
Więc \(NWD(a_1 , a_2 ) \neq 1\) a zatem \(a_1\) i \(a_2 \) nie są względnie pierwsze
2. Określmy ciąg Fibonnaciego jako:
\(a_1 = 1\)
\(a_2 = 1\)
\( a_{n+2}=a_{n+1}+a_{n}\)
Oczywiście \(NWD(a_1 , a_2 ) = 1\) więc \(a_1\), \(a_2\) są względnie pierwsze a co za tym idzie poprzez indukcje wszystkie pozostałe wyrazy ciągu Fibonnacciego
Pozdrawiam
Sciurius
Sciurius