\(\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źć...
NWD i ciąg Fibonacciego
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
NWD i ciąg Fibonacciego
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}}\)
\(\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}}\)
NWD i ciąg Fibonacciego
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
Może jednak komuś się uda
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
NWD i ciąg Fibonacciego
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.
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.
-
- Użytkownik
- Posty: 78
- Rejestracja: 24 lis 2009, o 17:22
- Płeć: Mężczyzna
- Podziękował: 4 razy
NWD i ciąg Fibonacciego
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)}\)
?
\(\displaystyle{ \left( f_{t}, f _{u}f _{t-1} \right) \stackrel{1}{=} \left( f_{t}, f _{u} \right)}\)
?