Mam problem ze zrozumieniem rekurencji. Czy mógłby wytłumaczyć mi ktoś krok po kroku jak dojść do rozwiązania, a mianowicie do wzoru na \(\displaystyle{ a_{n}}\) . na prostym przykładzie:
Ciąg {\(\displaystyle{ a _{n}}}\) jest taki że \(\displaystyle{ a _{0}= 1}\) , \(\displaystyle{ a _{n}= 3a _{n-1}-1}\)
Obliczyć np \(\displaystyle{ a _{5}}\) i znaleźć wzór na \(\displaystyle{ a _{n}}\)
i jeszcze pytanie czy \(\displaystyle{ a _{5} = 122}\) ??
Rekurencje I rzędu.
Rekurencje I rzędu.
Zastosuj pomysł podobny do równania różniczkowego liniowego z równaniem charakterystycznym i baza przestrzeni rozwiązań rekurencji jednorodnej w postaci ciągów geometrycznych. Rekurencje jednorodne omawiałem na przykładzie ciągu FIbonacci'ego jakieś pół roku temu. Tu dochodzi rozwiązanie szczególne rekurencji niejednorodnej, które można by znaleźć "metodą przewidywań".
Ukryta treść:
-
- Użytkownik
- Posty: 23
- Rejestracja: 7 lip 2011, o 18:28
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 4 razy
Rekurencje I rzędu.
W przypadku rekurencji najlepiej skorzystać z funkcji tworzących. Przyjmij, że \(\displaystyle{ f(x)= \sum_{0}^{ \infty } a_{n} x^{n}}\). Następnie przekształć tak ten szereg, aby można było za \(\displaystyle{ a _{n}}\) podstawić wzór rekurencyjny. Oblicz funkcję f(x), a następnie w odwrotną stronę - korzystając ze wzoru na sumę szeregu nieskończonego - znajdź szereg, którego sumą jest funkcja f(x). Ostatecznie porównaj pierwotny szereg z tym otrzymanym z f(x).
-
- 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
Rekurencje I rzędu.
Albo w ogóle z niczego prócz głowy nie korzystać:
Oznaczmy
\(\displaystyle{ b_n=a_{n+1}-a_n=(3a_{n}-1)-(3a_{n-1}-1)=3(a_n-a_{n-1})=3b_{n-1}}\)
czyli \(\displaystyle{ b_n}\) jest ciągiem geometrycznym o ilorazie \(\displaystyle{ 3}\), skąd
\(\displaystyle{ b_n=b_0\cdot 3^n=3^n}\)
wówczas:
\(\displaystyle{ a_n=a_0+\sum_{i=0}^{n-1}b_n=1+\sum_{i=0}^{n-1}3^i=1+\frac{3^n-1}{3-1}=\frac{3^n+1}2}\)
Oznaczmy
\(\displaystyle{ b_n=a_{n+1}-a_n=(3a_{n}-1)-(3a_{n-1}-1)=3(a_n-a_{n-1})=3b_{n-1}}\)
czyli \(\displaystyle{ b_n}\) jest ciągiem geometrycznym o ilorazie \(\displaystyle{ 3}\), skąd
\(\displaystyle{ b_n=b_0\cdot 3^n=3^n}\)
wówczas:
\(\displaystyle{ a_n=a_0+\sum_{i=0}^{n-1}b_n=1+\sum_{i=0}^{n-1}3^i=1+\frac{3^n-1}{3-1}=\frac{3^n+1}2}\)