Matematyka.pl

Witajcie.

Mam oto takie dwa zadanka do których nie wiem wogóle jak podejść:

Zadanie 1. Niech \(\displaystyle{ \sum=\left\{ a,b\right\}}\), \(\displaystyle{ A_{n}}\) będzie zbiorem słów słownika \(\displaystyle{ \sum*}\)niezawierających kolejnych liter \(\displaystyle{ a}\), a \(\displaystyle{ s_{n}}\) - liczbą słów długości \(\displaystyle{ n}\), w których nie występują kolejno dwie litery \(\displaystyle{ a}\), tzn. nie zawierają ciągu \(\displaystyle{ aa}\). Wyznaczyć wzór rekurencyjny na \(\displaystyle{ s_{n}}\).

Zadanie 2. Niech \(\displaystyle{ \sum=\left\{ a,b,c \right\}}\), \(\displaystyle{ A_{n}}\) będzie zbiorem słów słownika \(\displaystyle{ \sum*}\) w których występuje parzysta liczba liter \(\displaystyle{ a}\), a \(\displaystyle{ s_{n}}\) - liczbą słów długości \(\displaystyle{ n}\), ze zbioru \(\displaystyle{ A_{n}}\). Wyznaczyć wzór rekurencyjny na \(\displaystyle{ s_{n}}\).

Jakieś wskazówki jak zacząć?

Do pierwszego mam rozwiązanie dość pokrętne, ale skuteczne. Każde takie słowo może się kończyć na \(\displaystyle{ a}\) albo na \(\displaystyle{ b}\). Czyli możemy sobie zdefiniować nowe ciągi \(\displaystyle{ a_n}\) i \(\displaystyle{ b_n}\), takie że \(\displaystyle{ a_n+b_n=s_n}\). Dla tych ciągów układamy równania rekurencyjne

\(\displaystyle{ a_n=b_{n-1},\quad\quad b_n=a_{n-1}+b_{n-1}}\).

Z nich można otrzymać równania

\(\displaystyle{ a_n=b_{n-1}=a_{n-2}+b_{n-2}=a_{n-2}+a_{n-1}}\),

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

które po dodaniu stronami dają równanie rekurencyjne na \(\displaystyle{ s_n}\).

Drugie zadanie jest dużo łatwiejsze. Jeśli \(\displaystyle{ s_n}\) jest liczbą słów długości \(\displaystyle{ n}\) o parzystej liczbie liter \(\displaystyle{ a}\), to liczba słów długości \(\displaystyle{ n}\) o nieparzystej liczbie liter \(\displaystyle{ a}\) jest równa \(\displaystyle{ 3^n-s_n}\).