Wyznaczanie wzoru ogólnego ciągu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
joanna_
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 4 wrz 2007, o 23:43
Płeć: Kobieta
Lokalizacja: Słupsk
Podziękował: 1 raz
Pomógł: 1 raz

Wyznaczanie wzoru ogólnego ciągu

Post autor: joanna_ » 4 wrz 2007, o 23:58

Będę niezmiernie wdzięczna za pomoc/wskazówkę odnośnie rozwiązywania zadań typu:

Wyznacz wzór zwarty na an, gdzie
\(\displaystyle{ a_1 = a_3\\
a_2 = -2\\
a_n = a_{n-1} + 2 a_{n-2} + 6 n - 15}\)


Wzór jest na tyle skomplikowany, że nie sposób odgadnąć wyrażenia na an , nie można też skorzystać z równania charakterystycznego, próbowałam dostrzec jakąś analogie przy rozwijaniu poszczególnych wyrazów ciągu, ale to również nie pomogło, co poradzicie?
z góry dziękuję

Zapis poprawiłem, zapoznaj się z http://matematyka.pl/viewtopic.php?t=28951
luka52
Ostatnio zmieniony 5 wrz 2007, o 00:02 przez joanna_, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

Wyznaczanie wzoru ogólnego ciągu

Post autor: max » 5 wrz 2007, o 13:14

A z metody funkcji tworzących można korzystać?
Ale w sumie nie ma po co:
\(\displaystyle{ a_{n + 2} = a_{n + 1} + 2a_{n} + 6(n + 2) - 15\\
a_{n + 2} + a_{n + 1} = 2a_{n + 1} + 2a_{n} + 6n - 3}\)

i teraz oznaczamy sobie \(\displaystyle{ \alpha_{n} = a_{n + 1} + a_{n}}\)
a nasze równanie przyjmuje postać:
\(\displaystyle{ \alpha_{n + 1} = 2\alpha_{n} + 6n - 3\\
_{n + 1} - 2\alpha_{n} = 6n - 3}\)

Dalej bierzemy wszystkie takie równości począwszy od \(\displaystyle{ n}\) i na \(\displaystyle{ 1}\) skończywszy, wymnażając każdą kolejną stronami przez kolejną potęgę \(\displaystyle{ 2}\):
\(\displaystyle{ \begin{cases}\alpha_{n + 1} - 2\alpha_{n} = 6n - 3\\
2\alpha_{n} - 4\alpha_{n - 1} = 2\cdot 6(n - 1) - 2\cdot 3\\
4\alpha_{n - 1} - 8\alpha_{n - 2} = 4\cdot 6(n - 2) - 4\cdot 3\\
\ldots\\
2^{n - 2}\alpha_{3} - 2^{n - 1}\alpha_{2} = 2^{n - 2}\cdot 6(n - (n - 2)) - 2^{n - 2}\cdot 3\\
2^{n - 1}\alpha_{2} - 2^{n}\alpha_{1} = 2^{n - 1}\cdot 6(n - (n - 1)) - 2^{n - 1}\cdot 3\end{cases}}\)

i teraz jak dodamy do siebie wszystkie równania układu to, po redukcji wyrazów podobnych po lewej stronie i pogrupowaniu strony prawej otrzymamy:
\(\displaystyle{ \alpha_{n + 1} + 2^{n - 1}\alpha_{2} - 2^{n}\alpha_{1} = (6n - 3)\sum_{k = 1}^{n}2^{k - 1} - 6\sum_{k = 1}^{n}2^{n - k}(n - k)}\)
do końca nie chce mi się liczyć, ale dalej wystarczy tylko zwinąć sumy po prawej, wyznaczyć stałe \(\displaystyle{ \alpha_{2}, _{1}}\), wyliczyć z tego wszystkiego \(\displaystyle{ \alpha_{n + 1}}\) i rozwiązać rekurencję pierwszego stopnia:
\(\displaystyle{ a_{n + 1} = _{n} - a_{n}}\)
z czym mam nadzieję sobie poradzisz . W razie problemów wołaj o pomoc
(btw. wyszło jednak trochę długaśnie, funkcją tworzącą mogło by być nawet szybciej)

joanna_
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 4 wrz 2007, o 23:43
Płeć: Kobieta
Lokalizacja: Słupsk
Podziękował: 1 raz
Pomógł: 1 raz

Wyznaczanie wzoru ogólnego ciągu

Post autor: joanna_ » 7 wrz 2007, o 12:38

a potrafiłbyś wytłumaczyć metodę funkcji tworzących na tym przykładzie? sposób który podałeś jest zbyt czasochłonny (mam 15 na zad na egzaminie) i nie nie jestem pewna czy można go zastosować do każdej funkcji
pozdrawiam

palazi
Użytkownik
Użytkownik
Posty: 175
Rejestracja: 6 wrz 2006, o 21:58
Płeć: Mężczyzna
Lokalizacja: Łapy/Białystok
Podziękował: 2 razy
Pomógł: 37 razy

Wyznaczanie wzoru ogólnego ciągu

Post autor: palazi » 7 wrz 2007, o 13:02

