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.
