Фигура «маг» может ходить по полю на одну или на две клетки вправо. Попасть на
третью клетку маг может двумя способами: сделать один ход на две клетки или два хода по
одной клетке. Сколькими способами маг может попасть на крайнюю справа клетку?

Маг может это сделать 2*2*2=8 способами. Вот эти способы :
1+1+1+1+1+1=6
1+1+1+1+2=6
1+1+2+1+1=6
1+1+2+2=6
2+1+1+1+1=6
2+1+1+2=6
2+2+1 +1=6
2+2+2=6
То есть перемножаем 2 способа в 3 клетку на 2 способа в 5 клетку и на 2 способа в 7 клетку.
Ответ: 8 способов.
                                                                              

Помимо названного выше,существует универсальный алгоритм решения. С помощью методов динамического программирования(кот�орые напоминают и индукцию,и рекурсию) это делается так:
Выводятся базовые случаиС помощью формулы заполняется массивТак,в вашей задаче,F(1)=1;F(2n+1�)=2F(2n-1);а ответ:8.
Вот похожая задача