Wyznaczyć wzór jawny ciągu określonego wzorem rekurencyjnym:
\(\displaystyle{ a_{1}=1, a_{n}=2a_{\left\lfloor \frac{n}{2} \right\rfloor}}\)
Wzór jawny ciągu rekurencyjnego
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Wzór jawny ciągu rekurencyjnego
Wystarczy wypisać sobie parę pierwszych wyrazów, by odgadnąć, że dla \(\displaystyle{ n}\) z przedziału \(\displaystyle{ left[ 2^k, 2^{k+1}
ight)}\) jest \(\displaystyle{ a_n = 2^k}\). Nietrudno stąd wyznaczyć, że w takim razie:
\(\displaystyle{ a_n = 2^{ \left\lfloor \lg n \right\rfloor}}\)
Ogólniejszą metodę (dla ogólniejszych rekurencji tego typu, w szczególności zaś dla rekurencji Flawiusza) można znaleźć w pierwszym rozdziale Matematyki konkretnej.
Q.
ight)}\) jest \(\displaystyle{ a_n = 2^k}\). Nietrudno stąd wyznaczyć, że w takim razie:
\(\displaystyle{ a_n = 2^{ \left\lfloor \lg n \right\rfloor}}\)
Ogólniejszą metodę (dla ogólniejszych rekurencji tego typu, w szczególności zaś dla rekurencji Flawiusza) można znaleźć w pierwszym rozdziale Matematyki konkretnej.
Q.