Matematyka dyskretna - zależność rekurencyjna w ciągach ternarnych BiednyStudent: Niech sn oznacza liczbę ciągów binarnych o długości n, n ≥ 1, w których przynajmniej raz na dwóch kolejnych pozycjach występuje 0. Wyznacz rekurencyjną zależność dla sn.

wredulus_pospolitus:

	(2n − sn)
sn+2 = 2*sn+1 +
	2

czyli −−−> liczba takich ciągów długości o 1 mniejszej, które spełniają dany warunek + + te ciągi długości o 2 mniejsze, które NIEspełniają jeszcze warunków i są zakończone 1

kerajs: Tak by było gdyby niespełniających zakończonych cyfrą 1 było tyle samo co niespełniających zakończonych cyfrą 0. Czy tak faktycznie jest?

jc: 0 00 01 10 000 100 010 001 101 a_n dobre ciągi zakończone 0 b_n dobre ciągi zakończone 1 a_n+1 = a_n + b_n b_n+1 = a_n a_n+1 = a_n + a_n−1 a₁=1 a₂=2 a_n = f_n+1, ciąg g Fibonacciego s_n = a_n + b_n = f_n+1 + f_n = f_n+2