В одной из вершин треугольника посиживает лягушка. Она скачет по верхушкам

Обозначим количество методов попасть назад в начальную верхушку за n прыжков как A(n), а количество методов попасть в одну из 2-ух иных вершин как B(n) (явно, количество методов идиентично для обеих вершин). Тогда:

A(n) = 2*B(n-1) находясь в одной из 2-ух не-исходных вершин после n-1 прыжка, лягушка скачет в исходную верхушку
B(n) = A(n-1) + B(n-1) лягушка скачет или из исходной, либо другой не-исходной

A(1) = 0
B(1) = 1

Дальше по формулам
 A    B - n
  0    1 - 1
  2    1 - 2
  2    3 - 3
  6    5 - 4
10  11 - 5
22  21 - 6
42  43 - 7
86  85 - 8
170 ---- 9

Ответ: 170