Znajdź wzór ogólny na a_n wiedząc, że: eh: a_n − 7a_n−1 + 16a_n−2 − 12a_n−3 = n − 2 dla n ≥ 3 a₀ = a₁ = a₂ = 1

kerajs: a₃=3−2+7−16+12=4 a₄=4−2+28−16+12=... r³−7r²+16r−12=0 (r−2)²(r−3)=0 a_n=A2ⁿ+Bn2ⁿ+C3ⁿ+Dn+E wstaw a₀, a₁, .., a₄ i wylicz A,B,C,D i E.

Mariusz: Funkcja tworząca jest wygodniejsza w użyciu i bardziej ogólna A(x)=∑_n=0^∞a_nxⁿ Rekurencja zachodzi dla n≥3 więc zaczynasz sumować od n=3 ∑_n=3^∞a_nxⁿ+∑_n=3^∞−7a_n−1xⁿ+∑_n=3^∞16a_n−2xⁿ +∑_n=3^∞−12a_n−3xⁿ=∑_n=3^∞(n−2)xⁿ ∑_n=3^∞a_nxⁿ−7x(∑_n=3^∞a_n−1xⁿ⁻¹)+16x²(∑_n=3^∞a_n−2xⁿ⁻²) −12x³(∑_n=3^∞a_n−3xⁿ⁻³)=∑_n=3^∞(n−2)xⁿ ∑_n=3^∞a_nxⁿ−7x(∑_n=2^∞a_nxⁿ)+16x²(∑_n=1^∞a_nxⁿ) −12x³(∑_n=0^∞a_nxⁿ)=∑_n=0^∞(n+1)xⁿ⁺³ (∑_n=0^∞a_nxⁿ−1−x−x²)−7x(∑_n=0^∞a_nxⁿ−1−x)+16x²(∑_n=0^∞a_nxⁿ−1) −12x³(∑_n=0^∞a_nxⁿ)=x³(∑_n=0^∞(n+1)xⁿ) Tutaj ja użyłem różniczkowania szeregu geometrycznego aby dostać funkcję tworzącą ciągu n+1 ale można było skorzystać z uogólnionego dwumianu Newtona

	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

	x3
A(x)−1−x−x2−7xA(x)+7x+7x2+16x2A(x)−16x2−12x3A(x)=
	(1−x)2

	x3
A(x)(1−7x+16x2−12x3)−1+6x−10x2=
	(1−x)2

	x3
A(x)(1−7x+16x2−12x3)=10x2−6x+1+
	(1−x)2

(10x²−6x+1)(x²−2x+1)=10x⁴−20x³+10x²−6x³+12x²−6x+x²−2x+1 (10x²−6x+1)(x²−2x+1)=10x⁴−26x³+23x²−8x+1

	10x4−25x3+23x2−8x+1
A(x)(1−7x+16x2−12x3)=
	(1−x)2

	10x4−25x3+23x2−8x+1
A(x)=
	(1−7x+16x2−12x3)(1−x)2

1−7x+16x²−12x³=0

	1
t=
	x

	7		16		12
1−		+		−		=0|t3
	t		t2		t3

t³−7t²+16t−12=0 t³−27−7t²+63+16t−48=0 (t−3)(t²+3t+9)−7(t−3)(t+3)+16(t−3)=0 (t−3)(t²+3t+9−7t−21+16)=0 (t−3)(t²−4t+4)=0 (t−3)(t−2)²=0

	1		1
(		−3)(		−2)2=0
	x		x

	1−3x		(1−2x)2
(		)(		)=0
	x		x2

(1−3x)(1−2x)²=0

	10x4−25x3+23x2−8x+1
A(x)=
	(1−3x)(1−2x)2(1−x)2

Tutaj nie rozkładamy funkcji tworzącej na sumę ułamków prostych tylko raczej na sumę szeregów geometrycznych i ich pochodnych Można by było rozłożyć funkcję tworzącą na sumę ułamków prostych co ułatwiłoby n krotne różniczkowanie funkcji tworzącej

10x4−25x3+23x2−8x+1
	=
(1−3x)(1−2x)2(1−x)2

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

