Znajdz równanie rekurencyjne dla liczby n-elementowych ciagó

[Kogut18]

Znajdz równanie rekurencyjne dla liczby \(\displaystyle{ n}\)-elementowych ciagów ternarnych, w których:
(a) liczba zer jest parzysta,
(b) liczba zer i liczba jedynek sa parzyste
dla liczb \(\displaystyle{ \{0,1,2\}}\)

W przykładzie a wyszło mi
\(\displaystyle{ 3^{n-1} + S_{n-1}}\)

Ponieważ 0 v 1 v 2
dla 1 i 2 będzie \(\displaystyle{ S_{n-1}}\) a dla 0
\(\displaystyle{ 3^{n-1} + S_{n-1}}\)
Gdy od wszystkich mozliwosci w danym n odejmiemy mozliwosci parzyste z \(\displaystyle{ 0}\) zostana same nie parzyste i gdy dodamy jedno \(\displaystyle{ 0}\) otrzymamy parzysta ilosc zer.
Czy dobrze rozumiem ?
Z góry dziękuje serdecznie za pomoc !

[Premislav]

(a)
Oznaczmy przez \(\displaystyle{ S_n}\) liczbę ciągów ternarnych o \(\displaystyle{ n}\) wyrazach spełniających warunki, jak u Ciebie;
jeśli w ciągu ternarnym o \(\displaystyle{ n}\) wyrazach jest parzyście wiele zer, to dopisując dowolną liczbę z \(\displaystyle{ \left\{ 0,1,2\right\}}\) różną od zera (tj. jedynkę bądź dwójkę) dalej otrzymamy parzyście wiele zer. Natomiast jeśli w n-wyrazowym ciągu jest nieparzyście wiele zer, to dopisując na końcu zero, mamy ciąg \(\displaystyle{ n+1}\)-wyrazowy o parzystej liczbie zer. Wszystkich n-wyrazowych ciągów ternarnych jest oczywiście \(\displaystyle{ 3^n}\). Zatem:
\(\displaystyle{ S_{n+1}=2\cdot S_n+1\cdot (3^n-S_n)=3^n+S_n, tj. S_n=3^{n-1}+S_{n-1}}\), zgadza się.

b)
To już trudniejsze. Jest \(\displaystyle{ 3^n}\) ciągów ternarnych długości \(\displaystyle{ n}\), powiedzmy, że z tego mamy \(\displaystyle{ S_n}\) ciągów, w których jest zarówno parzyście wiele zer, jak i parzyście wiele jedynek.
Zatem mamy \(\displaystyle{ 3^n-S_n}\) ciągów ternarnych długości \(\displaystyle{ n}\), które nam nie pasują. Wszędzie dalej są ciągi ternarne długości \(\displaystyle{ n}\). Oznaczmy przez \(\displaystyle{ X_n}\) liczbę tych ciągów, które mają parzyście wiele zer, ale nieparzyście wiele jedynek, przez \(\displaystyle{ Y_n}\) liczbę ciągów o nieparzyście wielu zerach i parzyście wielu jedynkach oraz przez \(\displaystyle{ Z_n}\) liczbę ciągów o nieparzyście wielu zerach i nieparzyście wielu jedynkach. Oczywiście jest
\(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\)
Ponadto mamy
(1) \(\displaystyle{ X_{n+1}=X_n+S_n+Z_n}\)
Wyjaśnienie: patrzymy, w jaki sposób z ciągu długości \(\displaystyle{ n}\) możemy zrobić ciąg długości \(\displaystyle{ n+1}\) mający parzyście wiele zer, lecz nieparzyście wiele jedynek. Do spełniającego ten warunek n-wyrazowego dopisujemy dwójkę, do mającego zarówno parzyście wiele zer, jak i parzyście wiele jedynek dopisujemy jedynkę, do mającego nieparzyście wiele zer i nieparzyście wiele jedynek dopisujemy zero.
Jest także
(2) \(\displaystyle{ Y_{n+1}=Y_n+S_n+Z_n}\) - zupełnie analogicznie, jak z \(\displaystyle{ X_n}\), a ponadto
(3) \(\displaystyle{ Z_{n+1}=X_n+Y_n+Z_n}\)
- do n-wyrazowego ciągu o parzyście wielu zerach i nieparzyście wielu jedynkach dopisujemy na końcu zero, do n-wyrazowego ciągu o nieparzyście wielu zerach i parzyście wielu jedynkach dopisujemy na końcu jedynkę, do n-wyrazowego ciągu o nieparzyście wielu zerach i nieparzyście wielu jedynkach dopisujemy na końcu dwójkę.
Po dodaniu stronami zależności rekurencyjnych (1), (2), (3) dostajemy
\(\displaystyle{ X_{n+1}+Y_{n+1}+Z_{n+1}=2S_n+2(X_n+Y_n+Z_n)+Z_n}\)
i teraz korzystając dwukrotnie z: \(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\) otrzymujemy
\(\displaystyle{ 3^{n+1}-S_{n+1}=2S_n+2(3^n-S_n)+Z_n}\)
czyli
\(\displaystyle{ S_{n+1}=3^n-Z_n}\)
Z drugiej strony, wykorzystując powyższe zależności mamy
\(\displaystyle{ Z_{n+1}=X_n+Y_n+Z_n=3^n-S_n}\), czyli
\(\displaystyle{ Z_n=3^{n-1}-S_{n-1}}\)
i ostatecznie
\(\displaystyle{ S_{n+1}=3^n-Z_n=3^n-3^{n-1}+S_{n-1}=2\cdot 3^{n-1}+S_{n-1}}\)


