Wzór zwarty pewnej rekurencji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Wzór zwarty pewnej rekurencji

Post autor: matinf »

Witam,
Mamy taką rekurencję:
\(\displaystyle{ A_0 = 0 \\
A_1 = 1 \\
A_2 = 2 \\
A_n = A_{n-3} + 3A_{n-2} + A_{n-1}}\)


I ja będę to chciał najpierw tak zapisać:
\(\displaystyle{ A_n = A_{n-3} + 3A_{n-2} + A_{n-1} + [n=1] + [n=2]}\)
Następnie:
\(\displaystyle{ \sum_{n\in \ZZ} A_nx^n = x^3A(X) + x^2A(X) + xA(X) + x + x^2}\)
\(\displaystyle{ A(x) = \frac{x+x^2}{1-x^3-x^2-x}}\)
Tzn, że mamy już fcję tworzącą dla tego ciągu rekurencyjnego. Teraz powinniśmy zwinąć ten ułamek w szereg. W tym celu Należy rozłożyć na czynniki proste, - ale jak rozłożyć na te czynniki proste, jeśli nie ma rzeczywistych pierwiastków ?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wzór zwarty pewnej rekurencji

Post autor: norwimaj »

matinf pisze: \(\displaystyle{ A_n = A_{n-3} + 3A_{n-2} + A_{n-1} + [n=1] + [n=2]}\)
Następnie:
\(\displaystyle{ \sum_{n\in \ZZ} A_nx^n = x^3A(X) + x^2A(X) + xA(X) + x + x^2}\)
Gdzie zniknęła trójka przy \(\displaystyle{ A_{n-2}}\)?
matinf pisze:Teraz powinniśmy zwinąć ten ułamek w szereg.
Raczej mówi się: "rozwinąć w szereg".
matinf pisze:W tym celu Należy rozłożyć na czynniki proste, - ale jak rozłożyć na te czynniki proste, jeśli nie ma rzeczywistych pierwiastków ?
Nic nie stoi na przeszkodzie, żeby rozkładać na ułamki proste nad ciałem liczb zespolonych.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Wzór zwarty pewnej rekurencji

Post autor: matinf »

Jasne, to już nieaktualne

Mam inną fcję tworzącą, z której trzeba powrócić do świata ciągów, ale chyba zabłądziłem...
\(\displaystyle{ \frac{1}{2(-1+\sqrt{2}-x)} - \frac{1}{2(1+\sqrt{2} + x)}}\)
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wzór zwarty pewnej rekurencji

Post autor: norwimaj »

Wzór na sumę szeregu geometrycznego znasz, wiec w czym problem? Trzeba tylko znaleźć takie szeregi geometryczne, których sumy są równe tym ułamkom.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Wzór zwarty pewnej rekurencji

Post autor: matinf »

Chodzi Tobie o wzór:
\(\displaystyle{ S_n = a_1\frac{1-q^n}{1-q}}\)
?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wzór zwarty pewnej rekurencji

Post autor: norwimaj »

Chodziło mi o nieskończony szereg, czyli z \(\displaystyle{ n}\) musisz przejść do nieskończoności.
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Wzór zwarty pewnej rekurencji

Post autor: JakimPL »

Koniecznie trzeba taką metodą? Zadanie jest równoważne znalezieniu pierwiastków wielomianu trzeciego stopnia. Podstawienie \(\displaystyle{ A_n = t^n}\) skutkuje:

\(\displaystyle{ t^n = t^{n-3} + 3 t^{n-2} + t^{n-1}}\)

Dzielimy stronami:

\(\displaystyle{ t^3 = 1 + 3 t + t^2}\)

Otrzymujemy wielomian \(\displaystyle{ t^3-t^2-3t-1=0}\), który ma trzy różne pierwiastki (to jest istotne) \(\displaystyle{ t_1 = -1}\), \(\displaystyle{ t_2 = 1-\sqrt{2}}\), \(\displaystyle{ t_3=1+\sqrt{3}}\), a zatem

\(\displaystyle{ A_n = a_1(-1)^n + a_2\left(1-\sqrt{2}\right)^n + a_3\left(1+\sqrt{2}\right)^n}\)

Z "warunków początkowych" wyznaczamy stałe \(\displaystyle{ a_1}\), \(\displaystyle{ a_2}\) oraz \(\displaystyle{ a_3}\).
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Wzór zwarty pewnej rekurencji

Post autor: matinf »

\(\displaystyle{ \frac{1}{2(-1+\sqrt{2}-x)}}\)
To rozwinę w szereg i znajdę wyraz.

\(\displaystyle{ \frac{1}{2(-1+\sqrt{2}-x)}=\frac12\frac{1}{\sqrt2-1-x}=\left(\frac{1}{2(\sqrt2-1)}\cdot\frac{1}{1-\frac{x}{\sqrt2-1}}\right) = \frac{1}{2(\sqrt2-1)}\cdot\sum_{n=0}^{\infty}\left(\frac{x}{\sqrt2-1}\right)^n = \sum_{n=0}^{\infty}\frac{1}{2(\sqrt{2}-1)(\sqrt2-1)^n}x^n}\)

Tak więc znalazłem jeden z członów wyniku.

