Well to handle general linear recurrence relations you can use formal power series :
$$A:=\sum_{n=0}^{\infty}a_nX^n $$
Suppose you are given $a_0,...,a_{k-1}$ and you have the following recursive formula for $n\geq k$ :
$$a_n=-a_{n-1}...-a_{n-k} $$
Then you have :
$$A=a_0+a_1X+...a_{k-1}X^{k-1}+\sum_{n=k}^{\infty}a_nX^n$$
Now :
$$\sum_{n=k}^{\infty}a_nX^n=\sum_{n=k}^{\infty}(-a_{n-1}...-a_{n-k})X^n$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^k\sum_{n=k}^{\infty}a_{n-l}X^n$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l\sum_{n=k}^{\infty}a_{n-l}X^{n-l}$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l\sum_{n=k-l}^{\infty}a_{n}X^{n}$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l(A-a_0-...-a_{k-l-1}X^{k-l-1})$$
Finally :
$$A=a_0+a_1X+...a_{k-1}X^{k-1}-\sum_{l=1}^kX^l(A-a_0-...-a_{k-l-1}X^{k-l-1})$$
So you finally get that :
$$(\sum_{l=0}^kX^l)A=\sum_{l=0}^{k-1}(a_0+...+a_{k-l-1}X^{k-l-1}) $$
And using a little trick :
$$\frac{1-X^{k+1}}{1-X}A=\sum_{l=0}^{k-1}\frac{(k-l-1)(k-l)}{2}a_lX^{k-l-1}$$
$$\frac{1-X^{k+1}}{1-X}A=\sum_{l=0}^{k-1}\frac{l(l+1)}{2}a_{k-l}X^{l-1}$$
Then this express $A$ as a an element of $\mathbb{C}(X)$ to which you cann apply the decomposition into simple elements to get your answer. Notice that using the fact that roots of $X^{k+1}-1$ are of finite order, this shows that your sequence will always be periodic of period dividing $n$ (whatever might be your choice of $a_0$,...,$a_{k-1}$) which is some kind of result.
