Rekurencja ciągu ternarnego

[math_is_killing_me]

Ile jest różnych ciągów ternarnych (tj.składających się z 0,1,2) o długości n, takich że po
cyfrach 0 lub 1 zawsze stoi 2? Uloz odpowiednie rownanie rekurencyjne i rozwiaz je.

Nie mam pojęcia jak się za to wziąć:/

[arek1357]

\(\displaystyle{ a_{1}=3}\)

\(\displaystyle{ a_{n+1}=2a_{n}+(-1)^n}\)

[vpprof]

No jeśli rekurencja, to musisz się zastanowić, jakimi sposobami z ciągu \(\displaystyle{ n}\)-wyrazowego można utworzyć ciąg \(\displaystyle{ n+1}\)-wyrazowy — czyli co można dopisać na końcu i ile \(\displaystyle{ n+1}\)-wyrazowych ciągów można utworzyć z każdego \(\displaystyle{ n}\)-wyrazowego. To będzie twoje równanie rekurencyjne.

Potem wstawiasz warunek brzegowy, czyli pokazujesz, że dla \(\displaystyle{ n=1}\) są \(\displaystyle{ 3}\) możliwe ciągi: \(\displaystyle{ 0,\ 1,\ 2}\) i gotowe.

Oznacz sobie jakoś liczbę ciągów \(\displaystyle{ n}\)-wyrazowych, np. \(\displaystyle{ f(n)}\).

EDIT: Acha, masz jeszcze rozwiązać rekurencję. Najłatwiej funkcjami tworzącymi. Ale najpierw w ogóle dojdź do tej rekurencji

[arek1357]

\(\displaystyle{ \sum_{i=1}^{ \infty }a_{n+1}x^n=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)

\(\displaystyle{ \frac{1}{x} \sum_{i=1}^{ \infty }a_{n+1}x^{n+1}=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)

\(\displaystyle{ \frac{1}{x}( \sum_{i=1}^{ \infty }a_{n}x^{n}-a_{1}x)=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)

niech:

\(\displaystyle{ S= \sum_{i=1}^{ \infty }a_{n}x^{n}}\)

mamy:

\(\displaystyle{ \frac{1}{x}S-3=2S+\sum_{i=1}^{ \infty }(-1)^nx^n}\)

\(\displaystyle{ S( \frac{1}{x}-2 )=3- \frac{x}{1+x}}\)

Po przekształceniach:

\(\displaystyle{ S=-x \frac{2x+3}{2(x+1)(x- \frac{1}{2} )}}\)