Znależć wzór rekurencyjny dla ciągu ternarnego

[widowisko3]

Znależć wzór rekurencyjny dla ciągu ternarnego \(\displaystyle{ b _{n}}\) w którym liczba zer i liczba jedynek są parzyste.

[abc666]

Niech
\(\displaystyle{ c_n}\) - liczba ciągów długości \(\displaystyle{ n}\), w których liczba zer jest nieparzysta a jedynek parzysta
\(\displaystyle{ d_n}\) - liczba ciągów długości \(\displaystyle{ n}\), w których liczba zer jest parzysta a jedynek nieparzysta

Wtedy
\(\displaystyle{ b_n=b_{n-1}+c_{n-1}+d_{n-1}}\)
Do ciągu długości n-1 możemy dokleić tylko i wyłącznie
- dwójkę jeśli liczba zer i jedynek jest parzysta
- jedynkę jeśli liczba jedynek jest nieparzysta
- zero jeśli liczba zer jest nieparzysta

Trzeba jeszcze wyznaczyć wzory \(\displaystyle{ c_n}\) i \(\displaystyle{ d_n}\) (analogicznie jak \(\displaystyle{ b_n}\))
\(\displaystyle{ c_n=c_{n-1}+b_{n-1} \\
d_n=d_{n-1}+b_{n-1}}\)

Teraz ze wzoru \(\displaystyle{ b_n}\) wyznaczamy
\(\displaystyle{ c_{n+1}+b_{n-1}=b_{n}-d_{n-1}}\)
i podstawiamy do wzoru \(\displaystyle{ c_n}\) otrzymując
\(\displaystyle{ c_n=b_n-d_{n-1}}\) oraz
\(\displaystyle{ d_n=d_{n-1}+b_{n-1}}\)
dodajemy stronami te wzory i dostajemy
\(\displaystyle{ c_n+d_n=b_n+b_{n-1}}\) a z tego
\(\displaystyle{ c_{n-1}+d_{n-1}=b_{n-1}+b_{n-2}}\)
wracając do pierwotnego wzoru na \(\displaystyle{ b_n}\) i wykorzystując ostatnią równość dostajemy

\(\displaystyle{ b_n=2b_{n-1}+b_{n-2}}\)

Z warunkami początkowymi
\(\displaystyle{ b_1=1 \\
b_2=3}\)