Zadania dla Szkolniaka Mila: 1) a_n=2a_n−1+3, a₀=2 2)

	1
an=−		an−1+1
	2

	5
a0=
	3

3) a_n=a_n−1+2a_n−2+(−1)ⁿ a₀=1, a₁=1 Podpowiedź : dla ciągu:

	1
cn=(−1)n funkcja tworząca A(x)=
	1+x

Szkolniak: ad 1) Odpowiedzi na końcu, rozwiązanie zostawię dla potomnych, może ktoś skorzysta kiedyś a_n=2a_n−1+3, a₀=2 A(x)=_n=0^∞∑a_nxⁿ _n=1^∞∑a_nxⁿ=_n=1^∞∑(2a_n−1+3)xⁿ _n=1^∞∑a_nxⁿ=2*_n=1^∞∑a_n−1xⁿ+3_n=1^∞∑xⁿ _n=1^∞∑a_nxⁿ=2x*_n=1^∞∑a_n−1xⁿ⁻¹+3_n=1^∞∑xⁿ (_n=0^∞∑a_nxⁿ)−a₀=2x*_n=0^∞∑a_nxⁿ+3_n=1^∞∑xⁿ

	x
A(x)−a0=2xA(x)+3*
	1−x

	3x
A(x)−2=2xA(x)+
	1−x

A(x)(1−x)−2(1−x)=2x(1−x)A(x)+3x A(x)−xA(x)−2+2x=2xA(x)(1−x)+3x A(x)−xA(x)−2+2x=2xA(x)−2x²A(x)+3x A(x)−3xA(x)+2x²A(x)=x+2 A(x)(2x²−3x+1)=x+2 A(x)(2x²−2x−x+1)=(x+2) A(x)[2x(x−1)−(x−1)]=x+2 A(x)(x−1)(2x−1)=x+2

	x+2
A(x)=
	(1−x)(1−2x)

	x+2		A		B
		=		+
	(1−x)(1−2x)		1−x		1−2x

x+2=A(1−2x)+B(1−x) → (A,B)=(−3,5)

	1		1
A(x)=−3*		+5*
	1−x		1−2x

A(x)=−3*_n=0^∞∑xⁿ+5*_n=0^∞∑2ⁿxⁿ A(x)=_n=0^∞∑((−3)+5*2ⁿ)xⁿ a_n=5*2ⁿ−3

	x+2
funkcja tworząca : A(x)=
	(1−x)(1−2x)

jawna postać wzoru ciągu : a_n=5*2ⁿ−3

Szkolniak: ad 2)

	2   5   x− 3   3
funkcja tworząca : A(x)=
	1   1   x2+ x−1 2   2

	1		2
wzór ciągu : an=(−		)n+
	2		3

Mila:

Szkolniak: Mila, trzeci przykład to jakieś piekło Niby zrobiłem ale coś źle wyszło, zaraz poszukam błędu i zobaczymy co wyjdzie Przykład ciekawy i dużo myślenia

Mila: To na razie zostaw. Jutro będzie dobry dzień. Jeśli nie wyjdzie, to napiszę.

Szkolniak: Nie mogę znaleźć błędu, czy taka funkcja tworząca tu wychodzi?

	2x2+2x+1
A(x)=
	(1+x)2(1−2x)

Mila: Ja mam :

	x2+x+1
F(x)=
	(x+1)2*(1−2x)

Mogłam się pomylić?

Szkolniak: Niby podobne, rano przejrzę jeszcze raz moje rozwiązanie, dobrej nocy

Mariusz: a_n = a_n−1+2a_n−2+(−1)ⁿ a₀ = 1 , a₁ = 1 A(x)=∑_n=0^∞a_nxⁿ ∑_n=2^∞a_nxⁿ=∑_n=2^∞a_n−1xⁿ+∑_n=2^∞2a_n−2xⁿ+∑_n=2^∞(−1)ⁿxⁿ ∑_n=2^∞a_nxⁿ=x(∑_n=2^∞a_n−1xⁿ⁻¹)+2x²(∑_n=2^∞a_n−2xⁿ⁻²)+ ∑_n=2^∞(−1)ⁿxⁿ

	x2
