I'm currently stonewalled on this problem, in which I have to solve the following recurrence relation and prove my answers satisfy the recurrence.
My boundary conditions are $a_0 = 1$ and $a_1 = 9$.
The problem is $\forall\ n \in N$, $a_{n+2}-18a_{n+1}+9a_{n}=0$
I ended up with the sequence proceeding as $1, 9, 153, 2673, 46737$ for $a_{0}, a_{1}, a_{2}, a_{3},$ and $a_{4}$ respectively but I can't actually figure out the pattern that would give me a solution. Help?
On
Many recurrences can be solved by Wilf's techniques from "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} - 18 \frac{A(z) - a_0}{z} + 9 A(z) = 0 $$ Solve for $A(z)$ and split into partial fractions: $$ A(z) = \frac{1}{2} \frac{1}{1 - (9 + 3 \cdot 2^{3/2}) z} + \frac{1}{2} \frac{1}{1 - (9 - 3 \cdot 2^{3/2}) z} $$ From here, recognizing two geometric series: $$ a_n = \frac{(9 + 3 \cdot 2^{3/2})^n + (9 - 3 \cdot 2^{3/2})^n}{2} $$
There is a standard procedure for dealing with such problems. One looks for solutions of the form $r^n$.
Substituting in the recurrence, we get, if I am reading the coefficients correctly, the equation $r^{n+2}-18r^{n+1}+9r^n=0$. On the assumption $r\ne 0$, we get $r^2-18r+9=0$, which has the solutions $$r=9\pm6\sqrt{2}.$$ Let $\alpha$ and $\beta$ be these solutions of the quadratic equation. It is easy to verify that for any constants $A$ and $B$, $A\alpha^n+B\beta^n$ is a solution of the recurrence.
From the initial conditions, you can calculate what $A$ and $B$ must be. (That part is left to you.)
So for the $A$ and $B$ that you found, if we put $a_n=A\alpha^n+B\beta^n$, the recurrence and initial conditions are satisfied. But it is easy to prove by induction that there is only one solution to the recurrence with initial conditions. So we must have found it.
Remark: The method described above can be used for all linear homogeneous recurrences with constant coefficients. There is a small complication when the equation we get has roots of multiplicity greater than $1$.