How to solve this kind of recurrence relation in closed form? $F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$ How to solve this   recurrence relation in closed form? $$F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$$
I know how to solve recurrence relations for less than four calls by solving the characteristic polynomial. But are there other ways so that i don't have to solve the 4 degree characteristic polynomial to solve this recurrence relation?
 A: One of the ways of solving such recurrences is backward iteration. Fix the value of $n\ge 1$. Note that the solution will be a sum of product of quantities $a$, $b$, $c$ and $d$ followed by $F_\xi$ where $\xi=0,\cdots,3$. Note that each $a$ diminishes the time index $n$ by unity, each $b$ diminishes it by a two, each $c$ by three and finally each $d$ by a four. Let us denote the number of $b$'s , $c$'s and $d$'s in a sequence as $P$, $q$ and $r$ respectively and let the time index run backwards from the left to the right. Luckily the coefficients do not depend on the time index so all what we need to count the number of strictly ordered sequences of length $P+q+r-1$ (note that the last $d$ quantity in the sequence is replaced by $F_{\xi+1}$) bounded from the below by unity and from the above by $n-\xi-P-2 q-3 r-1$. Therefore we have:
\begin{equation}
F_{n+2} = \sum\limits_{r=0}^n \sum\limits_{q=0}^n \sum\limits_{P=0}^n 1_{n-\xi \ge 2P + 3 q+ 4 r}\frac{(P+q+r)!}{P! q! r!} \binom{n-\xi-P-2 q-3r-1}{P+q+r-1} a^{n-\xi-2 P-3 q-4 r} b^P c^q d^r \cdot F_{\xi+1}
\end{equation}
for $\xi=1$ only. In this way we have obtained one ''mode'',i.e. one solution. The other three linearly independent solutions can be obtained using similar reasoning except that certain boundary conditions have to be taken into account. We will complete this later on.