∑n=2∞anxn=x(∑n=1∞anxn)+2x2(∑n=0∞anxn)+
	1+x

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

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

	x2
1+x−x+
	1+x

	x2
A(x)(1−x−2x2)=1+
	(1+x)

	x2+x+1
A(x)(1−x−2x2) =
	(1+x)

	x2+x+1
A(x) =
	(1+x)(1−x−2x2)

	x2+x+1
A(x) =
	x   9   (1+x)((1− )2− x2)   2   4

	x2+x+1
A(x) =
	x   3   x   3   (1+x)(1− − x)(1− + x)   2   2   2   2

	x2+x+1
A(x) =
	(1+x)(1−2x)(1+x)

	x2+x+1
A(x) =
	(1+x)2(1−2x)

Czyli Mila się nie pomyliła Szkolniak miałeś wykładnicze funkcje tworzące ? Czasem wygodniej jest je zastosować np do rekurencji na liczby Bella czy liczby Bernoulliego

Szkolniak: ad 3) Ok policzyłem jeszcze raz i wyszło mi tak jak Wam, wszystko się zgadza i kontynuuje już tutaj:

	x2+x+1
A(x)=
	(1+x)2(1−2x)

	7		1		1		1		1		1
A(x)=		*		−		*		+		*
	9		1−2x		9		1+x		3		(1+x)2

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

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

	7		1		1
więc: an=		*2n−		*(−1)n+		*(−1)n(n+1)
	9		9		3

	7		1
po uproszczeniu: an=		*2n+		*(−1)n*(3n+2)
	9		9

Mariusz, nie miałem takich rzeczy, a bardziej 'nie czytałem' o tym Wczoraj znalazłem jakieś pliki pdf po angielsku na temat 'recurrence relations' więc dziś wieczorem jak będzie trochę czasu to może to przejrzę i zobaczę co tam w ogóle jest Bo żeby coś po polsku znaleźć na ten temat to ciężko, ale w sumie angielski nie jest dla mnie jakąś wielką barierą to chyba coś z tego wyniosę

Szkolniak: Swoją drogą dosyć skomplikowany i trochę, według mnie, niepotrzebny rozkład zrobiłeś z tym mianownikiem, tzn. z (1+x)(1−x−2x²) Ja tak to zrobiłem: (1+x)(1−x−2x²)=(1+x)*(1−x−x²−x²)= =(1+x)*[(1−x²)−(x+x²)]= =(1+x)*[(1+x)(1−x)−x(1+x)]= =(1+x)²(1−2x)

Mariusz: https://www2.math.upenn.edu/~wilf/gfology2.pdf Tutaj masz trochę o funkcjach tworzących Zwykła funkcja tworząca dla ciągu jedynek daje szereg geometryczny Wykładnicza funkcja tworząca dla ciągu jedynek daje eksponentę czyli funkcję e^x Jako przykład może pokażę jak wyprowadzić funkcje tworzące wielomianów Czebyszowa Najpierw wyprowadźmy równanie rekurencyjne dla wielomianów Czebyszowa cos((m+1)t)=cos(t)cos(mt) − sin(t)sin(mt) cos((m−1)t)=cos(t)cos(mt) + sin(t)sin(mt) Po dodaniu stronami otrzymamy cos((m+1)t) + cos((m−1)t) = 2cos(t)cos(mt) T_m+1(x)+T_m−1(x)=2xT_m(x) T_m+1(x) =2xT_m(x) − T_m−1(x) Niech m+1 = n T_n(x) =2xT_n−1(x) − T_n−2(x) T₁(x) = x T₀(x) = 1 Poszukajmy najpierw zwykłej funkcji tworzącej G(x,t) = ∑_n=0^∞T_n(x)tⁿ ∑_n=2^∞T_n(x)tⁿ = ∑_n=2^∞2xT_n−1(x)tⁿ+∑_n=2^∞−T_n−2(x)tⁿ ∑_n=2^∞T_n(x)tⁿ = 2xt(∑_n=2^∞T_n−1(x)tⁿ⁻¹)−t²(∑_n=2^∞T_n−2(x)tⁿ⁻²) ∑_n=2^∞T_n(x)tⁿ = 2xt(∑_n=1^∞T_n(x)tⁿ)−t²(∑_n=0^∞T_n(x)tⁿ) ∑_n=0^∞T_n(x)tⁿ − 1−xt = 2xt(∑_n=0^∞T_n(x)tⁿ − 1) − t²(∑_n=0^∞T_n(x)tⁿ) G(x,t)(1−2xt+t²) = 1+xt−2xt G(x,t)(1−2xt+t²) = 1 − xt

	1−xt