Wynosi on:
\(\displaystyle{ \frac{1}{2(\sqrt{2}-1)(\sqrt2-1)^n}}\)

Do tego należy dodać wynik, który otrzymamy robiąc to samo z drugim składnikiem fcji tworzącej.

Słusznie ? Bo ten "fragment" ciągu nie wygląda zbyt dobrze, wynikami powinny być liczby całkowite tego ciągu - a tu jakieś pierwiastki!
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wzór zwarty pewnej rekurencji

Post autor: norwimaj »

matinf pisze:Bo ten "fragment" ciągu nie wygląda zbyt dobrze, wynikami powinny być liczby całkowite tego ciągu - a tu jakieś pierwiastki!
To częste zjawisko przy rozwiązywaniu równań rekurencyjnych. Otrzymany wynik na pierwszy rzut oka nie wygląda na liczbę wymierną, czy nawet rzeczywistą, chociaż jest on liczbą naturalną.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Wzór zwarty pewnej rekurencji

Post autor: Mariusz M »

Skoro zaczął tą metodą to raczej musi być

\(\displaystyle{ a_0 = 0 \\
a_1 = 1 \\
a_2 = 2 \\
a_n = a_{n-3} + 3a_{n-2} + a_{n-1}}\)



\(\displaystyle{ \sum_{n=3}^{ \infty }{a_{n}x^{n}}=\sum_{n=3}^{\infty}{a_{n-1}x^{n}}+\sum_{n=3}^{\infty}{3a_{n-2}x^{n}}+ \sum_{n=3}^{\infty}{a_{n-3}x^{n}}\\
A\left( x\right)=\sum_{n=0}^{\infty}{a_{n}x^{n}} \\
\left( \sum_{n=0}^{ \infty }{a_{n}x^n}-x-2x^2 \right)=x\left( \sum_{n=3}^{ \infty }{a_{n-1}x^{n-1}} \right) +3x^2\left( \sum_{n=3}^{ \infty }{a_{n-2}x^{n-2}} \right)+x^3\left( \sum_{n=3}^{ \infty }{a_{n-3}x^{n-3}} \right) \\
\left( \sum_{n=0}^{ \infty }{a_{n}x^n}-x-2x^2 \right)=x\left( \sum_{n=2}^{ \infty }{a_{n}x^{n}} \right) +3x^2\left( \sum_{n=1}^{ \infty }{a_{n}x^{n}} \right)+x^3\left( \sum_{n=0}^{ \infty }{a_{n}x^{n}} \right) \\
\left( \sum_{n=0}^{ \infty }{a_{n}x^n}-x-2x^2 \right)=x\left( \sum_{n=0}^{ \infty }{a_{n}x^n}-x \right)+3x^2\left( \sum_{n=0}^{ \infty }{a_{n}x^{n}} \right)+x^3\left( \sum_{n=0}^{ \infty }{a_{n}x^{n}} \right) \\
A\left( x\right)-x-x^2=xA\left( x\right)-x^2+3x^2A\left( x\right)+x^3A\left( x\right)\\
A\left( x\right)\left( 1-x-3x^2-x^3\right)=x+x^2\\
A\left( x\right)=\frac{x+x^2}{1-x-3x^2-x^3}\\
A\left( x\right)=\frac{x\left( 1+x\right) }{\left(1+x\right)\left(1-2x-x^2\right)} \\
A\left( x\right)=\frac{x}{1-2x-x^2}\\
A\left( x\right)=\frac{x}{\left( 1-\left(1+ \sqrt{2} \right) x\right)\left( 1-\left(1-\sqrt{2} \right)x \right) }\\
\frac{p}{1-\left( 1+ \sqrt{2} \right)x }+\frac{q}{1-\left( 1- \sqrt{2} \right)x }=\frac{x}{1-2x-x^2}\\
p-\left( 1- \sqrt{2} \right)px+q-\left( 1+ \sqrt{2} \right)qx=0\\
\begin{cases} p+q=0 \\ -\left( 1- \sqrt{2} \right)p-\left( 1+ \sqrt{2} \right)q \end{cases} \\
\begin{cases} q=-p \\ -\left( 1- \sqrt{2} \right)p+\left( 1+ \sqrt{2} \right)p=1 \end{cases}\\
\begin{cases} q=-\frac{\sqrt{2}}{4} \\ p=\frac{\sqrt{2}}{4}\\ \end{cases} \\
A\left( x\right)= \frac{ \sqrt{2} }{4}\left( \sum_{n=0}^{ \infty }{\left( 1+ \sqrt{2} \right)^nx^n } \right)-\frac{ \sqrt{2} }{4}\left( \sum_{n=0}^{ \infty }{\left( 1- \sqrt{2} \right)^nx^n } \right)\\
a_{n}=\frac{ \sqrt{2} }{4}\left( 1+ \sqrt{2} \right)^n-\frac{ \sqrt{2} }{4}\left( 1- \sqrt{2} \right)^{n}\\}\)

Nic nie stoi na przeszkodzie, żeby rozkładać na ułamki proste nad ciałem liczb zespolonych.
Czasem po skorzystaniu np ze wzoru de Moivre można się pozbyć zespolonych
ODPOWIEDZ