If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, then $ b, nb, n^2 , ... , n^{t-1}b $ are all solution of the recurrence relation.
I want to prove this, so I can denote the characteristic equation of this relation as $$ p(x) = x^k + c_1 x^{k-1} + c_2x^{k-2} + .... + c_k $$ Then p(x) = $ (x - b)^ t q(x) $, where q(x) is of degree k-t. I dont know how solve after this, should it be done like with induction as where we first prove that b is true, then show if $ n^ {t-1} b $ is a solution then $ n^t $ is a solution too where $ t \lt k $ or is there some other way to prove it.
A proof goes by using generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and take your recurrence with initial values $a_0$ through $a_{k - 1}$. Shift indices to get:
$\begin{align} a_{n + k} = c_1 a_{n + k - 1} + \dotsb + c_k a_n \end{align}$
Multiply by $z^n$, sum over $n \ge 0$ and get:
$\begin{align} \sum_{n \ge 0} a_{n + k} z^n = c_1 \sum_{n \ge 0} a_{n + k - 1} z^n + \dotsb + c_k \sum_{n \ge 0} a_n z^n \end{align}$
Recognize the sums here:
$\begin{align} \frac{A(z) - a_0 - a_1 z - \dotsb - a_{k - 1} z^{k - 1}}{z^k} = c_1 \frac{A(z) - a_0 - a_1 z - \dotsb - a_{k - 2} z^{k - 2}}{z^{k - 1}} + \dotsb + c_k A(z) \end{align}$
Solving this for $A(z)$ gives a rational function of the form:
$\begin{align} A(z) = \frac{P(z)}{1 - c_1 z - \dotsb - c_k z^k} \end{align}$
The polynomial $P(z)$ depends on the initial values, and is of degree less than $k$. It is known that such can be split into partial fractions. A zero $\rho$ of multiplicity $m$ of the denominator gives rise to terms:
$\begin{align} \frac{a_m}{(z - \rho)^m} + \dotsb + \frac{a_1}{z - \rho} \end{align}$
Now, by the generalized binomial theorem we know that if $r$ is a positive integer:
$\begin{align} (1 - \rho^{-1} z)^{-r} &= \sum_{n \ge 0} (-1)^n \binom{-r}{n} \rho^{-n} z^n \\ &= \sum_{n \ge 0} \binom{n + r - 1}{r - 1} \rho^{-n} z^n \end{align}$
The solution of the recurrence is the coefficient of $z^n$ in the sum of the coefficients in each term of the partial fraction expansion. As the binomial coefficient in this expansion is a polynomial of degree $r - 1$ in $n$, the sum of the terms for $\rho$ add up to a polynomial of degree $m - 1$ in $n$ by $\rho^{-n}$, whose coefficients depend on the initial values.