G(x,t) =
	1−2xt+t2

Tutaj może się wydawać że mamy dwie zmienne ale tak naprawdę rozwijamy względem zmiennej t i x możemy potraktować jako stałą Teraz zajmijmy się wykładniczą funkcją tworzącą (z nią będzie nieco więcej zabawy)

	tn
E(x,t) = ∑n=0∞Tn(x)
	n!

	tn		tn
∑n=2∞Tn(x)		= ∑n=2∞2xTn−1(x)		+
	n!		n!

	tn
∑n=2∞−Tn−2(x)
	n!

	tn		tn
∑n=2∞Tn(x)		= 2x(∑n=2∞Tn−1(x)		)−
	n!		n!

	tn
∑n=2∞Tn−2(x)
	n!

	tn		tn+1
∑n=2∞Tn(x)		= 2x(∑n=1∞Tn(x)		)−
	n!		(n+1)!

	tn+2
∑n=0∞Tn(x)
	(n+2)!

	tn		tn+1
∑n=0∞Tn(x)		− 1 −xt = 2x(∑n=0∞Tn(x)		−t)
	n!		(n+1)!

	tn+2
−∑n=0∞Tn(x)		= 0
	(n+2)!

	tn		tn+1
∑n=0∞Tn(x)		−2x(∑n=0∞Tn(x)		)+
	n!		(n+1)!

	tn+2
∑n=0∞Tn(x)		= 1−xt
	(n+2)!

	tn+2
Niech P(t) = ∑n=0∞Tn(x)
	(n+2)!

wówczas

	(n+2)tn+1
P'(t) = ∑n=0∞Tn(x)
	(n+2)(n+1)!

	tn+1
P'(t) = ∑n=0∞Tn(x)
	(n+1)!

	(n+1)tn
P''(t) = ∑n=0∞Tn(x)
	(n+1)n!

	tn
P''(t) = ∑n=0∞Tn(x)
	n!

Otrzymujemy równanie różniczkowe P''(t) −2xP'(t)+P(t) = 1−xt Zastosujmy do tego równania przekształcenie Laplace

	1		x
