Podaj jawny wzór a_n i udowodnij indukcyjnie jego poprawność Seba: A) a_n=2a_n−1+a_n−2, a₀=0, a₁=1 B) a_n=5a_n−1+2a_n−2, a₀=1, a₁=1

Mariusz: Wzór jawny znajdziesz w ten sposób A(x)=∑_n=0^∞a_nxⁿ ∑_n=2^∞a_nxⁿ=∑_n=2^∞2a_n−1xⁿ+∑_n=2^∞a_n−2xⁿ Sumujesz od dwójki bo twoja rekurencja zachodzi dla n≥2 ∑_n=2^∞a_nxⁿ=2x(∑_n=2^∞a_n−1xⁿ⁻¹)+x²(∑_n=2^∞a_n−2xⁿ⁻²) ∑_n=2^∞a_nxⁿ=2x(∑_n=1^∞a_nxⁿ)+x²(∑_n=0^∞a_nxⁿ) ∑_n=0^∞a_nxⁿ−0−x=2x(∑_n=0^∞a_nxⁿ−0)+x²(∑_n=0^∞a_nxⁿ) A(x)−x=2xA(x)+x²A(x) A(x)(1−2x−x²)=x

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

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

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

x		a		b
	=		+
(1−(1−√2)x)(1−(1+√2)x)		(1−(1−√2)x))		1−(1+√2)x)

a(1−(1+√2)x)+b(1−(1−√2)x))=x a+b=0 −a(1+√2)−(1−√2)x)b=1 a+b=0 −a−a√2−b+b√2=1 a + b=0 −a√2+b√2=1 b=−a −a√2+b√2=1 b=−a −2a√2=1

	√2
a=−
	4

	√2
b=
	4

x		√2	1		√2
	=−			+b=		U{1}{1−(1+√2)x)
(1−(1−√2)x)(1−(1+√2)x)		4	(1−(1−√2)x))		4

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

	√2		√2
an=		(1+√2)n−		(1−√2)n
	4		4

Co do indukcji to sprawdzasz czy wzór jest poprawny dla n=0 Zakładasz że jest poprawny dla n=k i sprawdzasz czy jest poprawny dla następnika czyli dla n = k+1

Mariusz: Dla porównania drugi przykład z użyciem równania charakterystycznego a_n=5a_n−1+2a_n−2, a₀=1, a₁=1 λⁿ=5λⁿ⁻¹ + 2λⁿ⁻² λ²=5λ+2 λ²−5λ−2=0

	5		25		8
(λ−		)2−		−		=0
	2		4		4

	5		33
(λ−		)2−		=0
	2		4

	5−√33		5+√33
(λ−		)(λ−		)=0
	2		2

	5−√33		5+√33
an=C1(		)n+C2(		)n
	2		2

a₀=C₁+C₂

	5−√33		5+√33
a1=		C1+		C2
	2		2

C₁+C₂=1

5−√33		5+√33
	C1+		C2=1
2		2

C₁+C₂=1

5		5		√33		√33
	C1+		C1+		C2−		C1=1
2		2		2		2

C₁+C₂=1

5		√33		√33
	+		C2−		C1=1
2		2		2

C₁+C₂=1

√33		√33		3
	C2−		C1=−
2		2		2

C₁+C₂=1

	√33
−C1+C2=−
	11

	11−√33
2C2=
	11

	11+√33
2C1=
	11

11+√33		5−√33		11−√33		5+√33
	(		)n+		(		)n
22		2		22		2