wzór rekurencyjny dla puszek

[Fixus]

Witam,
poniżej zadanie, które trochę zbiło mnie z tropu

Wzór rekurencyjny określający liczbę \(\displaystyle{ X(n)}\) ciągów długości n złożony z puszek Coli, Pepsi i wody w którym puszki Coli nie mogą występować obok siebie opisany jest równaniem. Poprawna może być 0,1,2,3, odpowiedzi
a) \(\displaystyle{ X(1) = 3, X(2) = 8, X(n) = 2X(n-1) - X(n-2)}\)
b) \(\displaystyle{ X(1)=3, X(2) = 8, X(n) = X(n-1) - X(n-2)}\)
c) \(\displaystyle{ X(1) = 3, X(2) = 8, X(n) = 2X(n-1) + 2X(n-2)}\)

Nie rozumiem tu jak mam to wyznaczyć skoro nic nie wyznacza/nie odróżnia puszki

[vpprof]

To standardowe zadanie. Załóżmy, że mamy wypisane wszystkie ciągi puszek o długości \(\displaystyle{ n}\). Część z nich kończy się na \(\displaystyle{ C}\) (puszką Coli), a reszta — nie.

Tych ciągów, które nie kończą się na \(\displaystyle{ C}\), jest dwa razy tyle, co ciągów o długości \(\displaystyle{ n-1}\) — bo do każdego poprawnego ciągu można dopisać \(\displaystyle{ P}\) (Pepsi) albo \(\displaystyle{ W}\) (woda), nie naruszając warunku, że w ciągu nie może znaleźć się podciąg \(\displaystyle{ CC}\). Zgoda? To jest pierwszy składnik naszej rekurencyjnej sumy, czyli \(\displaystyle{ 2X(n-1)}\).

Z kolei ciągi, które kończą się na \(\displaystyle{ C}\), jako przedostatni wyraz mają \(\displaystyle{ P}\) lub \(\displaystyle{ W}\). Ile ich jest? Możemy zastosować powyższe rozumowanie: pokazaliśmy, że ciągów o długości \(\displaystyle{ r}\) zakończonych na \(\displaystyle{ P}\) lub \(\displaystyle{ W}\) jest dwa razy tyle, co ciągów o długości \(\displaystyle{ r-1}\). Powyżej \(\displaystyle{ r=n}\), zaś tutaj \(\displaystyle{ r=n-1}\), bo odrzuciwszy ostatnie \(\displaystyle{ C}\) otrzymamy ciągi o długości \(\displaystyle{ n-1}\) zakończone na \(\displaystyle{ P}\) lub \(\displaystyle{ W}\). Jak pokazaliśmy, jest ich \(\displaystyle{ 2X(n-2)}\).

Ostatecznie poprawna jest więc odpowiedź c.