Wzór ogólny z funkcji tworzących dla 3 cyfr

[Harry Xin]

Oznaczmy przez \(\displaystyle{ d_{n}}\) liczbę wszystkich ciągów długości \(\displaystyle{ n}\) o wyrazach ze zbioru \(\displaystyle{ \{0,1,2\}}\), w których nie występują ani dwie jedynki ani dwie dwójki pod rząd. Np. \(\displaystyle{ d_{3}=17}\), gdyż żądanymi ciągami są 000, 001, 002, 010, 012, 020, 021, 100, 101, 102, 120, 121, 200, 201, 202, 210, 212.
Znajdź wzór ogólny dla \(\displaystyle{ d_{n}}\), korzystając z metod funkcji tworzących.

Co wiem ponadto:
\(\displaystyle{ d_{0}=1, \ d_{1}=3, \ d_{2}=7, \ d_{3}=17, \ d_{4}=41, \ d_{5}=99,...}\)
Wzór rekurencyjny: \(\displaystyle{ d_{n+2}=2d_{n+1}+d_{n}}\)

[Szemek]

Na razie rozwiązanie bez funkcji tworzących - a właściwie to jest rozwiązanie równania rekurencyjnego. Jeśli uda mi się zrobić za pomocą funkcji tworzących to poniższe rozwiązanie będzie sprawdzeniem/potwierdzeniem wyniku.
\(\displaystyle{ x^2-2x-1=0 \\
\Delta_x = 8 \\
\sqrt{\Delta_x} = 2\sqrt{2} \\
x_1 = \frac{2-2\sqrt{2}}{2} \qquad x_2 = \frac{2+\sqrt{2}}{2} \\
x_1 = 1-\sqrt{2} \qquad x_2 = 1+\sqrt{2} \\
d_n = c_1 \cdot (1-\sqrt{2})^n + c_2 \cdot (1+\sqrt{2})^n \\
\begin{cases} 1 = c_1 + c_2 \\ 3 = c_1 (1-\sqrt{2}) + c_2 (1+\sqrt{2}) \end{cases} \\
\begin{cases} c_1 = \frac{1-\sqrt{2}}{2} \\ c_2 = \frac{1+\sqrt{2}}{2} \end{cases} \\
d_n = \frac{1-\sqrt{2}}{2} \cdot (1-\sqrt{2})^n + \frac{1+\sqrt{2}}{2} \cdot (1+\sqrt{2})^n \\
d_n = \frac{1}{2} \left[ (1-\sqrt{2})^{n+1} + (1+\sqrt{2})^{n+1} \right]}\)

[Harry Xin]

Tak już zdążyłem zrobić samemu. Mam nadzieję, że to tylko Twoja rozgrzewka przed zaprezentowaniem "chociaż wskazówki" co do funkcji tworzących i uda Ci się to zrobić.
Ja już nie mam za bardzo pomysłów.
A w ogóle można rekurencję wykorzystać? Kombinowałem z wyznaczeniem środkowego wyrazu i zapisanie po drugiej stronie średniej arytmetycznej wyrazów sąsiednich, ale niestety muszę jeszcze odjąć wyraz poprzedni...-- 4 kwietnia 2009, 21:27 --A coś takiego?
\(\displaystyle{ \begin{cases} a_{0}=1 \\ a_{1}=3 \\ a_{n}=2a_{n-1}+a_{n-2} \end{cases}}\)
Niech \(\displaystyle{ f\left(x\right)=\sum_{n=0}^{\infty}f_{n}x^{n}=1+3x+\sum_{n=2}^{\infty}\left(2f_{n-1}+f_{n-2}\right)x^{n}=1+3x+2xf\left(x\right)+x^{2}f\left(x\right)}\)
\(\displaystyle{ x^{2}f\left(x\right)+2xf\left(x\right)-f\left(x\right)=-1-3x}\)
\(\displaystyle{ f\left(x\right)\left(x^{2}+2x-1\right)=-1-3x}\)
\(\displaystyle{ f\left(x\right)=-\frac{\left(1+3x\right)}{x^{2}+2x-1}}\)
\(\displaystyle{ f\left(x\right)=\frac{A}{x+1-\sqrt{2}}+\frac{B}{x+1+\sqrt{2}}}\)