A(1−2x)²(1−x)²+B(1−3x)(1−2x)(1−x)²+C(1−3x)(1−x)²+D(1−x)(1−3x)(1−2x)²+E(1−3x)(1−2x)²= 10x⁴−25x³+23x²−8x+1 A(1−6x+13x²−12x³+4x⁴)+B(1−7x+17x²−17x³+6x⁴)+C(1−5x+7x²−3x³) +D(1−8x+23x²−28x³+12x⁴)+E(1−7x+16x²−12x³)=10x⁴−25x³+23x²−8x+1 A+B+C+D+E = 1 −6A−7B−5C−8D−7E=−8 13A+17B+7C+23D+16E=23 −12A−17B−3C−28D−12E=−25 4A+6B+12D = 10 1 1 1 1 1 −6 −7 −5 −8 −7 13 17 7 23 16 −12 −17 −3 −28 −12 4 6 0 12 0 1 1 1 1 1 0 −1 1 −2 −1 0 4 −6 10 3 0 −5 9 −16 0 0 2 −4 8 −4 1 1 1 1 1 0 −1 1 −2 −1 0 0 −2 2 −1 0 0 4 −6 5 0 0 −2 4 −6 1 1 1 1 1 0 −1 1 −2 −1 0 0 −2 2 −1 0 0 0 −2 3 0 0 0 2 −5 1 1 1 1 1 0 −1 1 −2 −1 0 0 −2 2 −1 0 0 0 −2 3 0 0 0 0 −2 U = 1 1 1 1 1 0 −1 1 −2 −1 0 0 −2 2 −1 0 0 0 −2 3 0 0 0 0 −2 L = 1 0 0 0 0 −6 1 0 0 0 13 −4 1 0 0 −12 5 −2 1 0 4 −2 1 −1 1 y₁=1 −6y₁+y₂=−8 13y₁−4y₂+y₃=23 −12y₁+5y₂−2y₃+y₄ =−25 4y₁−2y₂+y₃−y₄+y₅=10 y₁=1 y₂=−2 y₃=2 y₄=1 y₅=1 −2x₅=1

	1
x5=−
	2

−2x₄+3x₅=1

	3
−2x4−		=1
	2

	5
x4=−
	4

−2x₃+2x₄−x₅=2

	5		1
−2x3−		+		=2
	2		2

x₃=−2 −x₂+x₃−2x₄−x₅=−2

	5		1
−x2−2+		+		=−2
	2		2

−x₂+3=0 x₂=3 x₁+x₂+x₃+x₄+x₅=1

	5		1
x1+3−2−		−		=1
	4		2

	7
x1−		=0
	4

	7
x1=
	4

	7	1		1		1		5	1		1	1
A(x)=			+3		−2		−			−
	4	1−3x		1−2x		(1−2x)2		4	1−x		2	(1−x)2

	1
∑n=0∞λnxn =		// Szereg geometryczny
	1−λx

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

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

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

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

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

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

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

d		d		1
	(∑n=0∞(n+1)λnxn)=		(		)
dx		dx		(1−λx)2

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

	2λ
∑n=1∞n(n+1)λnxn−1 =
	(1−λx)3

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

	2λ
∑n=0∞(n+1)(n+2)λ*λnxn =
	(1−λx)3

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

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

d		d		2
	(∑n=0∞(n+1)(n+2)λnxn) =		(		)
dx		dx		(1−λx)3

	2*3
∑n=0∞n(n+1)(n+2)λnxn−1=−		(−λ)
	(1−λx)4

	2*3*λ
∑n=1∞n(n+1)(n+2)λnxn−1=
	(1−λx)4

	2*3*λ
∑n=0∞(n+1)(n+2)(n+3)λn+1xn=
	(1−λx)4

	2*3*λ
∑n=0∞(n+1)(n+2)(n+3)λ*λnxn=
	(1−λx)4

	2*3*λ
λ(∑n=0∞(n+1)(n+2)(n+3)λnxn)=
	(1−λx)4

	2*3
∑n=0∞(n+1)(n+2)(n+3)λnxn =
	(1−λx)4

	k!
∑n=0∞(∏m=1k(n+m))λnxn =
	(1−λx)k+1

Wzór powstały z k krotnego różniczkowania szeregu geometrycznego Jeżeli przyjmiemy że ∏_m=1⁰(n+m)=1 to będzie działał także dla pochodnej zerowego rzędu

	7	1		1		1		5	1		1	1
A(x)=			+3		−2		−			−
	4	1−3x		1−2x		(1−2x)2		4	1−x		2	(1−x)2

	7
A(x)=		(∑n=0∞3nxn)+3(∑n=0∞2nxn)−2(∑n=0∞(n+1)2nxn)
	4

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

	7		5		1
an=		*3n+3*2n−2(n+1)2n−		−		(n+1)
	4		4		2

	7		1
an=		*3n−(2n−1)*2n−		(2n+7)
	4		4

kerajs: ''Mariusz: Funkcja tworząca jest wygodniejsza w użyciu i bardziej ogólna '' Owszem, jest metodą bardziej uniwersalną, ale nigdy nie jest wygodniejszą. Twój post jest najlepszym tego dowodem. Wykreśliwszy poszukiwanie współczynników A, B, C, D , E i tak pozostaje niezły elaborat, wielokrotnie dłuższy (i wielokrotnie bardziej skomplikowany, i wielokrotnie bardziej narażony na pomyłkę, i wymagający wielokrotnie większej ilości wiadomości i wielokrotnie ... ) niż pięć linijek które napisałem powyżej. Niemniej, ten suchar nadal mnie bawi, tym bardziej że pewnie są osoby które wierzą w jego prawdziwość. PS Uzyskany wynik jest poprawny.

