I was studying the sequence A249665, which I will call $a_n$, and came up with a second sequence $b_n$ for which I could prove that the following recurrence holds.
\begin{align}
a_n&=a_{n-1}+a_{n-4}+a_{n-5}+b_{n-2}+b_{n-3}
\\b_n&=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+b_{n-2}+b_{n-3}+b_{n-4}
\end{align}
Here are some initial values.
\begin{align}
(a_0,…)&=(0,1,1,1,2,6,14,28,56,118,254,541,1140,…)
\\(b_0,…)&=(0,0,1,2,4,8,17,37,79,166,349,738,1563,…)
\end{align}
On the OEIS they give a linear recurrence in three sequence, so when I saw that I felt good about myself for finding one in only two sequences. However a bit further on, they give a recurrence in $a_n$ only, which caught me by surprise.
$$a_n=2a_{n-1}-a_{n-2}+2a_{n-3}+a_{n-4}+a_{n-5}-a_{n-7}-a_{n-8}$$
The companion matrix of this recurrence has the same dimension as the one for my recurrence, which leads me to believe there should be some method to find this recurrence out of mine.
So is there a general method to combine two simultaneous linear recurrences into one? Or can you at least find a way to deduce the one from OEIS from the simultaneous one I found?
Best Answer
I think I figured it out. At least for this specific case. I think the idea applies pretty generally, but can become much more complicated. This case is just a bit of algebraic manipulation.
Note that from the first recurrence formula we get $b_n+b_{n-1}=a_{n+2}-a_{n+1}-a_{n-2}-a_{n-3}$. We find \begin{align} a_n &=a_{n-1}+a_{n-4}+a_{n-5}+b_{n-2}+b_{n-3} \\&=a_{n-1}+a_{n-4}+a_{n-5}+b_{n-3} \\&+(a_{n-3}+a_{n-4}+a_{n-5}+a_{n-6}+b_{n-4}+b_{n-5}+b_{n-6}) \\&=a_{n-1}+a_{n-3}+2a_{n-4}+2a_{n-5}+a_{n-6} \\&+(b_{n-3}+b_{n-4})+(b_{n-5}+b_{n-6}) \\&=a_{n-1}+a_{n-3}+2a_{n-4}+2a_{n-5}+a_{n-6} \\&+(a_{n-1}-a_{n-2}-a_{n-5}-a_{n-6})+(a_{n-3}-a_{n-4}-a_{n-7}-a_{n-8}) \\&=2a_{n-1}-a_{n-2}+2a_{n-3}+a_{n-4}+a_{n-5}-a_{n-7}-a_{n-8}. \end{align}
To get an idea of the general approach, consider the problem of finding a recurrence for $b_n$. By applying the first recurrence formula on every $a$ term in the second, we obtain \begin{align} b_n &=b_{n-2}+b_{n-3}+b_{n-4} \\&+(a_{n-2}+a_{n-5}+a_{n-6}+b_{n-3}+b_{n-4}) \\&+(a_{n-3}+a_{n-6}+a_{n-7}+b_{n-4}+b_{n-5}) \\&+(a_{n-4}+a_{n-7}+a_{n-8}+b_{n-5}+b_{n-6}) \\&+(a_{n-5}+a_{n-8}+a_{n-9}+b_{n-6}+b_{n-7}). \end{align} By the second recurrence formula we get $a_n+a_{n-1}+a_{n-2}+a_{n-3}=b_{n+1}-b_{n-1}-b_{n-2}-b_{n-3}$, giving \begin{align} b_n &=b_{n-2}+2b_{n-3}+3b_{n-4}+2b_{n-5}+2b_{n-6}+b_{n-7} \\&+(b_{n-1}-b_{n-3}-b_{n-4}-b_{n-5}) \\&+(b_{n-4}-b_{n-6}-b_{n-7}-b_{n-8}) \\&+(b_{n-5}-b_{n-7}-b_{n-8}-b_{n-9}) \\&=b_{n-1}+b_{n-2}+b_{n-3}+3b_{n-4}+2b_{n-5}+b_{n-6}-b_{n-7}-2b_{n-8}-b_{n-9}. \end{align}
If you want to practice this youself, I advise to try and come up with a recurrence formula for the partial sums of fibonacci numbers, so give a recurrence formula for $s_n$ when $f_n=f_{n-1}+f_{n-2}$ and $s_n=s_{n-1}+f_n$.