Find the closed formula for the following recusive sequence.

Question

Find the closed formula for the recursive sequence defined by $a_0 = 4$, $a_1 = 12$, $a_n = 6a_{n-1}-a_{n-2}$ for $n>1$. This question is stumping me. I don't know any methods besides guess and check.

Current progress:

The first five terms are $4, 12, 68, 396, 2308$.

Each term is divisible by four, yielding $1, 3, 17, 99, 577$

Each of these is off of a perfect square by one or negative one $0-1, 4-3, 16-17, 100-99, 576-577$ = $-1,1,-1,1,-1$

Other than that I'm lost. Any help would be appreciated.

Answer 1

The characteristic equation is $x^2-6x+1$ with roots $3\pm\sqrt8$. Thus all sequences satisfying the given second-order recurrence have closed form $A(3+\sqrt8)^n+B(3-\sqrt8)^n$, with the initial conditions giving $A$ and $B$: $$A+B=4,A(3+\sqrt8)+B(3-\sqrt8)=12\implies A=B=2$$ Thus $a_n=2(3+\sqrt8)^n+2(3-\sqrt8)^n$.

Answer 2

Using the following fact, $$\begin{cases}a_{n}=ba_{n-1}+ca_{n-2},\\a_{0}=c,\quad a_{1}=d \end{cases}$$ then $$\begin{cases} a_{n}=\alpha r_{1}^{2}+\beta r_{2}^{2}, \quad \text{if} \quad r_{1}\not=r_{2},\quad r^{2}-br-c=0,\\a_{n}=br_{1}^{n}+dnr_{2}^{n},\quad \text{if}\quad r_{1}=r_{2},\quad r^{2}-br-c=0,\end{cases}$$ where $\alpha$ and $\beta$ can be found using the initial condition $a_{0}=c$ and $a_{1}=d$ by substitution in $a_{n}$.

Then, we have the recursive sequence with initial condition, $$\begin{cases}a_{n}=6a_{n-1}+(-1)\cdot a_{n-2},\\a_{0}=4,\quad a_{1}=12\end{cases}$$ Since $$r^{2}-6r-(-1)=0,\quad \text{then}\quad r=\frac{6\pm \sqrt{6^{2}-4}}{2},\quad \text{then}\quad r=3\pm \sqrt{8}, \quad \text{then}\quad r_{1}\not=r_{2}. $$

Then, the general solution is given by $$a_{n}=\alpha\left(3+\sqrt{8}\right)^{n}+\beta\left(3-\sqrt{8}\right)^{n}.$$ Setting $a_{0}=4$ and $a_{1}=12$ we have $$\begin{cases}4=\alpha\left(3+\sqrt{8}\right)^{0}+\beta\left(3-\sqrt{8}\right)^{0},\quad n=0,\\ 12=\alpha\left(3+\sqrt{8}\right)^{1}+\beta\left(3-\sqrt{8}\right)^{1},\quad n=1.\end{cases},\quad \text{then}\quad \begin{cases}\alpha=2,\\ \beta=2.\end{cases}$$ Therefore, the particular solution for the recursive sequence is given by $$\color{blue}{\boxed{a_{n}=2\left(3+\sqrt{8}\right)^{n}+2\left(3-\sqrt{8}\right)^{n},\quad n=0,1,\ldots}}$$

Answer 3

Solution by generating function:

The difference equation can be seen in the form $$ a_{n+2} = 6 \, a_{n+1} - a_{n} \, \hspace{10mm} a_{0} = 4, a_{1} = 12$$ leads to \begin{align} \sum_{n=0}^{\infty} a_{n+2} \, t^{n+2} &= 6 \, t \, \sum_{n=0}^{\infty} a_{n+1} \, t^{n+1} - t^2 \, \sum_{n=0}^{\infty} a_{n} \, t^n \\ \sum_{n=2}^{\infty} a_{n} \, t^{n} &= 6 \, t \, \sum_{n=1}^{\infty} a_{n} \, t^n - t^2 \, \sum_{n=0}^{\infty} a_{n} \, t^n \\ A - 4 - 12 \, t &= 6 \, t \, (A- 4) - t^2 \, A \\ A = \sum_{n=0}^{\infty} a_{n} \, t^n &= \frac{4 \, (1 - 3 \, t)}{1 - 6 \, t + t^2}. \end{align}

This can be compared to the Chebyshev polynomials of the first kind to obtain $$ a_{n} = 4 \, T_{n}(3). $$

Further properties can be obtained by using these polynomials and formulas such as: \begin{align} \sum_{n=0}^{\infty} T_{n}(x) \, t^n &= \frac{1 - x t}{1 - 2 x t + t^2} \\ T_{n}(x) &= \frac{1}{2} \, \left( \left(x + \sqrt{x^2 -1}\right)^n + \left(x - \sqrt{x^2 -1} \right)^n \right) \\ T_{n}(x) &= \sum_{k=0}^{\lfloor{n/2\rfloor}} \binom{n}{2 k} \, (x^2 - 1)^k \, x^{n-2 k}. \end{align} Properties and relations for $T_{n}(3)$ can be found in Oeis A001541.

By using $$ a_{n} = 4 \, T_{n}(3) = 2 \left( (3 + 2 \, \sqrt{2})^n + (3 - 2 \, \sqrt{2})^n \right) = 2 \, \left( (1+\sqrt{2})^{2 n} + (1 - \sqrt{2})^{2 n} \right) $$ then this last part can be compared to the Pell-Lucas numbers, $(Q_{n})$, see for some properties and relations Oeis A002203, and gives $$a_{n} = 2 \, Q_{2 n}.$$