Mariusz: " i tak pozostaje niezły elaborat, wielokrotnie dłuższy (i wielokrotnie bardziej skomplikowany, i wielokrotnie bardziej narażony na pomyłkę, i wymagający wielokrotnie większej ilości wiadomości i wielokrotnie ... ) niż pięć linijek które napisałem powyżej. " Tylko nie wiadomo skąd wziąłeś to że rozwiązanie jest postaci a_n=A2ⁿ+Bn2ⁿ+C3ⁿ+Dn+E ani nawet nie wiadomo skąd wziąłeś to równanie r³−7r²+16r−12=0 W przypadku funkcji tworzącej to że mamy sumę funkcji wykładniczych ewentualnie pomnożonych przez czynnik wielomianowy wychodzi z tego że otrzymujemy sumę szeregów geometrycznych i ich pochodnych a ty to zgadujesz W przypadku funkcji tworzących jeśli koniecznie chcemy otrzymać to równanie wielomianowe

	1
to w równaniu powstałym z przyrównania mianownika do zera podstawiamy r=
	x

natomiast ty to równanie zgadujesz Jest wygodniejsza w użyciu bo wystarczy wstawić i równanie się samo rozwiązuje W przypadku równań liniowych o stałych współczynnikach funkcja tworząca jest funkcją wymierną i można ją rozłożyć na sumę szeregów geometrycznych i ich pochodnych i nie trzeba zgadywać jaką postać będzie miało rozwiązanie Tutaj rozpisałem ten wzór na funkcję tworzącą ciągu ∏_m=1^k(n+k)λⁿ bo przydaje się on gdy mianownik funkcji tworzącej zawiera wielokrotne czynniki Mógłbym od razu podać tę funkcję tworzącą i nie wyprowadzać tego wzorku Wtedy byłaby ona równie czasochłonna co twoje ulubione zgadywanie Poza tym jak to jeden z użytkowników innego forum napisał to że dana metoda jest dłuższa nie oznacza że jest ona trudniejsza

Mila: Metoda przewidywań: a_n=A*2ⁿ+B*n*2ⁿ+C*3ⁿ+Dn+E 1) Wyznaczam wsp. D i E Dn+E−7[D*(n−1)+E]+16[D*(n−2)+E]−12[D*(n−3)+E]=n−2 Stąd D*(−2n+11)−2E=n−2 −2D*n+(11D−2E)=n−2

	1		7
D=−		i E=−
	2		4

2)

	1		7
(*) an=A*2n+B*n*2n+C*3n−		n−
	2		4

Korzystam z war. początkowych i wyznaczam wsp. A,B, C

	7
a0=A+C+(−		=1
	4

	1		7
a1=2A+2B+3C−		−		=1
	2		4

	7
a2=4A+8B+9C−1−		=1
	4

===============

	11
A+C=
	4

	13
2A+2B+3C=
	4

	15
4A+8B+9C=
	4

⇔

	7
A=1, B=−2, C=
	4

================ 3)

	7		1		7
an=2n−2n*2n+		*3n−		n−		,
	4		2		4

===========================

Mariusz: a_n − 7a_n−1 + 16a_n−2 − 12a_n−3 = n − 2 dla n ≥ 3 a₀ = a₁ = a₂ = 1 Rozwiązanie z użyciem funkcji tworzącej już pokazałem Pokażę teraz dość podobny pomysł na rozwiązanie tzn przekształcenie Z Na początek przesuńmy indeksy zadanego ciągu aby wygodniej było zastosować przekształcenie Z a_n+3 − 7a_n+2 + 16a_n+1 − 12a_n = n + 1 dla n ≥ 0 a₀ = a₁ = a₂ = 1 A(z) = ∑_n=−∞^∞a_nz⁻ⁿ Tutaj przyjmujemy że wyrazy o ujemnych indeksach są równe zero A(z) = ∑_n=0^∞a_nz⁻ⁿ ∑_n=0^∞a_n+3z⁻ⁿ+∑_n=0^∞−7a_n+2z⁻ⁿ+∑_n=0^∞16a_n+1z⁻ⁿ +∑_n=0^∞−12a_nz⁻ⁿ=∑_n=0^∞(n+1)z⁻ⁿ z³(∑_n=0^∞a_n+3z⁻ⁿ⁻³)−7z²(∑_n=0^∞a_n+2z⁻ⁿ⁻²)+ 16z(∑_n=0^∞a_n+1z⁻ⁿ⁻¹)−12(∑_n=0^∞a_nz⁻ⁿ)=∑_n=0^∞(n+1)z⁻ⁿ

	1		1		1
