Podaj wzór rekurencyjny i wyznacz wzór jawny

[Philip]

Witam,
mam takie oto zadanie:
Dany jest alfabet \(\displaystyle{ A=\{x,y,z\}}\). Podaj wzór rekurencyjny na liczbę słów \(\displaystyle{ t_n}\) długości \(\displaystyle{ n}\) utworzonych z alfabetu \(\displaystyle{ A}\), które zawierają parzystą liczbę liter \(\displaystyle{ z}\). Zamień wzór rekurencyjny na wzór jawny oraz wykaż, że wzór jawny jest poprawny.

No to ja założyłem, że jeżeli w danym ciągu jest \(\displaystyle{ 0}\) liter \(\displaystyle{ z}\) to jest to parzysta liczba \(\displaystyle{ z}\), bo \(\displaystyle{ 0}\) jest parzyste, więc wziąłem również pod uwagę wyrazy, które tegoż 'z' nie zawierają. Przy policzeniu ilości ciągów dla \(\displaystyle{ n=1, n=2}\) oraz \(\displaystyle{ n=3}\) zauważyłem taką zależność, że wzór rekurencyjny wyszedł mi tak:
\(\displaystyle{ a_{n}=2a_{n-1}+2a_{n-2}}\)

Czy to poprawny tok rozumowania oraz równanie?

[Euler41]

Czy litery \(\displaystyle{ x, y}\) mogą się powtarzać?

[leg14]

Czy to poprawny tok rozumowania oraz równanie?

Żaden tok rozumowania się nie pojawił, równanie również nie wygląda na poprawne.
Weź słowo długości \(\displaystyle{ n}\), jeśli kończy się na \(\displaystyle{ x \vee y}\), to po obcięciu ostatniej literki dostajesz element \(\displaystyle{ a_{n-1}}\) - czyli łącznie takich ciągów długości n nie kończących się na z masz \(\displaystyle{ 2a_{n-1}}\). Co natomiast dzieje się, gdy ciąg kończy się na z?

[a4karo]

A może tak: Niech \(\displaystyle{ a_n}\) oznacza ilość słów długości \(\displaystyle{ n}\) z parzystą ilościa \(\displaystyle{ z}\)-tów, a \(\displaystyle{ b_n}\) z nieparzystą.
Oczywiście \(\displaystyle{ a_n+b_n=???}\)
Teraz zastanów się jak powstają słowa długości \(\displaystyle{ n+1}\) za słów długości \(\displaystyle{ n}\)?

[Philip]

A może tak: Niech \(\displaystyle{ a_n}\) oznacza ilość słów długości \(\displaystyle{ n}\) z parzystą ilościa \(\displaystyle{ z}\)-tów, a \(\displaystyle{ b_n}\) z nieparzystą.
Oczywiście \(\displaystyle{ a_n+b_n=???}\)
Teraz zastanów się jak powstają słowa długości \(\displaystyle{ n+1}\) za słów długości \(\displaystyle{ n}\)?

Powstają w ten sposób, że dodaję do każdego po x oraz y, bo nic to nie zmienia oraz dodaję "z" tylko tam gdzie ilość "z" jest nieparzysta?

Czy to poprawny tok rozumowania oraz równanie?

Żaden tok rozumowania się nie pojawił, równanie również nie wygląda na poprawne.
Weź słowo długości \(\displaystyle{ n}\), jeśli kończy się na \(\displaystyle{ x \vee y}\), to po obcięciu ostatniej literki dostajesz element \(\displaystyle{ a_{n-1}}\) - czyli łącznie takich ciągów długości n nie kończących się na z masz \(\displaystyle{ 2a_{n-1}}\). Co natomiast dzieje się, gdy ciąg kończy się na z?

Zakładając, że jeżeli ciąg ma z w sobie to jest ich parzysta liczba, bo inaczej nie mógłbym ich brać pod uwagę (chyba). Wówczas dodanie 'z' sprawia, że dany ciąg nie spełnia warunków. Dodanie x,y sprawia, że jest ok.

Czy litery \(\displaystyle{ x, y}\) mogą się powtarzać?

W zadaniu nie pisze nic o tym, aby nie mogły.

[leg14]

Nie chcemy dodawać tylk oodejmować. SKoro nie możesz odjąć 1 z, to odejmij dwa.

[a4karo]

A jak to zapisać używając symboli?