Uff, trochę się napracowałem. Zapewne da się to ładniej zrobić, ale trzeba mieć mózg, ja niestety nie spełniam tego warunku.

[arek1357]

Tak na szybkiego a propo b) dołożę swoje trzy grosze ale na wzór jawny tzn. na funkcję charakterystyczną:

sugestia, że ilość możliwości powinno być:

\(\displaystyle{ a_{n}= \sum_{2x+2y+z=n}^{} \frac{n!}{(2x)!(2y)!z!}}\)

lub:

\(\displaystyle{ n! \sum_{}^{} \frac{1}{(2i)!(2j)!(n-2i-2j)!}}\)

co sugeruje nam takową funkcję:

\(\displaystyle{ (1+ \frac{1}{2!}x^2+ \frac{1}{4!}x^4+ \frac{1}{6!}x^6+.....)^2(1+x+ \frac{1}{2!}x^2+ \frac{1}{3!}x^3+...)}\)


co daje nam funkcję charakterystyczną:

\(\displaystyle{ f(x)=e^x \left( \sum_{n=0}^{ \infty } \frac{1}{(2n)!}x^{2n}\right)^2 = e^x \frac{\left( e^{-x}+e^x\right)^2 }{4}}\)

zwinąć rozłożyć a wynik pomnożyć przez: \(\displaystyle{ n!}\)

jak rozłożymy tę funkcję w szereg otrzymamy:

\(\displaystyle{ f(x)= \frac{e^{-x}+2e^x+e^{3x}}{4}= \frac{1}{4} \sum_{n=0}^{ \infty } \frac{3^n+(-1)^n+2}{n!}x^n}\)

więc nasz ciąg powinien wyglądać następująco:


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

Ja może przeproszę bo się tu dowaliłem niechcący i nie zrobiłem tak jak trzeba bo trzeba było znaleźć wzór
rekurencyjny a nie jawny, ale można z jawnego w końcu przejść do rekurencji którą tak pięknie zrobił Premislaw. (Po co mam powielać Premislawa jest niepowtarzalny). Szkoda że nie napisałeś w swoim wzorze wartości początkowe tzn\(\displaystyle{ S_{0}, S_{1}}\).

Wtedy indukcyjnie można udowodnić równoważność tych wzorów.

Tylko ja użyłem zmiennej \(\displaystyle{ a_{n}}\).

Ale się poprawię i napiszę:

mój:

\(\displaystyle{ S_{n}= \frac{3^n+(-1)^n+2}{4}}\)

Premislawa:

\(\displaystyle{ S_{n+1}=S_{n-1}+2 \cdot 3^{n-1}}\)



Spróbujmy udowodnić równoważność tych wzorów, przepiszę wzór Premislawa:

\(\displaystyle{ S_{n+1}-S_{n-1}=2 \cdot 3^{n-1}}\)

a teraz moje:

\(\displaystyle{ S_{n+1}-S_{n-1}= \frac{3^{n+1}+(-1)^{n+1}+2-3^{n-1}-(-1)^{n-1}-2}{4}= \frac{ \frac{8}{3} \cdot 3^n-(-1)^n+(-1)^n }{4}=2 \cdot 3^{n-1}}\)

Więc się zgadza wzory są równoważne brawa dla Premislawa...

Niech tylko dopisze warunki początkowe(Bo chyba \(\displaystyle{ S_{0}}\) nie ma sensu) a dostanie owacje na stojąco...


poprawiłem...