Rozwiązać równanie rekurencyjne przy użyciu funkcji tworzącej. Sebulbaaa: Witam ^^. Prosił bym o pomoc z zadaniem z matematyki dyskretnej. Próbowałem na wiele sposobów rozwiązać ale za każdym razem wychodził inny wynik. Treść zadania: Przy użyciu funkcji tworzącej rozwiązać poniższe równanie rekurencyjne: a_n = 2a_n−1 + 8a_n−2 + 5*3ⁿ + 9n, dla a₀ = 10, a₁ = −60. Z góry dziękuję za pomoc ^^

wynik: a_n=2*4ⁿ+19(−2)ⁿ−9*3ⁿ−n−2

Mila: Wolfram podaje inny wynik, sprawdź treść.

wredulus_pospolitus: a_n = 2a_n−1 + 8a_n−2 + 5*3ⁿ + 9n ; a₀ = 10 ; a₁ = −60 r² = 2r + 8 −> (r−4)(r+2) = 0 a_n = A*4ⁿ + B*(−2)ⁿ f(n) = 5*3ⁿ + 9n więc 'przewidujemy, że będziemy mieli a_n^sz = Cn+D + E*3ⁿ Cn + D + E*3ⁿ = 2C(n−1) + 2D + 8C(n−2) + 8D + 9n + 3ⁿ⁻²[6E + 8E + 45] 9E = 14E + 45 −−−> E = −9 C = 10C + 9 −−−> C = −1 −−−> D = −2 a_n^sz = −n − 2 − 9*3ⁿ = −n − 2 − 3ⁿ⁺² a₀ = A*4⁰ + B*(−2)⁰ − 0 − 2 − 3² = 10 a₁ = A*4¹ + B*(−2)¹ − 1 − 2 − 3³ = −60 A = 2 B = 19 więc mamy: a_n = 2*4ⁿ + 19(−2)ⁿ − n − 2 − 3ⁿ⁺² czyli to co jest o 20:13

Mila: Dziękuje Arturku. No to coś sknociłam w funkcji tworzącej. Autor właśnie chciał rozwiązania przy pomocy f. tworzącej. Ja rozwiązuję na ogół metodą przewidywań.

Mariusz: a_n = 2a_n−1 + 8a_n−2 + 5*3ⁿ + 9n, dla a₀ = 10, a₁ = −60. A(x)=∑_n=0^∞a_nxⁿ Rekurencja zachodzi dla n≥2 więc indeksujemy szereg od n=2 ∑_n=2^∞a_nxⁿ=∑_n=2^∞2a_n−1xⁿ+∑_n=2^∞8a_n−2xⁿ +∑_n=2^∞5*3ⁿxⁿ+∑_n=2^∞9nxⁿ ∑_n=2^∞a_nxⁿ=2x(∑_n=2^∞a_n−1xⁿ⁻¹)+8x²(∑_n=2^∞a_n−2xⁿ⁻²)

	45x2
+		+∑n=0∞9nxn−0−9x
	1−3x

	1
∑n=0∞xn=
	1−x

d		d		1
	(∑n=0∞xn)=		(		)
dx		dx		1−x

	1
∑n=0∞nxn−1=−		(−1)
	(1−x)2

	1
∑n=0∞nxn−1=
	(1−x)2

	x
∑n=0∞nxn=
	(1−x)2

∑_n=2^∞a_nxⁿ=2x(∑_n=1^∞a_nxⁿ)+8x²(∑_n=0^∞a_nxⁿ)

	45x2		9x
+		+		−9x
	1−3x		(1−x)2

∑_n=0^∞a_nxⁿ−10+60x=2x(∑_n=0^∞a_nxⁿ−10)+8x²(∑_n=0^∞a_nxⁿ)

	45x2		9x
+		+		−9x
	1−3x		(1−x)2

∑_n=0^∞a_nxⁿ=2x(∑_n=0^∞a_nxⁿ)+8x²(∑_n=0^∞a_nxⁿ)

	45x2		9x
+		+		−9x−20x+10−60x
	1−3x		(1−x)2

	45x2		9x
(∑n=0∞anxn)(1−2x−8x2)=−89x+10+		+
	1−3x		(1−x)2

	(−89x+10)(1−x)2(1−3x)+45x2(1−x)2+9x(1−3x)
A(x)(1−2x−8x2)=
	(1−3x)(1−x)2

(1−2x+x²)(1−3x)= 1−2x+x²−3x+6x²−3x³= 1−5x+7x²−3x³ (10−89x)(1−5x+7x²−3x³) 10−50x+70x²−30x³−89x+445x²−623x³+267x⁴ 10−139x+515x²−653x³+267x⁴ +45x²−90x³ +45x⁴ +9x−27x² 10−130x+533x²−743x³+312x⁴

	312x4−743x3+533x2−130x+10
A(x)(1−2x−8x2)=
	(1−3x)(1−x)2

	312x4−743x3+533x2−130x+10
A(x)(1−4x)(1+2x)=
	(1−3x)(1−x)2

	312x4−743x3+533x2−130x+10
A(x)=
	(1−3x)(1−x)2(1−4x)(1+2x)

312x4−743x3+533x2−130x+10
	=
(1−3x)(1−x)2(1−4x)(1+2x)

A		B		C		D		E
	+		+		+		+
1−3x		1−x		(1−x)2		1−4x		1+2x