Mógłby ktoś sprawdzić mój tok rozumowania?

[Szemek]

pokażę, co wytworzyłem wczoraj,
to jest wersja robocza, nie mogę dopracować końcówki, bo mam jeszcze braki w szeregach z analizy

też na początku tak rozpisywałem, ale zauważyłem, że nie uwzględniłem kilku wyrazów z szeregu


\(\displaystyle{ F(x) = \sum_{i=0}^{\infty} d_i x^i = d_0 + d_1 x + \sum_{i=2}^{\infty} d_i x^i = 1+3x + \sum_{i=2}^{\infty} (2d_{i-1}+d_{i-2})x^i = \\
= 1+3x+2x \sum_{i=2}^{\infty} d_{i-1} x^{i-1} + x^2\sum_{i=2}^{\infty} d_{i-2} x^{i-2} = 1+3x+2x \sum_{i=1}^{\infty} d_{i} x^{i} + x^2\sum_{i=0}^{\infty} d_{i} x^{i} = \\
= 1 + 3x + 2x(F(x)-1)+x^2F(x)}\)

\(\displaystyle{ F(x) = 1 + x + 2xF(x)+x^2F(x) \\
F(x)[1-2x-x^2] = 1+x \\
F(x) = \frac{1+x}{1-2x-x^2} \\
\frac{1+x}{1-2x-x^2} = \frac{A}{1-(1-\sqrt{2})x} + \frac{B}{1-(1+\sqrt{2})x} \\
A = \frac{1-\sqrt{2}}{2} \qquad B = \frac{1+\sqrt{2}}{2} \end{cases}}\)

na wykładzie z dyskretnej pojawiło się coś takiego:
\(\displaystyle{ A = \frac{\alpha}{\alpha -\beta} \qquad B = \frac{-\beta}{\alpha - \beta}}\)
\(\displaystyle{ F(x) = \frac{A}{1-\alpha x} + \frac{B}{1- \beta x} = A \sum_{i=0}^{\infty} \alpha^i x^i + B \sum_{i=0}^{\infty} \beta^i x^i = \sum_{i=0}^{\infty} \frac{\alpha^{i+1}+\beta^{i+i}}{\alpha -\beta} x^i}\)

\(\displaystyle{ \frac{\frac{1-\sqrt{2}}{2}}{1-(1-\sqrt{2})x} = \frac{1-\sqrt{2}}{2} \sum_{i=0}^{\infty} (1-\sqrt{2})^i x^i}\)
\(\displaystyle{ \frac{\frac{1+\sqrt{2}}{2}}{1-(1+\sqrt{2})x} = \frac{1+\sqrt{2}}{2} \sum_{i=0}^{\infty} (1+\sqrt{2})^i x^i}\)
\(\displaystyle{ F(x) = \frac{1-\sqrt{2}}{2} \sum_{i=0}^{\infty} (1-\sqrt{2})^i x^i + \frac{1+\sqrt{2}}{2} \sum_{i=0}^{\infty} (1+\sqrt{2})^i x^i}\)

dobrze jakby jeszcze się ktoś włączył do pomocy,
będę także wdzięczny

[Harry Xin]

Mógłbyś sprecyzować o co chodzi z tymi kilkoma nieuwzględnionymi przeze mnie wyrazami z szeregu?
Tego z wykładu z dyskretnej nie rozumiem (jakie hasło googlować?) i nie wiem czego nie możesz dopracować przy końcówce - jak dla mnie wygląda OK. Już można zapisać wzór na ciąg...

[Szemek]