(−P'(0)−sP(0)+s2Y(s))−2x(−P(0)+sY(s))+Y(s) =		−
	s		s2

Jeżeli nie znamy wartości początkowych to przyjmujemy za P'(0) oraz P(0) dowolne stałe Ja wiem że one akurat tutaj są równe zero

	s−x
(s2−2xs+1)Y(s) =
	s2

	s−x
Y(s) =
	s2(s2−2xs+1)

Rozłóżmy tę transformatę na sumę ułamków prostych pamiętając że x∊<−1,1>

s−x		A		B		Cs+D
	=		+		+
s2(s2−2xs+1)		s		s2		s2−2xs+1

As(s²−2xs+1)+B(s²−2xs+1)+(Cs+D)s²=s−x A(s³−2xs²+s)+B(s²−2xs+1)+Cs³+Ds² = s−x (A+C)s³+(−2xA+B+D)s²+(A−2xB)s+B = s−x B = −x A+2x²=1 −2xA+B+D = 0 A+C = 0 B = −x A = 1−2x² D = 2xA−B C = −A B = −x A = 1−2x² C = 2x²−1 D = 2x(1−2x²)+x D = 3x − 4x³

	1		1		(2x2−1)s+(3x − 4x3)
Y(s) = (1−2x2)		−x		+
	s		s2		s2−2xs+1

	1		1
Y(s) = (1−2x2)		−x		+
	s		s2

(2x2−1)(s−x)+2x3−x+3x−4x3
(s−x)2+1−x2

	1		1		s−x
Y(s) = (1−2x2)		−x		+(2x2−1)
	s		s2		(s−x)2+1−x2

	2x−2x3	√1−x2
+
	√1−x2	(s−x)2+1−x2

	2x−2x3
P(t) = (1−2x2) −xt + (2x2−1)extcos(t√1−x2)+		extsin(t√1−x2)
	√1−x2

P(t) = (1−2x²) −xt + (2x²−1)e^xtcos(t√1−x²)+2x√1−x²e^xtsin(t√1−x²) Obliczmy teraz P''(t) P'(t) = −x + (2x²−1)(xe^xtcos(t√1−x²)−√1−x²e^xtsin(t√1−x²)) +2x√1−x²(xe^xtsin(t√1−x²)+√1−x²e^xtcos(t√1−x²)) P'(t) = −x + (2x³−x)e^xtcos(t√1−x²)+2x(1−x²)e^xtcos(t√1−x²) −(2x²−1)√1−x²e^xtsin(t√1−x²)+2x²√1−x²e^xtsin(t√1−x²) P'(t) = −x +xe^xtcos(t√1−x²)+√1−x²e^xtsin(t√1−x²) P''(t) = x(xe^xtcos(t√1−x²)−√1−x²e^xtsin(t√1−x²)) +√1−x²(xe^xtsin(t√1−x²)+√1−x²e^xtcos(t√1−x²)) P''(t) = x²e^xtcos(t√1−x²)+(1−x²)e^xtcos(t√1−x²) −x√1−x²e^xtsin(t√1−x²)+x√1−x²sin(t√1−x²) P''(t) = e^xtcos(t√1−x²) zatem E(x,t) = e^xtcos(t√1−x²) Jak wydobyć współczynniki tego szeregu ? Można policzyć

	dn
limt→0		extcos(t√1−x2)
	dtn

Tutaj wikipedie podają funkcje tworzące wyrażone za pomocą liczb zespolonych bo nie uwzględnili tego że x∊<−1;1>

Mila: 4) a_n=a_n−1+n a₀=1 a₁=2 5) a_n=3a_n−1−4n a₀=2 6) a_n=−6a_n−1−9a_n−2+3ⁿ a₁==−3 a₂=36 7) (*) Znajdź funkcję tworzącą dla ciągu a_n=n²+2

Szkolniak: ad 4) ciekawy przykład, trzecia potęga w mianowniku i było trochę ciężej

	x2−x+1
A(x)=
	(1−x)3

	1
an=		(n2+n+2)
	2

I w ogóle nie spodziewałem się że wynik może być parabolą Mariusz, powiem tak, mógłbym przejrzeć cały Twój wpis i może bym zrozumiał, no ale nie do końca mam jakiekolwiek pojęcie gdzie to może mieć zastosowanie Przekształcenie Laplace'a to jest mi obce, jedynie mniej więcej wiem że to do równań różniczkowych ale nic więcej

Szkolniak: ad 5)

	2x2−8x+2
A(x)=
	(1−3x)(1−x)2

a_n=2n−3ⁿ+3 Ten przykład dosyć łatwy, bo już w głowie nawet udało mi się ułożyć równanie

	4x
A(x)−a0=3xA(x)−
	(1−x)2

Swoją drogą tutaj w przykładzie najwyższa potęga w mianowniku to druga, a z jaką najwyższą Ty się spotkałaś, Mila? Bo gdyby była np. ósma to byłoby ciekawie

