Znależć wzór rekurencyjny dla ciągu ternarnego
-
- Użytkownik
- Posty: 18
- Rejestracja: 20 cze 2009, o 18:55
- Płeć: Mężczyzna
- Podziękował: 2 razy
Znależć wzór rekurencyjny dla ciągu ternarnego
Znależć wzór rekurencyjny dla ciągu ternarnego \(\displaystyle{ b _{n}}\) w którym liczba zer i liczba jedynek są parzyste.
Znależć wzór rekurencyjny dla ciągu ternarnego
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}\)
\(\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}\)