Rekurencje I rzędu.

[krolik14p]

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}\) ??

[Xitami]

Kod: Zaznacz cały

http://oeis.org/A007051

[szw1710]

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ść:    

\(\displaystyle{ a_n=\frac{1}{2}(3^n+1).}\) Twoja odpowiedź jest poprawna.

[Mores]

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).

[xiikzodz]

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}\)