Задача
Лягушка прыгает по вершинам треугольника ABC, перемещаясь каждый раз в одну из соседних вершин.
Сколькими способами она может попасть из A в A за n прыжков?
Решение
Пусть an – число способов вернуться за n прыжков в исходную вершину, а bn – попасть за n прыжков в соседнюю вершину. Легко видеть, что an+1 = 2bn, bn+1 = an + bn. Отсюда нетрудно вывести, что bn+2 = bn+1 + 2bn, an+2 = an+1 + 2an.
Из начальных условий a0 = 1, a1 = 0, получаем 
(это нетрудно доказать по индукции).
Ответ
способами.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет