rekurencja Asia: Rozwiąż równanie rekurencyjne: a) T₀ = 2 2T_n = n* T_n−1 + 2n! b) T₀ = 1

	Tn−1
Tn =		+ 2n
	2

Zadanie polega na usunięciu rekurencji, czy mógłby ktoś wytłumaczyć krok po kroku, bo mam jeden przykład rozwiązany, ale totalnie nie wiem skąd co się bierze

Mariusz: a) Wykładnicza funkcja tworząca

	an
A(x)=∑n=0∞		xn
	n!

	an		1		nan−1		n!
∑n=1∞		xn=		∑n=1∞		xn+∑n=1∞		xn
	n!		2		n!		n!

	an		1		an		x
∑n=0∞		xn−2=		x∑n=0∞		xn+
	n!		2		n!		1−x

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

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

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

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

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

	2
A(x)=
	1−x

T_n=2n! b) Zwykła funkcja tworząca wystarczy A(x)=∑_n=0^∞a_nxⁿ

	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

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

A(x)=∑_n=0^∞a_nxⁿ

	1
∑n=1∞anxn=∑n=1∞		an−1xn+∑n=1∞2nxn
	2

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

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

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

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

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

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

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

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

A(2−4x+2x²)+B(2−3x+x²)+C(2−x)=2+2x² 2A+2B+2C=2 −4A−3B−C=0 2A+B=2 C=4 −4A−3B=4 4A+2B=4 B=−8 2A=2+8 A=5 B=−8 C=4

	5		8		4
A(x)=		−		+
	1   1− x   2		1−x		(1−x)2

	1
Tn=5(		)n−8+4(n+1)
	2

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

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

Mila: Trochę krócej: b) T(0)=1

	1
T(n)=		t(n−1)+2n
	2

	1		1
1) x2−		x=0 ⇔x=0 lub x=
	2		2

	1
2) T(n)=A*(		)n+B*n+C
	2

	1
3) B*n+C=		*[B*(n−1)+C]+2n
	2

	1		1		1
B*n+C=		B*n−		B+		C+2n
	2		2		2

1		1		1		1		1		1
	B*n+		C+		C=2n ⇔		B=2 i		C+		B=0
2		2		2		2		2		2

B=4 i C=−4 4)

	1
T(n)=A*(		)n+4n−4
	2

	1
T(0)=1=A*(		)0−4
	2

A=5

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

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

Mila: a) Na piechotę.

	n
T(n)=		*T(n−1)+n!
	2

T(0)=2=2*0! T(1)=1+1!=2=2*1! T(2)=1*2+2!=2*2!

	3
T(3)=		*4+3!=12=2*3!
	2

	4
T(4)=		*12+4!=24+24=48=2*4!
	2

T(n)=2n!

Mariusz: Oprócz funkcji tworzącej można było użyć czynnika sumacyjnego

Mila: Napracowałeś się, szczególnie w (a) Nie pamiętałam o wykładniczej f. tworzącej .

Mariusz: Czynnikiem sumacyjnym T₀=2 2T_n=nT_n−1+2n! a_n=2 b_n=n c_n=2n!

	an−1
sn=		sn−1
	bn

	2
sn=		sn−1
	n

	2
2Tnsn=		nTn−1sn−1+2n!sn
	n

U_n=2T_ns_n U_n=U_n−1+2n!s_n U_n=U₀+2∑_k=1ⁿk!s_k U_n=4s₀+2∑_k=1ⁿk!s_k

	1
Tn=		(4s0+2∑k=1nk!sk)
	2sn

	1
Tn=		(2s0+∑k=1nk!sk)
	sn

s₀=1

	2n
sn=
	n!

	n!		2k
Tn=		(2+∑k=1nk!		)
	2n		k!

	n!
Tn=		(2+∑k=1n2k)
	2n

	n!		1−2n
Tn=		(2+2		)
	2n		1−2

	n!
Tn=		(2+2n+1−2)
	2n

	n!
Tn=		* 2n+1
	2n

T_n=2n! T₀=1

	1
Tn=		Tn−1+2n
	2

a_n=1

	1
bn=
	2

c_n=2n

	1
sn=		sn−1
	1   2

s_n=2s_n−1

	1
Tnsn=		Tn−12sn−1+2nsn
	2

U_n=T_ns_n U_n=U_n−1+2ns_n U_n=U₀+2∑_k=1ⁿks_k U_n=s₀+2∑_k=1ⁿks_k s₀=1 s_n=2ⁿ

	1
Tn=		(1+2∑k=1nk2k)
	2n

Tutaj przyda się sumowanie przez części ∑(x2^x)δx=x2^x−∑2^x+1δx ∑(x2^x)δx=x2^x−2^x+1 ∑_k=0ⁿk2ⁿ=∑₀ⁿ⁺¹x2^xδx=(n+1−2)2ⁿ⁺¹−(0−2)2⁰ ∑_k=0ⁿk2ⁿ=(n−1)2ⁿ⁺¹+2 ∑_k=1ⁿk2ⁿ=(n−1)2ⁿ⁺¹+2−0

	1
Tn=		(1+2((n−1)2n+1+2))
	2n

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

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