# Solve the recurrence relations

Recurrence Relation: $$a_n = 6a_{n-1} - 9a_{n-2}$$ Initial Conditions: $$a_1 = -1, a_2 = 1$$

The answer in the back of the book is $$(2n-1)3^{n-1}$$ But I don't see how they got there. When using the auxiliary equation method I keep getting $$r=3$$ and I am not sure how to progress from there.

• The auxiliary equation $\lambda^2 - 6\lambda+9 = (\lambda-3)^2$ has a double root at $\lambda = 3$. In general, if the auxillary equation for a homogeneous linear recurrence equation can be factorized as $\prod_{i=1}^m(\lambda - \lambda_i)^{\mu_i}$, then the general solution has the form $a_n = \sum_{i=1}^m P_i(n) \lambda_i^n$ where $P_i(n)$ is a polynomial of degree $\mu_i - 1$, i.e. the degree is one less than the multiplicity of $\lambda_i$. – achille hui Oct 4 '15 at 0:08

## 2 Answers

Since $r^2-6r+9=0\implies(r-3)^2=0\implies r=3$,

we have that $a_n=c(3^n)+d(n3^n)$ for some constants $c$ and $d$ since 3 is a double root.

Then $a_1=-1$ gives $3c+3d=-1,\;\;$ and $a_2=1$ gives $9c+18d=1$.

Then $c+d=-\frac{1}{3}$ and $c+2d=\frac{1}{9}$, so $d=\frac{4}{9}$ and $c=-\frac{7}{9}$.

Therefore $a_n=-\frac{7}{9}(3^n)+\frac{4}{9}(n3^n)=(4n-7)3^{n-2}$.

(The answer given in the book does not satisfy the initial conditions.)

• Thank you! I was wondering because I kept coming to something similar to yours and was going crazy. Glad to know I was on the right track. – D.Peterson Oct 4 '15 at 23:30

As user84413 answered, the answer given in the book is not correct.

The general solution being $$a_n=c_1 3^n+c_2 3^n n$$ we can compute the coefficients $c_1$ and $c_2$ from $a_1$ and $a_2$. This gives at the end $$a_n=3^{n-2} \Big( (6a_1-a_2)+(a_2-3a_1)n\Big)$$ So, to get the answer from the book, it would be required that $a_1=-1$ and $a_2=9$.