Рекурренты в комбинаторике и числа Фибоначчи f(n)

Рассмотрим некоторый промежуточный шаг в движении Кузи. Если она на этом шаге находится в точке , то вероятность попасть в на следующем шаге равна нулю. Если же она находится в любой из оставшихся точек или ,то вероятность попасть в на следующем шаге равна , так как из каждой такой точки есть три равновозможных пути, только один из которых приводит в . Пусть — вероятность того, что на ом шаге блоха находится в точке . Соответственно не в точке она находится с вероятностью . Тогда на следующем шаге она окажется в с вероятностью

Таким образом, (так как изначально блоха в точке ),

Можно заметить закономерность и заключить при

Видим, что представляет собой сумму членов геометрической прогрессии со знаменателем равным Следовательно,

Замечание. Чтобы решение было более обоснованным, формулу для при можно доказать методом математической индукции.

База:

Шаг: пусть формула верна для , то есть

Тогда

то есть формула верна и для . А значит, верна и при любых