Niech \(\displaystyle{ a_{n} }\) oznacza liczbę \(\displaystyle{ n}\)-literowych słów nad alfabetem \(\displaystyle{ 26}\)-literowym, takich że
łączna liczba wystapień liter \(\displaystyle{ A,E,I,O,U }\) jest parzysta. Ułóż zależność rekurencyjną dla ciągu \(\displaystyle{ a _{n} }\).
Układanie rekurencji
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Układanie rekurencji
Autorka pewnie już rozwiązała, skoro wczoraj widziała podpowiedź i nie miała pytań, więc zamieszczę rozwiązanie.
Narzuca się odpowiedź bez rekurencji :
\(\displaystyle{ a_n= \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} {n \choose 2i} 5^{2i}21^{n-2i} }\)
Podpowiedź A4karo sugeruje układ:
\(\displaystyle{ \begin{cases} a_n=21a_{n-1} +5b_{n-1} \\ b_{n} =5a_{n-1} +21b_{n-1} \end{cases} }\)
który można sprowadzić do równania:
\(\displaystyle{ a_{n+1}-42a_{n-1} +416a_{n-1} =0 }\)
które dla \(\displaystyle{ a_1=21 \wedge a_2=466}\) ma rozwiązanie:
\(\displaystyle{ a_n= \frac{1}{2}(16^n+26^n) }\)
Dodano po 22 godzinach 28 minutach 16 sekundach:
Errata:
Zamiast:
\(\displaystyle{ a_{n+1}-42a_{n} +416a_{n-1} =0 }\)
Narzuca się odpowiedź bez rekurencji :
\(\displaystyle{ a_n= \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} {n \choose 2i} 5^{2i}21^{n-2i} }\)
Podpowiedź A4karo sugeruje układ:
\(\displaystyle{ \begin{cases} a_n=21a_{n-1} +5b_{n-1} \\ b_{n} =5a_{n-1} +21b_{n-1} \end{cases} }\)
który można sprowadzić do równania:
\(\displaystyle{ a_{n+1}-42a_{n-1} +416a_{n-1} =0 }\)
które dla \(\displaystyle{ a_1=21 \wedge a_2=466}\) ma rozwiązanie:
\(\displaystyle{ a_n= \frac{1}{2}(16^n+26^n) }\)
Dodano po 22 godzinach 28 minutach 16 sekundach:
Errata:
Zamiast:
powinno być:
\(\displaystyle{ a_{n+1}-42a_{n} +416a_{n-1} =0 }\)