Funkcja tworząca - odwracanie przekształcenia bez liczb zespolonych Mariusz: Funkcja tworząca − odwracanie przekształcenia bez jawnego korzystania z liczb zespolonych Dla liniowego równania rekurencyjnego o stałych współczynnikach funkcja tworząca jest funkcją wymierną Mamy do rozpatrzenia trzy przypadki 1. W rozkładzie mianownika na czynniki dostajemy tylko parami różne czynniki liniowe Policzmy kilka pochodnych z takiego ułamka prostego

d0f		1
	=
dx0		x−x1

df		1
	= −
dx		(x−x1)2

d2f		(−2)(−1)
	=
dx2		(x−x1)3

d3f		(−3)(−2)(−1)
	=
dx3		(x−x1)4

Widzimy że dla n. pochodnej dostaniemy

dnf		(−1)n n!
	=
dxn		(x−x1)n+1

dnf		(−1)n n!
	|x=0 =
dxn		(−x1)n+1

1	dnf		1
		|x=0 = −(		)n+1
n!	dxn		x1

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−− 2. W rozkładzie mianownika na czynniki dostajemy tylko parami różne czynniki kwadratowe nierozkładalne Niech g_n = aⁿcos(ωn+θ) , wtedy

	cos(θ)−acos(ω−θ)x
G(x) =
	1−2acos(ω)x+a2x2

Tutaj może przykładzik Przypuśćmy że w rozkładzie funkcji wymiernej którą dostaliśmy po zastosowaniu funkcji tworzącej otrzymaliśmy następujący ułamek

2x+7
x2+4x+5

2x+7		2x+7
	=
x2+4x+5		5(1+0.8x+0.2x2)

	0.4x+1.4
=
	1+0.8x+0.2x2

Teraz wiemy że jeżeli g_n = r aⁿcos(ωn+θ)

	rcos(θ)−ar cos(ω−θ)x
to G(x) =
	1−2acos(ω)x+a2x2

Teraz wyznaczamy potrzebne nam wielkości

	1		1
a2 =		, a =
	5		√5

	2		4
−		cos(ω) =
	√5		5

	−2√5
cos(ω) =
	5

	−2√5
ω = arccos(		)
	5

Mamy zatem układ równań

	7
rcos(θ) =
	5

	1		−2√5		2
−		rcos(θ−arccos(		)) =
	√5		5		5

	7
rcos(θ) =
	5

	−2√5		2√5
rcos(θ−arccos(		)) = −
	5		5

	7
cos(θ) =
	5r

	7		−2√5		7		2√5		−2√5
r(		(		)+sin(arccos(		))sin(arccos(−		))) =
	5r		5		5r		5		5

	7		−2√5		7		2√5
r(		(		)+√1−cos2(arccos(		))√1−cos2(arccos(−		))) =
	5r		5		5r		5

	−2√5
	5

	14√5		−2√5
r(−		+√1−4925r2√1−(−2√55)2) =
	25r		5

−14√5		√25r2−49	√5		2√5
	+			=−
25		5r	5		5

−14+√25r²−49 = −10 √25r²−49 = 4 25r²−49 = 16 25r² = 65 5r = √65

	√65
r =
	5

	7		5
cos(θ) =		*
	5		√65

	7
cos(θ) =
	√65

	7√65
θ = arccos(		)
	65

	2x+7
Dla ułamka		dostajemy ciąg
	x2+4x+5

	√65		√5		−2√5		7√65
an =		(		)ncos(arccos(		)n+ arccos(		))
	5		5		5		65

przy czym jego wyrazy zostały obliczone bez jawnego korzystania z liczb zespolonych 3. W rozkładzie mianownika na czynniki dostajemy czynniki wielokrotne Tutaj przydaje się to że funkcja tworząca splotu ciągów jest iloczynem funkcji tworzących gdzie splot jest zdefiniowany jako (f*g)(n) = ∑_k=0ⁿf_ng_n−k