Counting trails in a triangular grid A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$.

How many trails are there from $1$ to $N$ in this graph? A trail is allowed to visit a vertex more than once, but it cannot travel along the same edge twice.
I wrote a program to count the trails, and I obtained the following results for $1 \le N \le 17$.
$$1, 1, 2, 4, 9, 23, 62, 174, 497, 1433, 4150, 12044, 34989, 101695, 295642, 859566, 2499277$$
This sequence is not in the OEIS, but Superseeker reports that the sequence satisfies the fourth-order linear recurrence
$$2 a(N) + 3 a(N + 1) - a(N + 2) - 3 a(N + 3) + a(N + 4) = 0.$$
Question: Can anyone prove that this equation holds for all $N$?

Regard the same graph, but add an edge from $n-1$ to $n$ with weight $x$ (that is, a path passing through this edge contributes $x$ instead of 1).
The enumeration is clearly a linear polynomial in $x$, call it $a(n,x)=c_nx+d_n$ (and we are interested in $a(n,0)=d_n$).
By regarding the three possible edges for the last step, we find $a(1,x)=1$, $a(2,x)=1+x$ and
$$a(n,x)=a(n-2,1+2x)+a(n-1,x)+x\,a(n-1,1)$$
(If the last step passes through the ordinary edge from $n-1$ to $n$, you want a trail from 1 to $n-1$, but there is the ordinary edge from $n-2$ to $n-1$ and a parallel connection via $n$ that passes through the $x$ edge and is thus equivalent to a single edge of weight $x$, so we get $a(n-1,x)$.
If the last step passes through the $x$-weighted edge this gives a factor $x$, and you want a trail from $1$ to $n-1$ and now the parallel connection has weight 1 which gives $x\,a(n-1,1)$.
If the last step passes through the edge $n-2$ to $n$, then we search a trail to $n-2$ and now the parallel connection has the ordinary possibility $n-3$ to $n-2$ and two $x$-weighted possibilities $n-3$ to $n-1$ to $n$ to $n-1$ to $n-2$, in total this gives weight $2x+1$ and thus $a(n-2,2x+1)$.)
Now, plug in the linear polynomial and compare coefficients to get two linear recurrences for $c_n$ and $d_n$. 
\begin{align} 
c_n&=2c_{n-2}+2c_{n-1}+d_{n-1}\\
d_n&=c_{n-2}+d_{n-2}+d_{n-1}
\end{align}
Express $c_n$ with the second one, eliminate it from the first and you find the recurrence for $d_n$.
(Note that $c_n$ and $a(n,x)$ are solutions of the same recurrence.)
