Симметричную монету подбросили n раз. Найдите вероятность того, что не встретились два последовательных броска, в которых наблюдался орел?
Введем обозначения: О — орел, Р — решка. Пусть Sn — число последовательностей из О и Р длины n, в которых нет двух последовательных символов О (такие последовательности будем называть корректными). Очевидно, что и Найдем рекуррентную формулу для вычисления Sn при Рассмотрим всевозможные последовательности длины n оканчивающиеся на P. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последнего символа Р. Но таких последовательностей ровно Теперь рассмотрим все последовательности длины n оканчивающиеся на О. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последних двух символов Р и О (предпоследний символ
Получаем рекуррентную формулу для вычисления Sn:
Ответ: