Solve recurrence relation problem

Question

This is a recursion problem that I am stuck at. I need to use the characteristic equation.

Let $a_0, a_1, a_2, . . .$ be defined by $a_0 = 5, a_1 = 0$, and $a_{n+2} = a_{n+1} + 6a_n$ for $n \ge 0$.

Give a closed expression for '$a_n$'.

Thnx

Answer 1

$x^2 - x - 6 = 0 \to x = 3, -2$, and the general solution is: $a_n = A\cdot 3^n + B\cdot (-2)^n$. For $a_0 = 5 \to A + B = 5$, and $a_1 = 0 \to 3A - 2B = 0 \to 3A - 2(5-A) = 0 \to A = 2, B = 3 \to a_n = 2\cdot 3^n + 3\cdot (-2)^n$.

Answer 2

In terms of a generating function: Observe that we may use the recurrence relation to manipulate the formal power series $A(x):=\sum_{n=0}^\infty a_n x^n$ to give

\begin{align} A(x)&=5+\sum_{n=0}^\infty a_{n+2} x^{n+2}\\ &=5+x\sum_{n=0}^\infty a_{n+1}x^{n+1}+x^2\sum_{n=0}^\infty a_{n}x^{n}\\ &=5+x(A(x)-5)+6x^2 A(x).\\ \end{align}

From this we may in turn solve for $A(x)$ and expand in partial fractions as

$$A(x)=\frac{5-5x}{1-x-6x^2}=\frac{5-5x}{(1+2x)(1-3x)}=\frac{3}{1+2x}+\frac{2}{1-3x}.$$ This simple form is great, since we may expand each fraction as a geometric series; identifying coefficients of $x^n$ thus yields $\boxed{a_n=3(-2)^n+2(3)^n}$.

Answer 3

$$a_{n+2}=a_{n+1}+6a_n\\ a_{n+2}+2a_{n+1}=a_{n+1}+6a_n; \qquad \text{or}\qquad a_{n+2}-3a_{n+1}=-2a_{n+1}+6a_n$$

Put $u_n=a_n-a_{n-1}$

$$\begin{align} u_{n+2}&=3u_{n+1}; \qquad \text{or}\qquad &u_{n+2}&=-2u_{n+1}\\ u_n&=3u_{n-1} &u_n&=(-2)u_{n-1} \\ &=3^2u_{n-2} &&=(-2)^2u_{n-2}\\ &\vdots & &\vdots\\ &=3^{n-1}u_1 &&=(-2)^{n-1}u_1\\ \end{align}$$

Note that $u_1=a_1-a_0=0-5=-5$.

Hence

$$\begin{align} a_n-a_{n-1}&=-5\cdot 3^{n-1} &a_n-a_{n-1}&=-5(-2)^{n-1}\\ a_{n-1}-a_{n-2}&=-5\cdot 3^{n-2} &a_{n-1}-a_{n-2}&=-5(-2)^{n-2}\\ &\vdots &&\vdots \\ a_2-a_1&=-5\cdot 3^1 &a_2-a_1&=-5(-2)^2 \end{align}$$ Summing by telescoping and noting that $a_1=0$ gives

$$\begin{align} a_n&=-5\sum_{r=1}^{n-1}3^r\qquad &a_n&=-5\sum_{r=1}^{n-1}(-2)\\ &=-\frac56 (3^n-3) &&=-\frac56 [(-2)^n+2] \end{align}$$

Let $$a_n=-\frac56 \left[A(3^n-3)+B((-2)^n+2)\right]$$ Equating $a_0=5, a_2=30$ gives $A=-\dfrac{12}5, B=-\dfrac{18}5$.

Substituting $A$ and $B$ into $a_n$ and simplifying gives

$$a_n=2(3^n)+3(-2)^n\qquad \blacksquare$$