I just got in touch with the method of solving recursions with generating functions. However, even if it is not mentioned anywhere, it seems to me, this approach is not applicable for recursions of order higher than 4.
So here comes my question: Is the method of generating functions applicable to linear recursions of order $k>4$?
Below follows a description of the problem and an explanation, why I think the answer is no, please tell me, if I am right, or have overlooked something.
Generating functions provide a textbook method for solving linear recurrences. If one considers the order-$k$ recurrence problem
$$a_{n+k}=c_0 a_n + c_1 a_{n+1}+...+c_{k-1}a_{n+k-1}$$ with given initial conditions $(a_0,...,a_{k-1})$, one defines the generating function
$$G(z):=\sum_{l=0}^\infty a_l z^l$$ of a complex, formal variable $z$.
For the general problem stated above, one finds that $G$ is of the rational form
$$G(z)=\frac{a_0+a_1z+...+a_{k-1}z^{k-1}}{1-c_0z^k-c_1z^{k-1}-...-c_{k-1}z}$$.
I will not go into details, as this is a standard method, but basically one has to insert the recursion into the above definition of $G(z)$, reformulate all terms via $G(z)$ by index changes and finally solve for $G(z)$.
Now the final step to get the closed form solution is to compute
$$a_n = \partial_z^n G(z)|_{z=0}$$
which is (to my opinion) only possible via franctional decomposition of the rational function $G$. However, this requires to write the denominator in product form, so in general, analytical derivations would be restricted to cases $k\leq 4$.