z3(∑n=0∞anz−n−1−		−		)−7z2(∑n=0∞anz−n−1−		)
	z		z2		z

+16z(∑_n=0^∞a_n+1z⁻ⁿ⁻¹−1)−12(∑_n=0^∞a_nz⁻ⁿ) =

	1
∑n=0∞z−n=
	1   1−   z

	z
∑n=0∞z−n=
	z−1

d		d		z
	(∑n=0∞z−n) =		(		)
dz		dz		z−1

	1*(z−1)−z*1
∑n=0∞−nz−n−1=
	(z−1)2

	−1
∑n=0∞−nz−n−1=
	(z−1)2

	−1
−(∑n=0∞nz−n−1)=
	(z−1)2

	1
∑n=0∞nz−n−1=
	(z−1)2

	z
∑n=0∞nz−n=
	(z−1)2

	z		z
(z3A(z)−z3−z2−z)−7(z2A(z)−z2−z)+16(zA(z)−z)−12A(z)=		+
	(z−1)2		z−1

	z(z−1)+z
A(z)(z3−7z2+16z−12) − (z3−6z2+10z)=
	(z−1)2

	z2
A(z)(z3−7z2+16z−12)=(z3−6z2+10z)+
	(z−1)2

	(z3−6z2+10z)(z−1)2+z2
A(z)=
	(z3−7z2+16z−12)(z−1)2

z³−27−7(z²−9)+16z−12+27−63=0 z³−27−7(z²−9)+16z−48=0 (z−3)(z²+3z+9)−7(z−3)(z+3)+16(z−3)=0 (z−3)(z²+3z+9−7z−21+16)=0 (z−3)(z²−4z+4)=0 (z−3)(z−2)² (z³−6z²+10z)(z²−2z+1)=z⁵−6z⁴+10z³−2z⁴+12z³−20z²+z³−6z²+10z (z³−6z²+10z)(z²−2z+1)=z⁵−8z⁴+23z³−26z²+10z

	z5−8z4+23z3−25z2+10z
A(z)=
	(z−3)(z−2)2(z−1)2

Teraz odwracamy przekształcenie Tutaj wygodniejsza będzie metoda residuów z = 3 jest pojedynczym biegunem

	z5−8z4+23z3−25z2+10z
limz→3		zn−1
	(z−2)2(z−1)2

	z4−8z3+23z2−25z+10
limz→3		zn
	(z−2)2(z−1)2

	81−8*27+23*9−25*3+10
=		3n
	(3−2)2(3−1)2

	81−216+207−75+10
=		*3n
	4

	6−9+10
=		*3n
	4

	7
=		*3n
	4

z=2 jest podwójnym biegunem

	d	(z4−8z3+23z2−25z+10)zn
limz→2
	dz	(z−3)(z−1)2

d		f(z)		f'(z)g(z)−f(z)g'(z)
	(		)=
dz		g(z)		g2(z)

d		f(z)		f'(z)		f(z)g'(z)
	(		)=		−
dz		g(z)		g(z)		g2(z)

	(4z3−24z2+46z−25)zn+n(z4−8z3+23z2−25z+10)zn−1
limz→2
	(z−3)(z−1)2

	(3z2−10z+7)(z4−8z3+23z2−25z+10)
−limz→2
	(z−3)2(z−1)4

2(32−96+92−25)+n(16−64+92−50+10)
	2n−1
(−1)(1)2

	(12−20+7)(16−64+92−50+10)
−		2n
	(−1)2(1)4

−(6+n(118−114))2ⁿ⁻¹−(−1)(118−114)*2ⁿ =−3*2ⁿ−2n*2ⁿ+4*2ⁿ =2ⁿ−2n*2ⁿ =−(2n−1)*2ⁿ z=1 jest podwójnym biegunem

	d		(z4−8z3+23z2−25z+10)zn
limz→1		(		)
	dz		(z−3)(z−2)2

	(4z3−24z2+46z−25)zn+n(z4−8z3+23z2−25z+10)zn−1
limz→1
	(z−3)(z−2)2

	(3z2−14z+16)(z4−8z3+23z2−25z+10)zn
−limz→1
	(z−3)2(z−2)4

(4−24+46−25)+n(1−8+23−25+10)
(−2)(−1)2

	(3−14+16)(1−8+23−25+10)
−
	(−2)2(−1)4

	1		1
=−		(1+n)−		(5*1)
	2		4

	1
=−		(2n+7)
	4

Ostateczny wynik to suma residuów

	7		1
an=		*3n−(2n−1)*2n−		(2n+7)
	4		4