The number of ways to lay unit-length matchsticks on a $2 \times n$ grid (with respect to vertices) appears to be given by OEIS sequence A093129, but I found it a different way, and I'm looking for insight into how to move from one to the other.
In particular, it looks like $A093129(n) = a_1(n + 1) + a_5(n + 1)$ where
$$ \begin{align} a_1(n+1) &= a_1(n) + a_5(n)\\ a_2(n+1) &= a_1(n) + a_2(n) + 2a_5(n) + a_6(n) + a_7(n)\\ a_3(n+1) &= a_3(n) + a_5(n) + a_6(n)\\ a_4(n+1) &= a_4(n) + a_5(n) + a_6(n)\\ a_5(n+1) &= a_2(n) + a_5(n) + a_6(n) + a_7(n) \\ a_6(n+1) &= a_3(n) + a_5(n) + a_7(n)\\ a_7(n+1) &= a_4(n) + a_5(n) + a_6(n) \end{align} $$ with initial conditions $$ a_1(0) = a_2(0) = 1\\ a_3(0) = ... = a_7(0) = 0. $$
In particular, it appears that $$ \begin{align} a_1(n + 1) + a_5(n + 1) &= (a_1 + a_5)(n + 1) \\ &= A093129(n)\\ &= 5\cdot(A093129(n - 1) + A093129(n - 2))\\ &= 5\cdot((a_1 + a_5)(n) - (a_1 + a_5)(n - 1)). \end{align} $$
Questions
- How does one prove this recursion?
- Is there a general strategy for transforming such "systems of linear recurrences" to a single linear recurrence? (Can this even be done in general?)
An Idea
One thing that I try is to write this as $$ (a_1 + a_5)(n) = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}^T \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 2 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$ and do some linear algebra trickery to see if I can come up with some sort of closed form—but in this case, I'm really more interested in getting a recurrence.