Rekurencja, róże Piotrek: W kolejce do Walerii ustawiło się w kolejności alfabetycznej n jej kolegów, z których każdy chciał jej wręczyć jedną lub trzy róże. Jeśli któryś kolega wręczył jej trzy róże to Waleria dziękowała mu na tyle długo, że następny w kolejce zniecierpliwiony rezygnował i odchodził nie wręczając róż wcale. Podaj zależność rekurencyjną na liczbę sposobów w jaki mogło przebiegać wręczanie róż Walerii.

kerajs: S_n=S_n−1+S_n−2 ∧ S₁=2 ∧ S₂=3

Piotrek: A mógłbyś wyjaśnić, jak do tego doszedłeś?

kerajs: Odchodzącego będę oznaczał cyfrą 0. Zadanie sprowadza się do policzenia ile jest n−elementowych ciągów zawierających wyłącznie cyfry 1,3,0 i graniczonych regułami: − po 1 może następować 1 lub 3 − po 3 może być tylko 0 − po 0 może następować 1 lub 3 wprowadziłem ciągi a_n, b_n, c_n zliczające ile n−elementowych ciągów kończy się odpowiednio cyfrą 1,3 lub 0 Ograniczenia narzucają układ równań rekurencyjnych: a_n=a_n−1+c_n−1 b_n=a_n−1+c_n−1 c_n=b_n−1 Można by go rozwiązać, jednak w zadaniu pytają o sumę S_n tych ciągów. S_n=a_n+b_n+c_n =a_n−1+c_n−1+a_n−1+c_n−1+b_n−1= =S_n−1+a_n−1+c_n−1=S_n−1+(a_n−2+c_n−2)+b_n−2=S_n−1+S_n−2 I to jest zależnością o którą pyta autor zadania. Wzór ogólny dostanie się zliczając ciągi S₁: { (1), (3)} i S₂:{(1,1), (1.3), (3,0)} i rozwiązując równanie rekurencyjne, jednak od razu narzuca się skojarzenie z przesuniętym ciągiem Fibonacciego, a wzór Bineta jest powszechnie znany.

Piotrek: Dziękuję bardzo, już wszystko jasne