Równanie rekurencyjne Mati: Cześć. Mam do rozwiązania takie równanie rekurencyjne.

	⎧	1 dla n=0
T(n)=	⎩	2T(n−1)−9 dla n>0

Próbuje to rozwiązać metodą rekurencyjną i wyszło mi takie coś: T(1)=0 T(2)=−9 T(3)=−27 T(4)=−63 T(5)=−135 Jak wyprowadzić wzór, bo żadnej zależności pomiędzy tymi liczbami nie widzę

ICSP: T(0) = 1 T(1) = 2*T(0) − 9 T(2) = 2*[2T(0) − 9] − 9 = 2²*T[0] − 2*9 − 9 T(3) = 2*[2²*T[0] − 2*9 − 9] − 9 = 2³*T[0] − 9(2² + 2 + 1) T(4) = ... = 2⁴*T[0] − 9*(2³ + 2² + 2 + 1) ... T(n) = 2ⁿ*T[0] − 9(2ⁿ⁻¹ + ... + 1) = ...

Mati: Czyli to wystarczy podać jako rozwiązanie? T(n) = 2ⁿ*T[0] − 9(2ⁿ⁻¹ + ... + 1)

ICSP: T[0] masz dane Wyrażenie 1 + ... + 2ⁿ⁻¹ możesz przedstawić ładniej (to suma ciągu geometryczne)

Mariusz: Wygodniej jest zastosować funkcję tworzącą G(x)=∑_n=0ⁿT_nxⁿ ∑_n=1^∞T_nxⁿ=∑_n=1^∞2T_n−1xⁿ−∑_n=1^∞9xⁿ

	9x
∑n=1∞Tnxn=2x(∑n=1∞Tn−1xn−1)−
	1−x

	9x
∑n=0∞Tnxn−1=2x(∑n=0∞Tnxn)−
	1−x

	9x
G(x)(1−2x)=1−
	1−x

	1−10x
G(x)(1−2x)=
	1−x

	1−10x
G(x)=
	(1−x)(1−2x)

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

A(1−x)+B(1−2x)=1−10x A+B=1 −A−2B=−10 B=9 A=−8

	8		9
G(x)=−		+
	1−2x		1−x

G(x)=−8(∑_n=0^∞2ⁿxⁿ)+9(∑_n=0^∞xⁿ) G(x)=∑_n=0^∞(−8*2ⁿ+9)xⁿ T_n=−8*2ⁿ+9

Mila: T(0)=1 T(n)=2T(n−1)−9 1) Równanie charakterystyczne: x−2=0 ⇔x=2 T₁(n)=A*2ⁿ

	−9
T2(n)=		=9
	1−2

2) Przewidywana postać rozwiązania: T(n)=A*2ⁿ+9 T(0)=1=A*2⁰+9 A=−8 T(n)=−8*2ⁿ+9 ===========