Znaleźć wzór rekurencyjny ciągu

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
dom1ns00
Rozkręcam się
Rozkręcam się
Posty: 36
Rejestracja: 07 lut 2020, 19:19
Podziękowania: 14 razy
Płeć:

Znaleźć wzór rekurencyjny ciągu

Post autor: dom1ns00 »

Znaleźć wzór rekurencyjny ciągu, który ma funkcję tworzącą:
\( \frac{x^2}{(1-x-x^2)}\)
Awatar użytkownika
panb
Expert
Expert
Posty: 5122
Rejestracja: 26 kwie 2010, 22:54
Lokalizacja: Nowiny Wielkie
Podziękowania: 19 razy
Otrzymane podziękowania: 2053 razy
Płeć:

Re: Znaleźć wzór rekurencyjny ciągu

Post autor: panb »

dom1ns00 pisze: 01 cze 2020, 23:34 Znaleźć wzór rekurencyjny ciągu, który ma funkcję tworzącą:
\( \frac{x^2}{(1-x-x^2)}\)
\( C(x)=\frac{x^2}{1-x-x^2}= -1 + \frac{1-x}{1-x-x^2} =A(x)+B(x)\)
Jeśli \(\displaystyle C(x)= \sum_{n=0}^{\infty}c_n, \,\,\, A(x)=\sum_{n=0}^{\infty}a_n, \text{ i } B(x)=\sum_{n=0}^{\infty}b_n\) są funkcjami tworzącymi, to \(c_n=a_n+b_n\) jest szukanym ciągiem. Ciągi \(a_n\) i \(b_n\) możemy określić wzorami rekurencyjnymi:
\( \begin{cases}a_0=-1\\a_n=0&dla&n\ge1 \end{cases} \) - chyba nie trzeba tego specjalnie uzasadniać. \( \begin{cases}b_0=1\\b_1=0\\b_n=b_{n-1}+b_{n-2}&dla& n\ge2 \end{cases} \) to trzeba uzasadnić.

Niech \(\displaystyle { B(x)=\sum_{n=0}^{\infty}b_n=b_0+b_1x+ \sum_{n=2}^{\infty}b_{n}x^n =1+\sum_{n=2}^{\infty}(b_{n-1}+b_{n-2})x^n=1+\sum_{n=2}^{\infty}b_{n-1}x^n+\sum_{n=2}^{\infty}b_{n-2}x^n =\\\qquad =
1+x\sum_{n=2}^{\infty}b_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}b_{n-2}x^{n-2} =1+x\sum_{n=1}^{\infty}b_{n}x^n +x^2\sum_{n=0}^{\infty}b_{n}x^n=\\\qquad =
1+x \left(\sum_{n=0}^{\infty}b_{n}x^n -b_0x^0\right) +x^2B(x)=1-x+xB(x)+x^2B(x)}\)


Czyli \(B(x)=1-x+xB(x)+x^2B(x) \So B(x)= \frac{1-x}{1-x-x^2} \) co właśnie chcieliśmy uzasadnić.

Mamy więc \(c_n=a_n+b_n\):
\(\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
a_n:&-1&0&0&0&0&0&\ldots\\
\hline
b_n:&1&0&1&1&2&3&\ldots\\
\hline
c_n:&0&0&1&1&2&3&\ldots \\
\hline
\end{array}\\
\)


Odpowiedź: \( \frac{x^2}{1-x-x^2} \) jest funkcją tworzącą ciągu określonego rekurencyjnie:
\[ \begin{cases} a_0=0\\a_1=0\\a_2=1\\a_n=a_{n-2}+a_{n-1}&dla &n\ge 3\end{cases} \]

Uff!!
dom1ns00
Rozkręcam się
Rozkręcam się
Posty: 36
Rejestracja: 07 lut 2020, 19:19
Podziękowania: 14 razy
Płeć:

Re: Znaleźć wzór rekurencyjny ciągu

Post autor: dom1ns00 »

Dziękuję, wszytko jasno i przejrzyście wytłumaczone! :)
ODPOWIEDZ