# The sequence 0, 2, 8, 30, 112, 418,... is defined recursively by a_0 = 0, a_1 = 2, a_(n+1) = 4a_n-a_(n-1). What is the formula for a general term a_n?

Sep 16, 2016

${a}_{n} = \frac{{\left(2 + \sqrt{3}\right)}^{n} - {\left(2 - \sqrt{3}\right)}^{n}}{\sqrt{3}}$

#### Explanation:

$\textcolor{w h i t e}{}$
Proof by induction

Case $n = 0$

$\frac{{\left(2 + \sqrt{3}\right)}^{0} - {\left(2 - \sqrt{3}\right)}^{0}}{\sqrt{3}} = \frac{1 - 1}{\sqrt{3}} = 0 = {a}_{0}$

Case $n = 1$

$\frac{{\left(2 + \sqrt{3}\right)}^{1} - {\left(2 - \sqrt{3}\right)}^{1}}{\sqrt{3}} = \frac{2 \sqrt{3}}{\sqrt{3}} = 2 = {a}_{1}$

Induction step

Note that $\left(2 - \sqrt{3}\right) \left(2 + \sqrt{3}\right) = {2}^{2} - {\left(\sqrt{3}\right)}^{2} = 4 - 3 = 1$

So:

$\frac{{\left(2 + \sqrt{3}\right)}^{n + 1} - {\left(2 - \sqrt{3}\right)}^{n + 1}}{\sqrt{3}}$

$= \frac{\left(2 + \sqrt{3}\right) {\left(2 + \sqrt{3}\right)}^{n} - \left(2 - \sqrt{3}\right) {\left(2 - \sqrt{3}\right)}^{n}}{\sqrt{3}}$

$= \frac{4 \left({\left(2 + \sqrt{3}\right)}^{n} - {\left(2 - \sqrt{3}\right)}^{n}\right) - \left(\left(2 - \sqrt{3}\right) {\left(2 + \sqrt{3}\right)}^{n} - \left(2 + \sqrt{3}\right) {\left(2 - \sqrt{3}\right)}^{n}\right)}{\sqrt{3}}$

$= \frac{4 \left({\left(2 + \sqrt{3}\right)}^{n} - {\left(2 - \sqrt{3}\right)}^{n}\right)}{\sqrt{3}} - \frac{{\left(2 + \sqrt{3}\right)}^{n - 1} - {\left(2 - \sqrt{3}\right)}^{n - 1}}{\sqrt{3}}$

$= 4 {a}_{n} - {a}_{n - 1}$

$\textcolor{w h i t e}{}$
Bonus

$3 {a}_{n}^{2} + 4$ is always the square of an integer ...

Note that ${\left(2 + \sqrt{3}\right)}^{n} {\left(2 - \sqrt{3}\right)}^{n} = {1}^{n} = 1$

So:

$3 {a}_{n}^{2} + 4 = 3 {\left(\frac{{\left(2 + \sqrt{3}\right)}^{n} - {\left(2 - \sqrt{3}\right)}^{n}}{\sqrt{3}}\right)}^{2} + 4$

$\textcolor{w h i t e}{3 {a}_{n}^{2} + 4} = {\left({\left(2 + \sqrt{3}\right)}^{n} - {\left(2 - \sqrt{3}\right)}^{n}\right)}^{2} + 4$

$\textcolor{w h i t e}{3 {a}_{n}^{2} + 4} = {\left(2 + \sqrt{3}\right)}^{2 n} - 2 {\left(2 + \sqrt{3}\right)}^{n} {\left(2 - \sqrt{3}\right)}^{n} + {\left(2 - \sqrt{3}\right)}^{2 n} + 4$

$\textcolor{w h i t e}{3 {a}_{n}^{2} + 4} = {\left(2 + \sqrt{3}\right)}^{2 n} + 2 {\left(2 + \sqrt{3}\right)}^{n} {\left(2 - \sqrt{3}\right)}^{n} + {\left(2 - \sqrt{3}\right)}^{2 n}$

$\textcolor{w h i t e}{3 {a}_{n}^{2} + 4} = {\left({\left(2 + \sqrt{3}\right)}^{n} + {\left(2 - \sqrt{3}\right)}^{n}\right)}^{2}$

Note that ${\left(2 + \sqrt{3}\right)}^{n} + {\left(2 - \sqrt{3}\right)}^{n}$ must be an integer, since odd powers of $\sqrt{3}$ from the two binomial powers carry opposite signs.