Mila: (4 i 5) dobrze 1) Zadanie 4 to rozwiązanie zadania tekstowego. Na ile części zostanie podzielona płaszczyzna przez 4 proste, z których żadne dwie proste nie są równoległe, a także żadne 3 proste nie przecinają się w jednym punkcie. Po ustaleniu wzoru rekurencyjnego (jak podałam) masz taki wzór jawny ciągu jak wyznaczyłeś. Dla ciekawości porysuj proste i zobaczysz jak ładnie się wszystko zgadza. 2) Ja nie jestem ekspertem w sprawie f. tworzących. Nigdy nie miałam na studiach teorii na ten temat. Na forum zobaczyłam, że coś takiego jest, z ciekawości poczytałam i coś tam mogę rozwiązać. 3) Jeśli chodzi o potęgę w mianowniku to nie ma większego problemu. Korzystasz z wzoru:

1		m+n n
	=∑(n=0 do∞)		xn− funkcja tworząca
(1−x)m+1

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

Szkolniak: Właśnie chciałem pomyśleć nad jakimś takim wzorem, bo czułem że da się to w ten sposób wyrazić i potem sobie tylko podstawiać odpowiednie liczby według przykładu jaki robimy Ale na razie wolę sobie gdzieś tam na boku to wszystko liczyć i samemu wyprowadzać, bo sprawdzam dzięki temu czy w ogóle wiem o co tu chodzi Rozwiązałem szóste i też dużo roboty, ale wydaje mi się że udało się to zrobić:

	−27x3+27x2−3x		1		5
A(x)=		oraz an=		*3n+		*(−3)n(2n−1)
	(1−3x)(1+3x)2		4		4

Mila: Zgadza się.

Mariusz:

dn
	extcos(t√1−x2)
dtn

tutaj n. pochodną łatwo policzyć ze wzoru Leibniza

Szkolniak: ad 7) a_n=n²+2 n²+2=(n+1)(n+2)−3n

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

oraz

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

zatem:

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

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

W ten sposób się to robi?

Mila: Dobrze.

Szkolniak: Dziękuję Mila oraz Mariusz za nauki w wolnych chwilach może sam będę coś jeszcze z tego tematu robił Wzoru Leibniza na n−tą pochodną nie miałem i nie umiem używać, ten wpis Twój długi Mariusz może sobie zapiszę skrina i kiedyś przejrzę jeszcze raz, na razie aż tak nie chce mi się zagłębiać

Mariusz: Wzór Leibniza na n. pochodną iloczynu jest bardzo podobny do dwumianu Newtona

Szkolniak:

dn		n k
	extcos(t√1−x2)=k=0n∑		(ext)(k)(cos(t√1−x2))(n−k)
dtn

Ale to chyba jeszcze nie koniec? Bo myślałem jeszcze żeby tu wyznaczyć wzór na n−tą pochodną funkcji f(t)=e^xt oraz funkcji g(t)=cos(t√1−x²), ale jeśli tak trzeba to będzie mi ciężko bo niezbyt umiem znajdywać te wzory na n−te pochodne

Mariusz: No tak by to było i aby to dokończyć to właśnie trzeba by było policzyć n. pochodną czynników tak jak podejrzewałeś ale tutaj n. pochodną czynników będzie łatwo policzyć

dn
	ext = xnext
dtn

dn		π
	cos(t√1−x2) = cos(		n+t√1−x2)
dtn		2

Mariusz: a tutaj zapomniałem o pochodnej złożenia

dn		π
	cos(t√1−x2) = (√1−x2)ncos(		n+t√1−x2)
dtn		2

Mariusz: Dobrze by było abyś sobie poćwiczył liczenie n. pochodnych bo jeżeli funkcja tworząca jest wymierna to można ją stosunkowo łatwo rozłożyć ale nie zawsze tak będzie

Mariusz: Bardzo podobnie wygląda rekurencja na wielomiany Hermite H_n+1(x)=2xH_n(x)−2nH_n−1(x) H₀(x) = 1 H₁(x) = 2x tyle że tutaj równania różniczkowego nie rozwiążesz przekształceniem Laplace bo poszukiwana funkcja rośnie szybciej niż funkcja wykładnicza Równanie różniczkowe można jednak łatwo rozwiązać obniżaniem rzędu o ile znamy podstawowe funkcje nieelementarne takie jak funkcja błędu które pojawią się podczas całkowania