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

По­лу­ча­ем ре­кур­рент­ную фор­му­лу для вы­чис­ле­ния S_n: и при Оче­вид­но, что это про­сто сме­щен­ная по­сле­до­ва­тель­ность Фи­бо­нач­чи Ито­го­вая ве­ро­ят­ность вы­чис­ля­ет­ся по фор­му­ле

Ответ: