aa Hugo: Rozwiązać następujące rekurencje liniowe a) S_n+1 = s_n + 3s_n−1 jak się za takie zadanie zabrać? z góry dziękuję za pomoc

Adamm: x²−x−3 = 0 Δ = 13

	1±√13
x =
	2

	1−√13		1+√13
sn = c1(		)n+c2(		)n
	2		2

Mila: A warunki początkowe?

Hugo: właśnie nic nie mam, poza tym co napisałem warunki początkowe to rozumiem że s₀ i s₁ ?

Hugo: @Adamm dziękuję ! spróbuje machnąć kilka kolejnych przykładów sam

Hugo: c') x² = 2x +3 x² −2x −3 = 0 delta = 4 +4*3 = 16 C1 = 2+4)/2 = 3 C2 = 2−4)/2 = −1 sn = C1(−1)ⁿ + C23ⁿ , zgodnie z kluczem b) S_n+1 = −4s_n +5s_n−1 x² = −4x + 5 x² +4x −5 = 0 delta = b² − 4ac = 16+20 = 36 >0 C2 = (−4−6)/2 = −5 C1 = (−4+6)/2 = 1 s_n = C2(−5)ⁿ + C1ⁿ dobrze wdl klucza

Hugo: co w przypadku takiego trudniejszego: d') S_n+1 = 6s_n − 5s_n−1 ? s₀ = 5 , s₁ = 1 klucz: s_n = 6 − 5ⁿ

Satan: λ² − 6λ + 5 = 0 λ₁ = 1 λ₂ = 5 S_n = a(1)ⁿ + b(5)² S₀ = a(1)⁰ + b(5)⁰ S₁ = a(1)¹ + b(5)¹ Stąd mamy: a + b = 5 a + 5b = 1 Czyli: a = 1 − 5b 1 − 4b = 5 4b = −4 b = −1 Czyli a = 6 Więc: S_n = 6(1)² + (−1)(5)² S_n = 6 − 5ⁿ

Hugo: x = 6x − 5 x − 6x + 5 = 0 delta = 36+20 = 54 √54 = 3√6 = p x1= (6+p)/2 x2= (6−p)/2 s_n = C1*((6+p)/2)ⁿ + C1*((6−p)/2)ⁿ cos to chyba zle jest

Satan: Korekta: W drugiej linijce od dołu zamiast kwadratu powinno być "n"

Satan: Hugo, bo: Δ = b² − 4ac Czyli: Δ = (−6)² −4*1*5 = 36 − 20

Hugo: @Satan czyli wgl bez delty, samo podstawienia dzieki

Hugo: racja, rozumiem ze jak bym dał tam dobry znak to tez moglo by wyjsc, ale Twoje lepsze !

Satan: Generalnie to, co napisałem korzysta z tego, co napisał Adamm, bo po drodze powinienem jeszcze trochę się narobić, by dotrzeć do tej postaci

Mila: s_n+1 = 6s_n − 5s_n−1 − równanie jednorodne s₀ = 5 , s₁ = 1 1) równanie charakterystyczne: x²−6x+5=0 x₁=1 lub x₂=5 2) Rozwiązanie ma postać: s_n=A*1ⁿ+B*5ⁿ Z warunków początkowych wyznaczamy wsp. A i B s₀=5=A+B*5⁰ s₁=1=A+B*5¹ A+B=5 A+5B=1 ===== odejmuję stronami −4B=4, B=−1 A+(−1)=5 A=6, B=−1 s_n=6−5ⁿ ==========

Mila: s_n+1 = 6s_n − 5s_n−1 Możesz sprawdzić ( np. na kolokwium) Z rekurencji: s₂=6s₁−5s₀=6*1−5*5=−19 s₃=6s₂−5s₁=6*(−19)−5*1=−114−5=−119 Wg otrzymanego wzoru: s₂=6−5²=−19 s₃=6−5³=6−125=−119

Hugo: Fajne dziękuję

Mila:

