Znajdź wzór rekurencyjny i go uzasadnij.

[yaritoko]

Zacząłem powtarzać sobie zadania z Matematyki Dyskretnej i natknąłem się na taki problem.
Treść zadania brzmi:
''Rzucamy n-krotnie monetą i wynik zapisujemy jako ciąg n symboli O lub R. Serią orłów nazywamy wypadnięcie trzech orłów pod rząd. Niech \( a_{n} \) oznacza liczbę wyników n-krotnego rzutu, które nie zawierają serii orłów. Znajdź i uzasadnij wzór rekurencyjny dla ciągu \( {(a_{n})}_{n=0}^{ \infty }
\) "
Wydaje mi się, że dobrze rozwiązałem to zadanie, otrzymując:

1 dla n=0
2 dla n=1
4 dla n=2
\(
a_{n}= a_{n-1} + a_{n-2} + a_{n-3} \) dla n>3

Mam jednak problem, w jaki sposób udowodnić taki wzór? Prosiłbym o pomoc.

[kerajs]

Wydaje mi się, że dobrze rozwiązałem to zadanie, otrzymując:
1 dla n=0

A skąd wynika owe ''1 dla n=0'' ?

Mam jednak problem, w jaki sposób udowodnić taki wzór?

Uzasadnieniem jest sposób w jaki doszedłeś do (fakt, że prawidłowego) wyniku. A jak uzyskałeś ten wzór?

[yaritoko]

A jak uzyskałeś ten wzór?

Rozpisuję sobie w postaci drzewka wszystkie możliwości które spełniają treść zadania. Czyli zaczynam od tylko dwóch możliwości wylosowania monety - orła albo reszki. Jeżeli otrzymam orła, to wtedy nie interesuje mnie co będzie dalej (bo muszę uważać tylko na 3 orły z rzędu), więc otrzymuję \(a_{n-1}\) i na tym kończy się ta możliwość. Potem wracam do przypadku gdzie otrzymuję reszkę, wtedy następnym ruchem będzie znów reszka albo orzeł, po orle wpisuję \(a_{n-2}\) (no bo po nim może być wszystko), natomiast po reszce muszę wpisać znów orła, bo nie może nam się trafić trzecia reszka pod rząd, stąd \(a_{n-3}\). Zatem \(a_{n}=a_{n-1}+a_{n-2}+a_{n-3}\) Problemem jest tylko to, że nie jest to wystarczający dowód(a przynajmniej przez osobę która to sprawdza, bo mimo iż uważa, że jest to dobre rozwiązanie to jednak nie jest to żaden dowód na to, że wzór ten jest poprawny).

[yaritoko]

A skąd wynika owe ''1 dla n=0'' ?

Zapomniałem dopisać w poprzedniej odpowiedzi. Czy to nie jest tak, że podczas gdy nie rzucamy wcale monetą, to mamy wtedy tylko 1 możliwy wynik, czyli brak jakichkolwiek orłów czy reszek? Stąd wpisałem 1 dla n=0.

[kerajs]

Fajne, brak wyników to jeden możliwy wynik. Niestety nieprawdziwe.
Gdybym sprawdzał powyższe uzasadnienie, to uważałbym, że znasz tylko wynik i do niego dopasowujesz (niestety nieumiejętnie) rozwiązanie.
Bardziej prawdziwe:
Ciąg o n wyrazach dostaje się dopisując R (reszkę) do dowolnego z ciągów o n-1 wyrazach, lub dopisując RO (reszkę i orła) do dowolnego z ciągów o n-2 wyrazach, lub ROO (reszkę i dwa orły) do dowolnego z ciągów o n-3 wyrazach.
Stąd \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\) dla \(n \ge 4\) . Ponadto \(a_1=2 \ , \ a_2=4 \ , \ a_3=7 \)
Można też znaleźć rekurencje dla każdego z trzech ciągów -zakończonego reszką, jednym orłem lub dwoma orłami, i wskazać ich sumę.