Trzy operacje

Własności ciągów i zbieżność, obliczanie granic. Twierdzenia o zbieżności.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11264
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Trzy operacje

Post autor: mol_ksiazkowy »

Jak wyliczyć \(\displaystyle{ 2^n}\) ty wyraz ciągu Fibonacciego wykonując nie więcej niż \(\displaystyle{ 6n}\) operacji dodawania, odejmowania i mnożenia ?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Trzy operacje

Post autor: kerajs »

Znając trójkę \(\displaystyle{ F_{2^k-1} \ , \ F_{2^k} \ i \ F_{2^k+1}}\) można wyznaczyć trójkę \(\displaystyle{ F_{2 \cdot 2^k-1} \ , \ F_{2 \cdot 2^k} \ i \ F_{2 \cdot 2^k+1}}\) w 6 działaniach:
\(\displaystyle{ F_{2 \cdot 2^k}=F_{2^k}(F_{2^k-1} + F_{2^k+1})}\) (dodawanie i mnożenie)
\(\displaystyle{ F_{2 \cdot 2^k-1}=(F_{2^k-1})^2 + (F_{2^k})^2}\) (dwa mnożenia i dodawanie )
\(\displaystyle{ F_{2 \cdot 2^k+1}=F_{2 \cdot 2^k-1} + F_{2 \cdot 2^k}}\) (dodawanie)
ODPOWIEDZ