\(\displaystyle{ [..]=1+3x+\sum_{n=2}^{\infty}\left(2f_{n-1}+f_{n-2}\right)x^{n}= [..]}\)
wyciągam z tego wyrażenia
\(\displaystyle{ \sum_{n=2}^{\infty} 2f_{n-1}x^n = 2x\sum_{n=2 *}^{\infty}f_{n-1}x^{n-1} = ...}\)

rzućmy okiem na: \(\displaystyle{ f(x) = \sum_{n=0}^{\infty} f_n x^n \iff \sum_{n=1 *}^{\infty} f_{n-1} x^{n-1}}\)
gwiazdkami zaznaczyłem różnicę

zatem brakuje nam wyrazu dla n=1, żeby mieć pełną f(x)
\(\displaystyle{ ... = 2x[f(x)-1] = ...}\)

Niestety wykłady z matematyki dyskretnej na mojej uczelni nie są dostępne w wersji elektronicznej.

Ale przy rozwiązywaniu posiłkowałem się materiałami:
- plik w formacie *.ps, do obejrzenia np. w GSView

[url=http://www.math.ust.hk/~mabfchen/Math391I/Recurrence-Relation-Generating-Function.pdf]Recurrence Relations and Generating Functions[/url]

[Harry Xin]

No niby zszedłeś ze zliczaniem o oczko w dół. Tylko nie wiem czemu odejmujesz od funkcji wartość jeden wtedy, ale może jak się zapoznam z tymi materiałami to mi się trochę rozjaśni.
Ale zastanawia mnie bardziej jakim cudem dla drugiej sumy zrobiłeś taki trick, że zmieniłeś początkowe n a nie wpłynęło to w ogóle na wzór. o.O
Jakoś tak niekonsekwentnie jak dla mnie.

[Szemek]

No niby zszedłeś ze zliczaniem o oczko w dół. Tylko nie wiem czemu odejmujesz od funkcji wartość jeden wtedy, ale może jak się zapoznam z tymi materiałami to mi się trochę rozjaśni.
Ale zastanawia mnie bardziej jakim cudem dla drugiej sumy zrobiłeś taki trick, że zmieniłeś początkowe n a nie wpłynęło to w ogóle na wzór. o.O
Jakoś tak niekonsekwentnie jak dla mnie.

Dla jednej sumy skok o jedno oczko, dla drugiej o dwa.
Zajrzyj np. na stronę 5. pierwszy link.

Akurat ta faza rozwiązywania jest (jak dla mnie) ok.

Gorzej z końcówką, poszukam jeszcze jakichś materiałów, bo to, co tu umieściłem nie za bardzo mnie przekonuje.

[Rogal]

Z tego, co tutaj widzę, to raczej wszystko Szemku zrobiłeś jak najbardziej poprawnie (z dokładnością do obliczeń, ale wychodzi tak jak algebraicznymi metodami, więc zakładam, że rachunkowych błędów nie ma).
Rozumiem, że pomoc jest potrzebna by to dociągnąć do końca.
Zauważmy przecież, że można to sobie zrobić o tak:
\(\displaystyle{ F(x) = \frac{1}{2} \sum_{i=0}^{\infty} [(1-\sqrt{2})^{i+1} + (1+\sqrt{2})^{j+1}]x^{i} \\ \\ \sum_{i=0}^{\infty} d_{i} x^{i} = \sum_{i=0}^{\infty} \frac{1}{2}[(1-\sqrt{2})^{i+1} + (1+\sqrt{2})^{j+1}]x^{i}}\)
Z jednoznaczności rozwinięć w szereg Taylora otrzymujemy równość na wyrazach ciągów, czyli upragniony przez nas wzór jawny na d_i.
Jak coś, to mogę próbować tłumaczyć, czy też gdyby były wątpliwości natury teoretycznej (jakieś twierdzenia i takie tam), bo coś tam z analizy jeszcze pamiętam ;p

[Szemek]

Rogal, dzięki za to rozpisanie. Teraz widzę spójną i logiczną całość.

[bosa_Nike]

[...] Niestety wykłady z matematyki dyskretnej na mojej uczelni nie są dostępne w wersji elektronicznej.

Ale przy rozwiązywaniu posiłkowałem się materiałami: [...]

Wychodzi na to, że pierwszy i ostatni link to ten sam dokument.

[...] poszukam jeszcze jakichś materiałów [...]

Przydatna może być jeszcze Wilfa.

[Harry Xin]

Dziękuję wszystkim za pomoc.
Jako podsumowanie przedstawię w tym poście pełne rozwiązanie (wybrałem najprostszą drogę - bez tych ułamków jakie Szemek miał na wykładzie, więc mam nadzieję, że nie będzie to początkiem burzliwej dyskusji jak ta wczorajsza dotycząca języka C):

\(\displaystyle{ \begin{cases} d_{1}=3, \ d_{2}=7, \ d_{3}=17, \ ... \\ d_{n+2}=2d_{n+1}+d_{n} \end{cases}\Rightarrow d_{0}=1}\)

\(\displaystyle{ d_{n}=2d_{n-1}+d_{n-2}}\)

Niech \(\displaystyle{ f\left(x\right)=d_{0}+d_{1}x+d_{2}x^{2}+...}\)

\(\displaystyle{ f\left(x\right)=\sum_{i=0}^{\infty}d_{i}x^{i}=d_{0}+d_{1}x+\sum_{i=2}^{\infty}d_{i}x^{i}=1+3x+\sum_{i=2}^{\infty}\left(2d_{i-1}+d_{i-2}\right)x^{i}=1+3x+2x\sum_{i=2}^{\infty}d_{i-1}x^{i-1}+x^{2}\sum_{i=2}^{\infty}d_{i-2}x^{i-2}=1+3x+2x\sum_{i=1}^{\infty}d_{i}x^{i}+x^{2}\sum_{i=0}^{\infty}d_{i}x^{i}=1+3x+2x\left(f\left(x\right)-1\right)+x^{2}f\left(x\right)=1+3x+2xf\left(x\right)-2x+x^{2}f\left(x\right)}\)

\(\displaystyle{ f\left(x\right)=1+x+2xf\left(x\right)+x^{2}f\left(x\right)}\)

\(\displaystyle{ f\left(x\right)-2xf\left(x\right)-x^{2}f\left(x\right)=1+x}\)

\(\displaystyle{ f\left(x\right)\left[1-2x-x^{2}\right]=1+x}\)

\(\displaystyle{ f\left(x\right)=\frac{1+x}{1-2x-x^{2}}=\frac{A}{x-1-\sqrt{2}}+\frac{B}{x-1+\sqrt{2}}}\)

\(\displaystyle{ f\left(x\right)=\frac{\frac{1+\sqrt{2}}{2}}{x-1-\sqrt{2}}+\frac{\frac{1-\sqrt{2}}{2}}{x-1+\sqrt{2}}=\frac{1}{2}\left[\frac{1+\sqrt{2}}{x-\left(1+\sqrt{2}\right)}+\frac{1-\sqrt{2}}{x-\left(1-\sqrt{2}\right)}\right]}\)

\(\displaystyle{ f\left(x\right)=\frac{1}{2}\left[\left(1+\sqrt{2}\right)\sum_{i=0}^{\infty}\left(1+\sqrt{2}\right)^{i}x^{i}+\left(1-\sqrt{2}\right)\sum_{i=0}^{\infty}\left(1-\sqrt{2}\right)^{i}x^{i}\right]}\)

\(\displaystyle{ \sum_{i=0}^{\infty}d_{i}x^{i}=\sum_{i=0}^{\infty}\frac{1}{2}\left[\left(1+\sqrt{2}\right)^{i+1}+\left(1-\sqrt{2}\right)^{i+1}\right]x^{i}}\)

Stąd:

\(\displaystyle{ d_{n}=\frac{1}{2}\left[\left(1+\sqrt{2}\right)^{n+1}+\left(1-\sqrt{2}\right)^{n+1}\right]}\)