Znajdz proste rónanie rekurencyjne

[tamirka]

Proszę o pomoc, potrafię rozwiązać zadanie do połowy i staje w martwym punkcie bo nie wiem co dalej..

Polecenie jest takie: Znajdz proste równanie rekurencyjne, które spełnia ciąg:
\(\displaystyle{ g_{n} = (2 n^{2} + n - 1)(\sum_{k \in Z}^{}(-1)^{k}{k-\frac{6}{5} \choose k}4 ^{ \frac{1}{2} -k})^{5n} + 2 \sum_{k=0}^{n} {n \choose k} ,n \ge 0}\)

Moja część rozwiązania:
\(\displaystyle{ g_{n} = (2 n^{2} + n - 1)(\sum_{k \in Z}^{}(-1)^{k}{k-1-\frac{1}{5} \choose k}4 ^{ \frac{1}{2} -k})^{5n} + 2 \sum_{k=0}^{n} {n \choose k}}\)

\(\displaystyle{ g_{n} = (2 n^{2} + n - 1)(\sum_{k \in Z}^{} { \frac{1}{5} \choose k} 4 ^{ \frac{1}{2} -k})^{5n} + 2 \sum_{k=0}^{n} {n \choose k}}\)

\(\displaystyle{ g_{n} = (2 n^{2} + n - 1) 5^{ \frac{1}{5}*5n} + 2 \sum_{k=0}^{n} {n \choose k}}\)

\(\displaystyle{ g_{n} = (2 n^{2} + n - 1) 5^{n} + 2*2 ^{n}}\)

\(\displaystyle{ g_{n} = (2 n^{2} + n - 1) 5^{ \frac{1}{5}*5n} + 2 \sum_{k=0}^{n} {n \choose k}}\)


No i teraz wiem ze trzeba wykorzystac funkcje tworzące "od końca".. tylko że próbuję wykorzystac magiczny wzór: \(\displaystyle{ \sum_{ \infty }^{n=0} 2 ^{n} z ^{n} = \frac{1}{1 - 2z}}\) i przeszkadza mi początek \(\displaystyle{ (2 n^{2} + n - 1)}\) , szczerze to nie rozumiem do konca o co chodzi w tym, jeśli ktos by mogł to poproszę o rozwiązanie zadania do konca z komentarzem albo o szczegolowe wytlumaczenie

[bstq]

\(\displaystyle{ g_{n}=\left(2n^{2}+n-1\right)\cdot5^{n}+2^{n+1}}\) - zakladajac ze to co napisalas jest prawda...

\(\displaystyle{ g_{n+1}=\left(2\left(n+1\right)^{2}+n+1-1\right)\cdot5^{n+1}+2^{n+2}=\left(2n^{2}+4n+2+n+1-1\right)\cdot5^{n+1}+2^{n+2}

=\left(2n^{2}+n-1\right)\cdot5^{n+1}+2^{n+2}+\left(4n+2+1\right)\cdot5^{n+1}+5\cdot2^{n+1}-5\cdot2^{n+1}=5\cdot\left[\left(2n^{2}+n-1\right)\cdot5^{n}+2^{n+1}\right]+2^{n+2}+\left(4n+2+1\right)\cdot5^{n+1}-5\cdot2^{n+1}=5\cdot g_{n}+2^{n+2}+\left(4n+2+1\right)\cdot5^{n+1}-5\cdot2^{n+1}}\)

chyba rekurencja to uzaleznienie g_n od g_n-1, g_n-2 itp nie wiem po co chcesz to bardziej upraszczac

[tamirka]

hmm... rozumiem co zostało zrobione w Twoim rozwiązaniu ale takiej odpowiedzi chyba by mi nie uznali na egzaminie dlatego chce to uproscic bardziej... chodzi im o to że trzeba to uproscic do takiej postaci (przykład innego rozwiazania z zadania tego typu)
\(\displaystyle{ g_{0} = 1}\)
\(\displaystyle{ g_{1} = 1}\)
\(\displaystyle{ g_{n} = 4 \cdot g_{n-1} + 4 \cdot g_{n-2}}\)

Dlatego napisałam ze wczesniej uzywałam "magicznego wzoru" bo z nim wszystko ładnie wychodzilo

[xiikzodz]

Mając:

