<s>[INST] Find the closed formula for the following recusive sequence. 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.
 [/INST] 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}.$$
</s>