Лягушка прыгает по вершинам шестиугольника ABCDEF, каждый раз перемещаясь в одну из соседних вершин.
а) Сколькими способами она может попасть из A в C за n прыжков?
б) Сколько таких способов при условии, что вершиной D пользоваться нельзя?
а) Ясно, что после четного числа прыжков, лягушка может находиться только в вершинах A, C или E. Обозначим через 
число путей длины 
ведущих из A в A, C и E соответственно. В силу симметрии 
Легко видеть, что выполняются равенства 
(можно за два шага перейти из A в C, или за два шага перейти из Е, или сходить С-B-C или С-D-C), 
(аналогично). Отсюда 
Из начальных условий 
По индукции легко показать, что 
б) Сохраним обозначение ck из пункта а). Обозначим через bk число путей длины 
ведущих из A в B. Тогда 
(за два прыжка можно двумя способами вернуться из B в B и одним способом попасть из B в F). Но 
значит, 
при 
По-прежнему, 
следовательно, 
Ответ: а) 
(n обязательно четное); б) 
(n обязательно четное).