哈密顿路个数

2019年徐州区域赛第二题的题目如下：输入正整数$n$和$k$，其中$n\leq10^6$，$k\leq3$，求满足$\forall1\leq i<n,|p_i-p_{i+1}|\leq k$的$p\in S_n$的个数。在OEIS上可知，只要$k$固定，这个个数关于$n$是常系数线性递推数列（当然，好像没给证明）。而OEIS上给了思考此问题的一个思路：

就是下方那句将此问题描述为一个由简单图构成的序列的哈密顿路数量构成的序列。
于是，我有一猜想：“以某种形式递推生成的简单图序列，其哈密顿路数量构成的数列会是常系数线性递推数列”。这里的“某种形式递推生成”我暂时不确定到底是什么，不过我当前有一个初步的猜想：
考虑正整数$a$以及$k$，以及$k+1$个二元关系：$P_0,...,P_k\subset\{1,...,a\}\times\{1,...,a\}$（其中$f_0$是对称关系），那么考虑如下方式生成的简单图构成的序列：对于$G_n$，其点由$(s,t),s\in\{1,...,n\},t\in\{1,...,a\}$组成，对于$1\leq s_1<s_2\leq n$，$(s_1,t_1)$和$(s_2,t_2)$之间有边当且仅当$s_2-s_1\leq k$且$P_{s_2-s_1}(t_1,t_2)$为真，而对于$t_1\neq t_2$的$(s,t_1)$和$(s,t_2)$，它们之间右边当且仅当$P_0(t_1,t_2)$为真。
那么我的猜想可以简述为：当$a,k,P_0,...,P_k$固定的时候，$G_n$的哈密顿路的数量关于$n$构成一常系数线性递推数列。
证明该命题，或给出反例并适当弱化该命题再给出证明。