Wzór zwarty pewnej rekurencji
-
- 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
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 ?
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 ?
-
- 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
Gdzie zniknęła trójka przy \(\displaystyle{ A_{n-2}}\)?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}\)
Raczej mówi się: "rozwinąć w szereg".matinf pisze:Teraz powinniśmy zwinąć ten ułamek w szereg.
Nic nie stoi na przeszkodzie, żeby rozkładać na ułamki proste nad ciałem liczb zespolonych.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 ?
-
- 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
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)}}\)
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)}}\)
-
- 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
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.
- JakimPL
- 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
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}\).
\(\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}\).
-
- 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
\(\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!
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!
-
- 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
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ą.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!
- Mariusz M
- 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
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}\\}\)
\(\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}\\}\)
Czasem po skorzystaniu np ze wzoru de Moivre można się pozbyć zespolonychNic nie stoi na przeszkodzie, żeby rozkładać na ułamki proste nad ciałem liczb zespolonych.