Ok. to inny i nieco szybszy sposób:
Wezmy sobie ciąg: \(\displaystyle{ b_{n} = a_{n} + 3n}\) Wtedy dostajesz rekurencję:
\(\displaystyle{ b_{n} = b_{n-1} + 2b_{n-2}}\)
I dalej już chyba jasne co trzeba robic.

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

Wyznaczanie wzoru ogólnego ciągu

Post autor: max » 7 wrz 2007, o 14:58

Metoda funkcji tworzących jest również czasochłonna. Nie wiem zatem na ile Ci się to przyda, ale skoro prosisz, to napiszę chociażby w ramach ciekawostki przyrodniczej:

Funkcją tworzącą ciągu nazywamy szereg potęgowy o współczynnikach równych kolejnym wyrazom ciągu, np funkcja tworząca \(\displaystyle{ F}\) ciągu \(\displaystyle{ (a_{n})_{n\in \mathbb{N}\setminus\{0\}}}\) jest określona w następujący sposób:
\(\displaystyle{ F(x) = \sum_{n = 0}^{\infty}a_{n+1}x^{n}}\)
Aby wyznaczyć zwartą postać zdefiniowanego rekurencyjnie ciągu \(\displaystyle{ (a_{n})_{n\in\mathbb{N}\setminus\{0\}}}\) można spróbować, korzystając z danej rekurencji dokonać przeksztełceń powyższej równości, tak, aby wyrazić funkcję \(\displaystyle{ F}\) w postaci skończonej. Jeśli się uda i potrafimy tę funkcję rozwinąć w szereg Maclaurina, to ze względu na jednoznaczność przedstawienia funkcji w postaci szeregu potęgowego otrzymamy szukany wzór.
Myślę, że ten przykład powinien to w pewnym stopniu zilustrować:
\(\displaystyle{ F(x) = \sum_{n=0}^{\infty}a_{n+1}x^{n} = \\
= a_{1} + a_{2}x + \sum_{n = 0}^{\infty}a_{n + 3}x^{n + 2} = \\
= -1 - 2x + \sum_{n=0}^{\infty}\left(a_{n+2} + 2a_{n + 1} + 6(n + 3) - 15\right)x^{n + 2} = \\
= -1 - 2x + \sum_{n = 0}^{\infty}a_{n + 2}x^{n + 2} + \sum_{n=0}^{\infty}2a_{n + 1}x^{n + 2} + \sum_{n = 0}^{\infty}6nx^{n + 2} + \sum_{n = 0}^{\infty}3x^{n + 2} = \\
= -1 - 2x + x\sum_{n = 1}^{\infty}a_{n + 1}x^{n} + 2x^{2}\sum_{n = 0}^{\infty}a_{n+1}x^{n} + 6x^{3}\sum_{n = 1}^{\infty}nx^{n - 1} + 3x^{2}\sum_{n = 0}^{\infty}x^{n} = \\
= -1 - 2x + x(F(x) + 1) + 2x^{2}F(x) + \frac{6x^{3}}{(1 - x)^{2}} + \frac{3x^{2}}{1 - x}}\)

I otrzymujemy równanie, z którego wyliczamy \(\displaystyle{ F(x)}\):
\(\displaystyle{ F(x) = \frac{-1 - x}{(1 - x - 2x^{2})} + \frac{6x^{3}}{(1 - x - 2x^{2})(1 - x)^{2}} + \frac{3x^{2}}{(1 - x - 2x^{2})(1 - x)} = \\
= -\frac{1}{1 - 2x} + \frac{6x^{3}}{(1 - 2x)(1 + x)(1 - x)^{2}} + \frac{3x^{2}}{(1 - 2x)(1 + x)(1 - x)}}\)

Aby rozwinąć tę funkcję w szereg można rozbić ją na ułamki proste, rozwinąć każdy z ułamków i zsumować rozwinięcia wyraz za wyrazem. Współczynnik stojący przy n-tej potędze \(\displaystyle{ x}\) w otrzymanym rozwinięciu będzie wyrażał (n + 1)-szy wyraz ciągu.
To oczywiście tylko przykład, o samej metodzie można poczytać np w:
Herbert Wilf: generatingfunctionology
co nieco jest również tutaj.

A tak swoją drogą to chyba Cię na początku nie zrozumiałem, bo założyłem, że wykluczamy zastosowanie równania charakterystycznego... Jeśli tak (tzn jeśli nie wykluczamy) to zobacz też tu.

jovante
Użytkownik
Użytkownik
Posty: 204
Rejestracja: 23 cze 2007, o 14:32
Płeć: Mężczyzna
Lokalizacja: Siedlce
Pomógł: 56 razy

Wyznaczanie wzoru ogólnego ciągu

Post autor: jovante » 7 wrz 2007, o 15:31

Zrobiłem to zadanie metodą podobną do tej, ktorą zademonstrował Max (mniejsza o różnice), więc dodam, że ostatecznie \(\displaystyle{ F(x)=\frac{2x}{1-2x}-\frac{3x}{(x-1)^2}}\). Po rozwinięciu tego w szereg, łatwo otrzymujemy, że \(\displaystyle{ a_n=2^n-3n}\).

ODPOWIEDZ