TAOCP 1.2.8 Exercise 39

Exercise 39. [M24] Find a closed form expression for $a_n$, given that $a_0=0$, $a_1=1$, and $a_{n+2}=a_{n+1}+6a_n$ for $n \ge 0$.

Verified: no
Solve time: -

Solution

The recurrence relation is

$$ a_{n+2}=a_{n+1}+6a_n, $$

with initial conditions

$$ a_0=0,\qquad a_1=1. $$

We solve this recurrence by the standard method used to derive Eq. (14). Assume a solution of the form

$$ a_n=r^n. $$

Substitution into the recurrence gives

$$ r^{n+2}=r^{n+1}+6r^n. $$

Since $r^n\ne0$, division by $r^n$ yields the characteristic equation

$$ r^2=r+6, $$

that is,

$$ r^2-r-6=0. $$

Factoring,

$$ (r-3)(r+2)=0. $$

Hence the two roots are

$$ r=3,\qquad r=-2. $$

Therefore the general solution has the form

$$ a_n=A3^n+B(-2)^n. $$

We determine $A$ and $B$ from the initial conditions. From $a_0=0$,

$$ A+B=0. $$

From $a_1=1$,

$$ 3A-2B=1. $$

Since $B=-A$, substitution gives

$$ 3A+2A=1, $$

hence

$$ A=\frac15,\qquad B=-\frac15. $$

Therefore

$$ a_n=\frac15\left(3^n-(-2)^n\right). $$

Thus the closed form expression is

$$ \boxed{a_n=\frac{3^n-(-2)^n}{5}}. $$