В одной из вершин треугольника сидит лягушка. Она прыгает по вершинам треугольника, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами лягушка может попасть в начальную вершину за 9 прыжков?

1-м прыжком можно попасть в 2 различные вершины. 2-м тоже в две вершины и так до 8 прыжка включительно. Но 9-м прыжком мы можем очутиться только в одной вершине (т.к. в конце нужно попасть в начальную вершину).