\(\displaystyle{ g_{n} = (2 n^{2} + n - 1) 5^{n} + 2\cdot 2 ^{n}}\)

wygląd rekurencji znamy z ogólnej teorii. Wystarczy rozważyć wielomian którego trzykrotnym pierwiastkiem jest liczba 5 (bo przy \(\displaystyle{ 5^n}\) staoi wielomian stopnia 2 od zmiennej \(\displaystyle{ n}\)) i jednokrotnym liczba 2, czyli

\(\displaystyle{ \chi(x)=(x-5)^3(x-2)}\).

Po otworzeniu nawiasów:

\(\displaystyle{ \chi(x)=x^4-17x^3+105x^2-275x+250}\)

stąd już mamy warunek rekurencyjny:

\(\displaystyle{ g_{n+4}=17g_{n+3}-105g_{n+2}+275g_{n+1}-250g_n}\).

Pozostaje wyznaczyć pierwsze cztery wyrazy ciągu.

Jeśli chcemy używać funkcji tworzących, to zauważamy, że jeśli:

\(\displaystyle{ f(x)}\)

jest funkcją tworzącą ciągu \(\displaystyle{ a^n}\), czyli z jednej strony

\(\displaystyle{ f(x)=\frac{1}{1-ax}}\)

zaś z drugiej

\(\displaystyle{ f(x)=\sum (ax)^n}\)

to

\(\displaystyle{ f'(x)=\frac{a}{(1-ax)^2}}\)

oraz

\(\displaystyle{ f'(x)=\sum na(ax)^{n-1}}\).

Różniczkując ponownie otrzymujemy:

\(\displaystyle{ f''(x)=\frac{2a^2}{(1-ax)^3}}\)

oraz

\(\displaystyle{ f''(x)=\sum n(n-1)a^2(ax)^{n-2}}\).

Podstawiając zatem:

\(\displaystyle{ f(x)=\frac{1}{1-5x}}\)

i rozważając kombinację liniową funkcji \(\displaystyle{ f,f',f''}\), czyli \(\displaystyle{ \frac{1}{1-5x},\frac{5}{(1-5x)^2},\frac{50}{(1-5x)^3}}\) bez trudu otrzymamy funkcję tworzącą ciągu \(\displaystyle{ (2 n^{2} + n - 1) 5^{n}}\).

[tamirka]

Nie rozumiem pierwszej częsci skąd się wziął akurat taki wielomian\(\displaystyle{ X(x)}\) . .
Czy to są rozważania czy mozna to jakos udowodnic np rozpisac?

Bo ja robiłam cos takiego że zakładałam ze
\(\displaystyle{ A(z)= a_{0}+ a_{1} \cdot z^{1} + a_{2} \cdot z^{2} +...+ a_{n} \cdot z^{n} +...}\)

pozniej:

\(\displaystyle{ A(z) = \sum_{ \infty }^{n=0} a_{n} \cdot z^{n}}\)


podstawiałam liczylam i wychodziły zazwyczaj ładne liczby czyli cos w stylu:

\(\displaystyle{ A(z) = \frac{g(z)}{m(z)}}\)

i z takiego juz potrafie rozpisac i rozwiązac..

Jeśli ktos rozumie o co mi chodzi i czy ja dobrze mam zamiar rozwiązywac zadanie i czy pierwsza czesc rozwiazania xiikzodz, ma cos wspolnego z tym co napisałam, to proszę o pomoc.
I oczywiscie dziękuję za dotychczasowe odpowiedzi , pomogły troche

edit:
RACJA!!! Rozumiem teraz, bardzo podobnie mi wyszło tylko nie wiedzialam co trzeba zrobic w jednym miejscu a to trzeba było uzyc pochodnych teraz juz wszystko jest jasne! Dziekuje za pomoc

[xiikzodz]

Równanie charakterystyczne ciągu (liniowo) rekurencyjnego otrzymujemy (na przykład) właśnie stosując funkcje tworzące ciągów i proste operacje na funkcjach wymiernych. Łatwo bowiem zauważyć, że w każdym przypadku stosowania metody funkcji tworzących pojawia się ten wielomian \(\displaystyle{ \chi}\) i rozwiązanie wyznaczają jego pierwiastki.

[bstq]

ciekawe rozwiazanie - nigdy nie myslalem o tym w ten sposob