Hugo: idąc kolejnymi przykładami... mamy takie 2ⁿ S_n+1 = 3s_n−2s_n−1 + 2ⁿ nie ma podanych: s₀ i s₁ to można tak wyciąć? bez 2ⁿ? x² = 3x −2 x² −3 +2 = 0 delta = 9−8 = 1 C1 = (3+1)/2 = 2 C2 = (3−1)/2 = 1 S_n = C1 * 2ⁿ + C2 * 1ⁿ co należy uczynić z tym 2ⁿ? n(An+B)?

Mila: (*) s_n+1 = 3s_n−2s_n−1 + 2ⁿ− równanie niejednorodne x² −3x +2 = 0 r. charakterystyczne x₁=2 lub x₂=1 s_n⁽¹⁾=A*2ⁿ+B s_n⁽²⁾=C*n*2ⁿ, (gdyby 2 nie było roz. równania char. to byłoby : C*2ⁿ) s_n=s_n⁽¹⁾+s_n⁽²⁾ 1) wyznaczamy C , podstawiamy do (*) C*n*2ⁿ C*(n+1)*2ⁿ⁺¹=3*C*n*2ⁿ−2*C*(n−1)*2ⁿ⁻¹+2ⁿ /:2ⁿ 2C(n+1)=3Cn−C(n−1)+1 2C*n+2C=3C*n−C*n+C+1 C=1 s_n⁽²⁾=n*2ⁿ s_n=A*2ⁿ+B+n*2ⁿ Do wyznaczenia A i B potrzebne a₀ ,a₁ Posprawdzaj rachunki

Mila: Dobranoc

Mariusz: Hugo na dyskretnej dla informatyków powinieneś mieć też funkcje tworzące (do rozwiązywania równań rekurencyjnych przydają się dwie zwykła, geometryczna i wykładnicza zwykła dla ciągu jedynek generuje szereg geometryczny wykładnicza dla ciągu jedynek generuje funkcję wykładniczą − a konkretnie jej rozwinięcie w szereg) s_n+1 = s_n + 3s_n−1 s_n=s_n−1+3s_n−2 S(x)=∑_n=0^∞s_nxⁿ ∑_n=2^∞s_nxⁿ=∑_n=2^∞s_n−1xⁿ+∑_n=2^∞3s_n−2xⁿ ∑_n=2^∞s_nxⁿ=x(∑_n=1^∞s_nxⁿ)+3x²(∑_n=0^∞s_nxⁿ) ∑_n=0^∞s_nxⁿ−s₀−s₁x=x(∑_n=0^∞s_nxⁿ−s₀)+3x²(∑_n=0^∞s_nxⁿ) S(x)−s₀−s₁x=x(S(x)−s₀)+3x²S(x) S(x)−s₀−s₁x=xS(x)−xs₀+3x²S(x) S(x)(1−x−3x²)=s₀+(s₁−s₀)x

	s0+(s1−s0)x
S(x)=
	1−x−3x2

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

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

A+B=s₀ −λ₂A−λ₁B=s₁−s₀ λ₂A+λ₂B=λ₂s₀ −λ₂A−λ₁B=s₁−s₀ (λ₂−λ₁)B=s₁+(λ₂−1)s₀

	s1+(λ2−1)s0
B=
	λ2−λ1

λ₁A+λ₁B=λ₁s₀ −λ₂A−λ₁B=s₁−s₀ (λ₁−λ₂)A=s₁+(λ₁−1)s₀

	s1+(λ1−1)s0
A=−
	λ2−λ1

	s1+(λ1−1)s0
A=−
	λ2−λ1

	s1+(λ2−1)s0
B=
	λ2−λ1

(1−λ₁x)(1−λ₂x)=1−x−3x² 1−λ₂x−λ₁x+λ₁λ₂x²=1−x−3x² 1−(λ₁+λ₂)x+λ₁λ₂x²=1−x−3x² λ₁+λ₂=1 λ₁λ₂=−3 λ²−λ−3=0

	1−√13
λ1=
	2

	1+√13
λ2=
	2

(1+√13)−(1−√13)
	=√13
2

	1+√13   −s1+ s0   2
A=
	√13

	1−√13   s1− s0   2
B=
	√13

	1+√13   −s1+ s0   2		1
S(x)=				+
	√13		1−√13   1−( )x   2

1−√13   s1− s0   2	1
√13	1+√13   1−( )x   2

	1−√13		1+√13
sn=A(		)n+B(		)}{n}
	2		2