【bzoj4321】queue2 题目描述

n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行； 现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。 输入

只有一行且为用空格隔开的一个正整数 N，其中 100%的数据满足 1≤N ≤ 1000; 输出

一个非负整数，表示方案数对 7777777 取模。

样例输入 4

样例输出 2

如上，本题正解为DP $O(n^2)$，但oeis给出了递推式

$a_n=(n+1)a_{n-1}−(n−2)a_{n−2}−(n−5)a_{n−3}+(n−3)a_{n−4} $

自己太弱了理解不了，有大佬能给出递推式的证明吗