# Solve the linear homogeneous recurrence relation with constant coefficients

$$9a_{n} = 6a_{n-1}-a_{n-2}, a_{0}=6, a_{1}=5$$

So

$$x^n = (6x^{n-1}-x^{n-2})\div9$$

thus

$$[x^2 = (6x-1)\div9] \equiv [x^2 - \frac{2}{3}x + \frac{1}{9} = 0], x=\frac{1}{3}$$

also

$$a_{2}=\frac{8}{3}, a_{3}=\frac{31}{27}$$

How do I plug in that x/root to solve for the given recurrence relation?

I tried

$$9a_{n} = 6(\frac{1}{3})^{n-1} - (\frac{1}{3})^{n-2}$$

which for n=1 gives 5... which is correct, for a_1 though, not 9a_1? So that's not right.

Since $a_n=c\left(\frac{1}{3}\right)^n+dn\left(\frac{1}{3}\right)^n$, $a_0=2\implies c=6$ and $a_1=5\implies d=9$, so

$\displaystyle a_n=\frac{6}{3^n}+\frac{9n}{3^n}=\frac{2+3n}{3^{n-1}}$

• thank you but what is this d. – user163831 Dec 3 '14 at 21:06
• c and d are arbitrary constants, and then we can use $a_0$ and $a_1$ to solve for them. – user84413 Dec 3 '14 at 21:07
• Since there is a repeated root, the general solution to the recurrence has the form $a_n=c(r^n)+dn(r^n)$ where c and d are constants and r is the repeated root. – user84413 Dec 3 '14 at 21:09
• awesome thanks. that's only for repeated root cases though? so like if there were 2 distinct roots i wouldn't follow this formula? – user163831 Dec 3 '14 at 21:11
• I am just canceling a common factor of 3 on the top and bottom after combining the two fractions. – user84413 Dec 3 '14 at 21:23

Here are the steps $$a_{0}=6$$ $$a_{1}=5$$ $$9a_{n} = 6a_{n-1}-a_{n-2}$$ Lets rewrite this recurrence as $$a_{n} = \frac69a_{n-1}-\frac19a_{n-2}$$ $$a_{n} = \frac23a_{n-1}-\frac1{3^2}a_{n-2}$$ Now let's multiply by $3^n$ $$3^0a_{0}=3^06=6$$ $$3^1a_{1}=3^15=15$$ $$3^na_{n} = 2\cdot 3^{n-1}a_{n-1}-3^{n-2}a_{n-2}$$ Let $S_n=3^na_n$, then $$S_0=6$$ $$S_{1}=15$$ $$S_n= 2S_{n-1}-S_{n-2}$$ It follows that $$S_n= S_1n-S_0(n-1)=9n+6=3(3n+2)$$ Therefore

$$a_n=\frac{3(3n+2)}{3^n}=3^{1-n}(3n+2)$$