Solving a third-order homogeneous recurrence relation with variable coefficients I'm working on a problem that I've managed to reduce to a third-order homogeneous recurrence relation given by the following expression:
$$(n + 3) f_{n + 3} - 2(n + 2) f_{n + 2} + (n - 1) f_{n + 1} + 2 f_n = 0$$
From here I want to try to find an expression for $f_n$ only in terms of $n$, but I'm hopelessly stuck. All resources that I've been able to find discuss solving recurrence relations that have constant coefficients, or the coefficients are variable but the same as the order, i.e. $(n + 1)f_{n + 1} + n f_n = 0$. 
I'm unaware if this expression even has a closed-form solution, so I could be grasping at straws here. Any help that could either walk me through how you approach these sorts of problems or point me towards resources that discuss them would be much appreciated.
 A: Yes, there is a closed-form solution to your recurrence relation. Methods to obtain this are in most texts on generating functions. (My particular favorite is Wilf's generatingfunctionology; see section 2.2 The Calculus of Formal Ordinary Power Series Generating Functions.) As a brief summary of the method, the main idea is to convert the recurrence relation about the $f_n$'s to an analogous relation about the generating function $F(x)=\sum_{n\ge0}f_nx^n$. In your recurrence relation, there are two main conversions. The first is a shift of indices, as in $f_{n+3}$. Here the generating function of the sequence $\langle f_{n+3}:n\ge0\rangle$ is $\frac{F(x)-f_0-f_1x-f_2x^2}{x^3}$. The second conversion involves multiplication by a non-constant coefficient, as in $n+3$. Here if $A(x)$ is the generating function of a sequence $\langle a_n:n\ge0\rangle$, then $xD[A(x)]$ is the generating function of the sequence $\langle n\cdot a_n:n\ge0\rangle$, where $D$ stands for the derivative. Therefore, your recurrence relation is equivalent to the following differential equation about the generating function $F(x)$:
\begin{align*}(xD+3)\frac{F(x)-f_0-f_1x-f_2x^2}{x^3}&-2(xD+2)\frac{F(x)-f_0-f_1x}{x^2}\\
+&(xD-1)\frac{F(x)-f_0}{x}
+2F(x)=0.
\end{align*}
This relation turns out to be a first-order differential equation for the generating function $F(x)$, where the coefficients of $F(x)$ and $F'(x)$ are rational functions of $x$. The exact solution depends on the initial conditions $f_0, f_1, f_2$ of the recurrence relation (which you did not state), but in general the differential equation can be solved with standard methods from a calculus or differential equations class. Once you get this generating function $F(x)$, hopefully it will be straightforward to extract its coefficients, thereby producing an exact solution to the recurrence relation.
A: Let us simplify the given equation in the following way:
\begin{align*}
(n+3)f_{n+3}−2(n+2)f_{n+2}+(n−1)f_{n+1}+2f_n&=0\\
(n+3)f_{n+3}−2(n+2)f_{n+2}+(n+1)f_{n+1}&=2f_{n+1}-2f_n\\
\Delta^2(nf_n)&=\Delta(2f_n)\\
\Delta(nf_n)&=2f_n+K
\end{align*}
where $\Delta$ is the forward difference operator and $K$ is a real constant. Then we have that
\begin{align*}
(n+1)f_{n+1}-nf_n&=2f_n+K\\
(n+1)f_{n+1}&=(n+2)f_n+K.
\end{align*}
It is not hard to show that the solution of the last equation is 
$$
\boldsymbol{f_n=C\cdot(n+1)-K},\qquad C,K\in\mathbb R
$$
A: Hint:
$\because$ sum of the coefficients of the recurrence relation is $0$
$\therefore$ The recurrence relation should have one group of linearly independent solutions that $f_n=\Theta(n)$ , where $\Theta(n)$ is an arbitrary periodic function with unit period.
