When playing around trying to answer a question, I discovered a curious recurrence and solution for the Fibonacci convolution
$$a_n=\sum_{i+j=n} f_i f_j$$
where $f_i$ is ith element the Fibonacci sequence, defined by $f_0=0, f_1=1, f_{n+1}=f_n+f_{n-1}$.
One can show that $a_n$ satisfies the recurrence relation $a_{n+1}+a_{n-1}=nf_n$ and will have solution $5a_n=(n-1)f_{n+1}+(n+1)f_{n-1}$. The symmetry here feels like it belies a deeper fact or principle, but I can't tell what.
So, are there general conditions under which we have
$$a_{n+1}+a_{n-1}=nb_n,\qquad ca_n=(n-1)b_{n+1}+(n+1)b_{n-1}$$
or was this just an interesting coincidence? I suspect that one can work out what the conditions should be for this to happen in terms of generating functions, but when I was trying, the equations were complicated looking and unenlightening.
Edited to add: The way I initially found the recurrence was by using the identity $f_{i+1}f_{j+1}+f_{i}f_{j}=f_{i+j+1}$. Then $$\begin{align}\sum_{\substack{i+j=n,\\i>0,j>0}} f_if_j&=\sum_{i+j=n,i>0,j>0} f_{n-1}-f_{i-1}f_{j-1} \\
&= \sum_{i=1}^{n-1} f_{n-1} + \sum_{\substack{(i-1)+(j-1)=n-2,\\i-1\geq 0, j-1 \geq 0}}f_{i-1}f_{j-1} \\
&= (n-1)f_{n-1} + \sum_{\substack{i+j=n-2,\\i\geq 0, j\geq 0}}f_{i}f_{j} \end{align}.$$
Then, the fact that $f_0=0$ and a simple reindexing yields $a_{n+1}+a_{n-1}=nf_n$.
Best Answer
Consider the system of two equations $$ \begin{cases} a_{n+1} + a_{n-1} = nb_n, \\ c a_n = (n-1) b_{n+1} + (n+1) b_{n-1} \end{cases} $$ We need to describe all pairs of sequences $(a_n, b_n)$ that satisfy the recurrence above.
Let $A(x)$ and $B(x)$ be OGFs of $a_n$ and $b_n$ and $\Delta = x \frac{\partial}{\partial x}$. Also assume that $a_0=b_0=0$, so that $\frac{A(x)}{x}$ and $\frac{B(x)}{x}$ are still meaningful expressions. Then, the first recurrence rewrites as $$ (x^{-1}+x)A(x) = \Delta B(x), $$ and the second recurrence rewrites as $$ cA(x) = (\Delta-1) x^{-1} B(x) + (\Delta+1) xB(x). $$
However, we should note that, unlike the previous recurrence, this one only works for $n > 0$ with Fibonacci numbers, which we can fix by subtracting a constant $t=b_1$ on the right hand side.
Getting rid of $A(x)$ in them, we arrive at $$ c\Delta B(x) = (x^{-1}+x) [(\Delta-1) x^{-1} B(x) + (\Delta+1) xB(x)-t] $$
Expanding $\Delta$ back, we get the differential equation $$ cxB'(x) = (x^{-1}+x) [B'(x) - 2x^{-1}B(x) +x^2 B'(x) +2xB(x)-t] $$ This simplifies into $$ cx^3B'(x) = x(1+x^2)^2 B'(x) + 2(x^4-1)B(x)-t(x+x^3) $$
As WolframAlpha suggest, the general solution to this is $$ \boxed{B(x) = \frac{tx(1-x^2)+k_1 x^2}{1-(c-2)x^2+x^4}} $$ In particular, for $c=5$, $t=1$ and $k_1=1$, we get $$ B(x) = \frac{x+x^2-x^3}{1-3x^2+x^4} = \frac{x}{1-x-x^2}. $$ We can also get a generic expression for $A(x)$: $$ \boxed{A(x) = \frac{x^2 \left( t (1+(c-6)x^2+x^4) + 2 k_1 x(1-x^2) \right)}{\left(1-(c-2) x^2 + x^4 \right)^2}} $$ The result generally looks less than satisfactory, because other than $c=5, t=1, k_1=1$ there doesn't seem to be any particularly interesting set of parameters. Note that there might be further solutions to the recurrences if we drop the $a_0=b_0=0$ constraint, but I don't think it's likely to find anything interesting there, while it also will entail new technical challenges to account for them.