How to find a closed form expression for the following recurrence? Recently, I was dealing with the following recurrence, where $F_n$ is the $n$-th Fibonacci number:
$$
\displaylines{\begin{align}a(0) &= 0 \\\ a(1) &= 1 \\\ a(n) &= a(n-1) + a(n-2) + F_n + F_{n-2} \end{align}}
$$
By computing the first terms of it and searching the resulting sequence in OEIS, I found A045925, so:
$$
\displaylines{\begin{align}a(n) &= nF_n\end{align}}
$$
Now I want to go further and substitute $F_n$ with $nF_n$ and $F_{n-2}$ with $(n-2)F_{n-2}$:
$$
\displaylines{\begin{align}s(0) &= 0 \\\ s(1) &= 1 \\\ s(n) &= s(n-1) + s(n-2) + nF_n + (n-2)F_{n-2} \end{align}}
$$
I tried computing the first terms of that, but couldn't find any related sequences in OEIS:
$$
0,1,3,11,28,70,158,344,718,1459,...
$$
What steps should I take in order to find the closed form expression for that recurrence?
 A: You can certainly use generating functions. I would recommend going through generatingfunctionology, plus you can always check questions with [generating-functions] tag on this site as well.
Your sequence turns out to have generating function
$$
f(x)=\frac{x(x^2+1)^2}{(1-x-x^2)^3}=x+3x^2+11x^3+28x^4+70x^5+\dots
$$
From this you can also retrieve another recurrence, specifically
$$
s(n)=3s(n-1)-5s(n-3)+3s(n-5)+s(n-6)
$$
with initial values $0,1,3,11,28,70$.
The closed form can be expressed similarly as Binet's formula for Fibonacci numbers, either from the generating function or from the recurrence above. For example the characteristic polynomial is $f(x)=x^6-3x^5+5x^3-3x-1=(x^2-x-1)^3$ and the two roots $\varphi=\frac{1+\sqrt{5}}{2},\psi=\frac{1-\sqrt{5}}{2}$ of $x^2-x-1$ have multiplicity $3$ in the characteristic polynomial, so we expect
$$
s(n)=a_1\varphi^n+a_2n\varphi^n+a_3n^2\varphi^n+a_4\psi^n+a_5n\psi^n+a_6n^2\psi^n
$$
where the constants $(a_1,a_2,a_3,a_4,a_5,a_6)=(\frac{2\sqrt{5}}{25},\frac{1}{10},\frac{\sqrt{5}}{10},-\frac{2\sqrt{5}}{25},\frac{1}{10},-\frac{\sqrt{5}}{10})$ can be found from the initial values of the sequence.
However, based on your first example you seem to be fine with expression in terms of Fibonacci numbers. In that case notice that
$$
s(n)=\frac{1}{10}(5n^2+n+4)F_n+\frac{1}{5}nF_{n-1}.
$$
I don't know if there is more systematic way to found such relation, but I simply expected $s(n)$ in a form $$s(n)=(An^2+Bn+C)F_n+(Dn^2+En+F)F_{n-1}$$
and solved for constants $A,B,C,D,E,F$ provided enough values of $n$. You can prove it coresponds to your sequence by induction.
