Рекуррентная последовательность и перестановки

[icu]

Нашел в oeis такую последовательность:
A038718
В шапке страницы можете увидеть любопытное утверждение. Каждый член последовательности - число перестановок $P$ набора $ 1,2,...,n $ такое, что $P_{1}=1$ и $|P_{i+1}-P_{i}|\leqslant2$ для $i=1,2,...,n-1$. Если непонятно, то $P$ - сама перестановка. Получается очень красивая рекурреннтная последовательность $a_{n} = a_{n-1} + a_{n-3} + 1$. Я попытался вывести эту формулу.
Идея была такая: пусть есть набор $ 1,2,...,n $, и какая-то его перестановка в рамках данных условий. Увеличим все числа в перестановке на 1 и слева допишем 1. Так мы получиим первые $a_{n}$ перестановок следующего набора $ 1,2,...,n, n+1 $. Далее заметим, что перестановки набора $ 1,2,...,n-2 $ тоже можно как-то дописывать и получим еще $ a_{n-2}$ перестановок набора $ 1,2,...,n, n+1 $. Ну и наконец догадываемся, что каждый новый набор генерит еще одну уникальную перестановку, которую первыми двумя способами из перестановок более мелких наборов получить нельзя.
Решение недоделанное и, вполне возможно, вообще не про то, что нужно. В правильном ли направлении я мыслю? Какие подходы использовали бы вы?

[DeBill]

icu в сообщении #1177660 писал(а):

Какие подходы использовали бы вы?

Я ж Вам писал в Вашей предыдущей теме: была указана ссылка на тему, в которой эта задача решалась для $n=41$, и было показано, как сводится к 40 и 38....

[whitefox]

icu в сообщении #1177660 писал(а):

Получается очень красивая рекурреннтная последовательность $a_{n} = a_{n-1} + a_{n-3} + 1$

Уже было, причём недавно. Решение.

-- 17 дек 2016, 11:06 --

Пардон, Вы не про решение рекуррентности, а про её вывод.

Тоже было, и тоже не так давно.