rekurencja rekurencja: Niech c_n będzie liczbą ciągów o długości n zbudowanych z liter ze zbioru {A, B, C, D, E, F, G, H, I}, w których żadne dwie spółgłoski nie występują obok siebie. Znajdź, uzasadnij i rozwiąż równanie rekurencyjne.

kerajs: c_n= 3c_n−1 + 18c_n−2 c₁=9 c₂=45

	4		1
cn=		6n −		(−3)n
	3		3

rekurencja: Ojoj, a skąd taki wynik? Mogę prosić o jakieś rozpisanie?

kerajs: Pierwsza linijka: c_n=3c_n−1+18c_n−2 Zadanie sprowadza się do policzenia ile jest n−elementowych ciągów zawierających wyłącznie A, B, C, D, E, F, G, H, I (9 liter, w tym 3 samogłoski) ograniczonych regułą: po spółgłosce może następować tylko samogłoska. Wprowadziłem ciągi a_n, b_n zliczające ile n−elementowych ciągów kończy się odpowiednio samogłoską lub spółgłoską Ograniczenie narzuca układ równań rekurencyjnych: a_n=3a_n−1+3b_n−1 b_n=6a_n−1 Można by go rozwiązać, jednak w zadaniu pytają o sumę c_n tych ciągów. c_n=a_n+b_n=3a_n−1+3b_n−1+6a_n−1=3c_n−1+6(3a_n−2+3b_n−2)=3c_n−1+18c_n−2 Pozostałe trzy linijki także wymagają wyjaśnień?