0
$\begingroup$
  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!

$\endgroup$
0
$\begingroup$
  1. 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.

  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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.