Matematyka dyskretna, zadanie nr 5478
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
mateusz3338 postów: 2 | 2017-06-02 20:10:15 Dla każdej liczby naturalnej n niech a_n oznacza liczbę ciągów ternarnych (tj. o wyrazach 0,1,2) długości n, w których każde dwa symbole niezerowe są rozdzielone przynajmniej jednym zerem. Znajdź rekurencję dla ciągu a_n. |
tumor postów: 8070 | 2017-06-09 09:36:12 $a_1=1+2=3$ (jeden ciąg kończy się 0, dwa ciągi liczbą różną od 0) Zauważmy teraz, że każdy ciąg z powyższych możemy przedłużyć liczbą 0, a tylko jeden ciąg liczbą różną od zera (na 2 sposoby), czyli $a_2=a_1*1+1*2$ Wobec tego teraz $a_1$ ciągów kończy się na 0 (i możemy je przedłużyć liczbą inną niż 0), a wszystkie ciągi możemy przedłużyć wyrazem 0 $a_3=2a_1+a_2$ ogólnie: rozpatrując ciągi o długości n+2 widzimy, że każdy ciąg o długości n+1 możemy przedłużyć zerem, natomiast tylko te ciągi możemy przedłużyć liczbą 1 lub 2, które były przedłużone zerem krok wcześniej. Stąd $a_{n+2}=a_{n+1}+2a_n$ dla n>0 |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj