Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Question

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ .

---

My attempt:

$a_r=3-6a_{r-1}-9a_{r-2}$

I calculated manually, I get $a_{20}=-6465079410=-6.46\times10^9$, so $x=-6.46$

Can you explain in formal way, please?

Answer 1

Let $f(z)=\sum_{n=0}^\infty a_n z^n$. Multiplying both sides of the recurrence by $z^n$ and summing over $n$ yields $$\sum_{n=2}^\infty a_n z^n +6\sum_{n=2}^\infty a_{n-1}z^n +9\sum_{n=2}^\infty a_{n-2}z^n = 3\sum_{n=2}^\infty z^n, $$ or $$f(z)-(a_0+a_1z)+6z(f(z)-a_0) + 9z^2f(z)=\frac{3z^2}{1-z}. $$ Substituting $a_0$ and $a_1$ and isolating $f(z)$, we have $$f(z)(1+6z+9z^2) = \frac{3z^2}{1-z}+z, $$ and hence $$f(z) = \frac z{(1+3z)^2}+\frac{3z^2}{(1-z)(1+3z)^2}. $$ Partial fraction decomposition yields $$f(z) = \frac3{16}\left(\frac1{1-z}\right)-\frac5{48}\left(\frac1{1+3z}\right)-\frac1{12}\left(\frac1{(1+3z)^2}\right). $$ Manipulating the geometric series $$\sum_{n=0}^\infty z^n=\frac1{1-z} $$ we find that $$f(z) = \sum_{n=0}^\infty \frac3{16}z^n - \sum_{n=0}^\infty\frac5{48}(-3)^n z^n-\sum_{n=0}^\infty \frac1{12}(n+1)(-3)^nz^n.$$ Simplifying, we have $$f(z) = \sum_{n=0}^\infty\left(\frac3{16}-\frac5{48}(-1)^n3^{n}-\frac1{12}(n+1)(-1)^n3^{n} \right)z^n, $$ and so we conclude that $$a_n=\frac3{16}-\frac5{48}(-1)^n3^{n}-\frac1{12}(n+1)(-1)^n3^{n}. $$ In particular, $$a_{20} = \frac{3}{16}-\frac{5}{48} (-1)^{20} 3^{20}-\frac{21}{12} (-1)^{20} 3^{20}=-6465079410. $$

Answer 2

HINT:

Let $a_n=Ab_n+B$

$$Ab_n+B+6(Ab_{n-1}+B)+9(Ab_{n-2}+B)=3$$

$$A(b_n+6b_{n-1}+9b_{n-2})+B(1+6+9)-3=0$$

Set $B(1+6+9)-3=0\iff B=?$

and use this on $$b_n+6b_{n-1}+9b_{n-2}=0$$

Answer 3

To make your life easier, work with difference equations: write the rxpression for the previous term and subtract. You get rid of the annoying constant term and set $b_n =a_n -a_{n-1}$. Then use GF or characteristic equation.

Answer 4

If you work out the answer manually, you get $x=-6.46$. You could try the method of generating functions to obtain a formula.