- Consider a linear recurrence of order $k$ with constant coefficients:
$$ a_n = \lambda_1a_{n-1}+\dots+\lambda_ka_{n-k} + f(n), n\ge k.$$
How do I show that all solutions $a_n$ of this linear recurrence can be written as $a_n = a_n ^{(h)} + a_n^{(p)}$, with $a_n ^{(h)}$ an arbitrary solution of the corresponding homogeneous linear recurrence, and $a_n ^{(p)}$ a particular solution of the given linear recurrence.
- Consider this homogeneous linear recurrence of order $2$: $a_n = \lambda_1 a_{n-1}+\lambda_2 a_{n-2}, \, n\ge 2$.
Suppose that the characteristic polynomial of this recurrence has one unique solution $r = \lambda_1 / 2$. This means that $a_n = (\frac{\lambda_1}{2})^n $ is a solution of the given linear recurrence. How do I prove that $nr^n$ is also a solution of the homogeneous linear recurrence?
Thanks!
Hint. Take two arbitrary solutions of your nonhomogeneous equation. What did you get as their difference? A solution of the homogeneous part of the equation. Now fix one particular solution of the nonhomogeneous equation and reverse the process.
We have one root $r$ of multiplicity 2 of the characteristic polynomial. That means $x^2-\lambda_1 x-\lambda_2 = (x-r)^2 = x^2-2r x+r^2$. As you already noted, $\lambda_1 = 2r$ and from above we also have $\lambda_2 = -r^2$. Using this, just plug $a_k = kr^k$ for $k=n,n-1,n-2$, into your equation and you get easily the result.