A(1−x)²(1−4x)(1+2x)+B(1−3x)(1−x)(1−4x)(1+2x)+C(1−3x)(1−4x)(1+2x)+D(1−3x)(1−x)²(1+2x) +E(1−3x)(1−x)²(1−4x)=312x⁴−743x³+533x²−130x+10 Mamy układ równań −8A − 24B −6D+12E=267 14A +26B +24C +11D−31E=−653 −3A +3B −2C −3D+27E=515 −4A −6B −5C −3D −9E=−139 A +B +C +D +E=10 Do rozwiązania tego układu równań proponuję użyć albo macierzy odwrotnej do macierzy głównej układu albo rozkładu LU=PA Jeśli chodzi o odwracanie macierzy to istnieje wersja eliminacji bez dołączania macierzy jednostkowej Potrzebna jest jedynie dodatkowa kolumna aby odtworzyć poprawną permutację kolumn macierzy odwrotnej Macierz odwrotna do macierzy głównej układu to −27/540 −81/540 −243/540 −729/540 −2187/540 −15/540 15/540 45/540 75/540 105/540 30/540 30/540 30/540 30/540 30/540 10/540 40/540 160/540 640/540 2560/540 2/540 −4/540 8/540 −16/540 32/540 312x⁴−743x³+533x²−130x+10

	−27*312−81*(−743)−243*533−729*(−130)−2187*10
A=
	540

	−15*312+15*(−743)+45*533+75*(−130)+105*10
B=
	540

	30*312+30*(−743)+30*533+30*(−130)+30*10
C=
	540

	10*312+40*(−743)+160*533+640*(−130)+2560*10
D=
	540

	2*312−4*(−743)+8*533−16*(−130)+32*10
E=
	540

A=−9 B=−1 C=−1 D=2 E=19

	9		1		1		2		19
A(x)=−		−		−		+		+
	1−3x		1−x		(1−x)2		1−4x		1+2x

	1
∑n=0∞(xn)=
	1−x

d		d		1
	(∑n=0∞(xn))=		(		)
dx		dx		1−x

	1
∑n=0∞(nxn−1)=−		(−1)
	(1−x)2

	1
∑n=1∞(nxn−1)=
	(1−x)2

	1
∑n=0∞((n+1)xn)=
	(1−x)2

A(x)=−9(∑_n=0ⁿ3ⁿxⁿ)−(∑_n=0^∞xⁿ)−(∑_n=0^∞(n+1)xⁿ) +2(∑_n=0ⁿ4ⁿxⁿ))+19(∑_n=0ⁿ(−2)ⁿxⁿ)) A(x)=∑_n=0^∞[19*(−2)ⁿ+2*4ⁿ−(n+2)−9*3ⁿ]xⁿ a_n=19*(−2)ⁿ+2*4ⁿ−(n+2)−9*3ⁿ

Mariusz: O widać że nie dodałem składników części niejednorodnej i otrzymałem błędny układ którego nie poprawiłem I tutaj ujawnia się zaleta macierzy odwrotnej tzn jeśli pomyliliśmy się wyznaczaniu licznika funkcji tworzącej to nie musimy rozwiązywać układu równań po raz wtóry Macierz odwrotna wydaje mi się też odrobinę wygodniejsza w użyciu niż rozkład LU=PA

Mariusz: Mila "Ja rozwiązuję na ogół metodą przewidywań." Ja akurat nie lubię metody przewidywań Jeśli chcemy mieć analogię do równań różniczkowych to proponuję taką metodę Równanie jednorodne przekształcamy w układ równań i rozwiązujemy metodą algebraiczną Do obliczenia potęgi macierzy przydatny będzie jakiś rozkład macierzy np diagonalizacja albo rozkład Jordana Rozwiązanie szczególne znajdujemy uzmienniając stałe Zamiast wrońskianu mamy casoratian a zamiast całkować sumujemy Do obliczania sum przydatna może być suma skończonego ciągu geometrycznego oraz sumowanie przez części

Mila: a_n = 2a_n−1 + 8a_n−2 + 5*3ⁿ + 9n, dla a₀ = 10, a₁ = −60 1) ∑(n=0 do∞)a_n xⁿ= a₀+a₁x+∑(n=2 do∞) (2a_n−1} + 8a_n−2 + 5*3ⁿ + 9n)xⁿ ⇔ A(x)=10−60x+2x*∑(n=2 do∞) a_n−1*xⁿ⁻¹+8x²∑(n=2 do∞) a_n−2*xⁿ⁻²+ +5*3²x²*∑(n=2 do∞) 3ⁿ⁻²xⁿ⁻²+9∑(n=2 do∞)n xⁿ A(x)=10−60x+2x*∑(n=1 do∞)a_nxⁿ+8x²∑(n=0 do∞)a_nxⁿ+45x²∑(n=0 do∞)3ⁿxⁿ+ +9∑(n=2 do∞)n xⁿ

	45x2		9x
A(x)=10−60x+2x*(A(x)−10)+8x2*A(x)+		+		−9*0−9*1x
	1−3x		(1−x)2

	45x2		9x
A(x)−2x*A(x)−8x2*A(x)=10−60x+20x−9x+		+
	1−3x		(1−x)2

	45x2		9x
A(x)*(1−2x−8x2)=10−89x+		+
	1−3x		(1−x)2

	(10−89)*(1−x)2*(1−3x)+45x2*(1−x)2+9x*(1−3x)
A(x)*(1−4x)*(1+2x)=
	(1−3x)*(1−x)2

	312x4−743x3+533x2−130x+10
A(x)=
	(1−x)2+(1+2x)*(1−3x)*(1−4x)

	19		9		2		1		1
A(x)=		−		+		+		−
	1+2x		1−3x		1−4x		1−x		1−x)2