# Question on solutions of linear recurrences

1. 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.

1. 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!

2. 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.