Solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$?

Question

What is the simplest way to solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$, with the initial values $a_0=2,a_1=1$? Is it possible to do this with generating functions?

Answer 1

There're at least two four commonly used methods:

1. generating functions

2. looking for solutions in a particular form: $n^k\alpha^n$ with $k\in\mathbb N$ and $\alpha\in\Bbb R$.

3. Z-transform. Thank you, @Omnomnomnom.

4. The annihiliator method/characteristic equations (even though they are closely related to the second method). Thank you, @anorton.

The wikipedia article on recurrence relations can give you a couple of ideas.

Answer 2

solve the equation $$a_{n+2}=5a_{n+1}-9a_n$$ with the ansatz $$a_n=q^n$$ and look for a special solution of the equation $$a_{n+2}=5a_{n+1}-9a_n+3n$$