Znajdź wzór rekurencyjny i go uzasadnij.

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
yaritoko
Witam na forum
Witam na forum
Posty: 3
Rejestracja: 13 sie 2022, 11:15

Znajdź wzór rekurencyjny i go uzasadnij.

Post autor: 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
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re: Znajdź wzór rekurencyjny i go uzasadnij.

Post autor: kerajs »

yaritoko pisze: 13 sie 2022, 11:17
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'' ?
yaritoko pisze: 13 sie 2022, 11:17 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
Witam na forum
Witam na forum
Posty: 3
Rejestracja: 13 sie 2022, 11:15

Re: Znajdź wzór rekurencyjny i go uzasadnij.

Post autor: yaritoko »

kerajs pisze: 13 sie 2022, 16:14 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
Witam na forum
Witam na forum
Posty: 3
Rejestracja: 13 sie 2022, 11:15

Re: Znajdź wzór rekurencyjny i go uzasadnij.

Post autor: yaritoko »

kerajs pisze: 13 sie 2022, 16:14 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
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re: Znajdź wzór rekurencyjny i go uzasadnij.

Post autor: 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ę.
ODPOWIEDZ