TL;DR: How to prove in a manner that is general and elegant (and without generating functions, if possible) that if $\lambda$ is a root of multiplicity $r$ of the characteristic equation, then $n^{t}\lambda^n$ is a solution to the recurrence relation for every $0\le t<n$?
In more detail:
Given a linear recurrence relation with constant coefficients, $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\ldots+c_{k}a_{n-k}$, the well-known method for finding closed form solution is to consider the characteristic equation, $x^k=c_{1}x^{k-1}+c_{2}x^{k-2}+\ldots+c_{k}$, or equivalently the characteristic polyonmial $p(x)=x^k-c_{1}x^{k-1}-c_{2}x^{k-2}-\ldots-c_{k}$.
Given a root $p(\lambda)=0$, it is easy to prove that $a_n=\lambda^n$ is a solution to the recurrence relation, simply by substituting $\lambda$ in the characteristic equation and multiplying by $\lambda^{n-k}$.
If $p(x)$ has no multiple roots, this sufficies to find every possible solution to the recurrence relation since every solution is a linear combination of the solutions obtained in the above method. However, if $\lambda$ is a multiple root, we need to produce additional solutions.
It is claimed that if $\lambda$ is a root of multiplicity $r$ of $p(x)$ then $n^{t}\lambda^n$ is a solution to the recurrence relation for every $0\le t<n$. This is the claim I want to prove.
For the solution $a_n=n\cdot\lambda^n$ I did the following trick: since $\lambda$ has multiplicity at least 2, then $p(x)=(x-\lambda)q(x)$ where $q(\lambda)=0$. Then we obtain $p^\prime(x)=q(x)+(x-\lambda)q^\prime(x)$, so $p^\prime(\lambda)=0$ as well. This gives me the relation
$$k\lambda^{k-1}=\left(k-1\right)c_{1}\lambda^{k-2}+\left(k-2\right)c_{2}\lambda^{k-3}+\ldots+c_{k-1}$$
And with some algebraic manipulations with this and the original relation I get to
$$n\lambda^n=\left(n-1\right)c_{1}\lambda^{n-1}+\left(n-2\right)c_{2}\lambda^{n-2}+\ldots+\left(n-k\right)c_{k}$$
However, I feel there should be a better way to do this, one which extends more naturally for the higher orders of $t$.
I know that one way to handle this is using generating functions; I wish to avoid this, unless GF's are indeed the easiest way to go here (GF's are an extremely powerful tool, but for relatively simple combinatorics they are somewhat of an overkill, less suitable for educational purposes).
Best Answer
$\lambda$ is a root of multiplicity $r$ of $p(x)$ iff $p(\lambda) = p'(\lambda) = \ldots p^{(r-1)}(\lambda)=0$, which implies that $x^t p^{(r-t-1)}(x)$ has $\lambda$ as a root for $0 \le t \lt r$. Then, with the notation $\left(f(\lambda)\right)'$ for $f'(x) \big|_{x=\lambda}\,$:
$$ \begin{align} 0 = \lambda^{n-k}p(\lambda) &= \lambda^n-c_{1}\lambda^{n-1}-\ldots-c_{k}\lambda^{n-k} \\ 0 = \lambda \big(\lambda^{n-k}p(\lambda)\big)' &= n \lambda^n - (n-1)c_1\lambda^{n-1} - \ldots - (n-k)c_k\lambda^{n-k} \\ 0 = \lambda\Big(\lambda\big(\lambda^{n-k}p(\lambda)\big)'\Big)' &= n^2 \lambda^n- (n-1)^2c_1\lambda^{n-1} - \ldots - (n-k)^2c_k\lambda^{n-k} \\ \ldots &\qquad \end{align} $$