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

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

Use generating functions. To simplify later work, use the recurrence backwards to get $$a_0 = -5/9$$. Define $$A(z) = \sum_{n \ge 0} a_n z^n$$, shift the recurrence by 2, multiply by $$z^n$$ and sum over $$n \ge 0$$, recognize some sums:

\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= 6 \sum_{n \ge 0} a_{n + 1} z^n - 9 \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 6 \frac{A(z) - a_0}{z} - 9 A(z) \end{align*}

Solve for $$A(z)$$, as partial fractions:

\begin{align*} A(z) &= \frac{7 - 33 z}{9 - 54 z + 81 z^2} \\ &= \frac{4}{9 (1 - 3 z)^2} - \frac{11}{9 (1 - 3 z)} \end{align*}

Use the generalized binomial theorem:

\begin{align*} (1 - u)^{-m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} u^n \\ &= \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n \end{align*}

\begin{align*} a_n &= [z^n] A(z) \\ &= \frac{4}{9} \binom{n + 2 - 1}{2 - 1} \cdot 3^n - \frac{11}{9} \cdot 3^n \\ &= (4 n - 7) \cdot 3^{n - 2} \end{align*}