Question

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`?

Answer 1

`a_n =((2+sqrt(3))^n - (2-sqrt(3))^n)/sqrt(3)`

Explanation:

`color(white)()`
Proof by induction

Case `n=0`

`((2+sqrt(3))^0 - (2-sqrt(3))^0)/sqrt(3) = (1 - 1) / sqrt(3) = 0 = a_0`

Case `n=1`

`((2+sqrt(3))^1 - (2-sqrt(3))^1)/sqrt(3) = (2sqrt(3))/(sqrt(3)) = 2 = a_1`

Induction step

Note that `(2-sqrt(3))(2+sqrt(3)) = 2^2-(sqrt(3))^2 = 4-3 = 1`

So:

`((2+sqrt(3))^(n+1)-(2-sqrt(3))^(n+1))/sqrt(3)`

`=((2+sqrt(3))(2+sqrt(3))^n-(2-sqrt(3))(2-sqrt(3))^n)/sqrt(3)`

`=(4((2+sqrt(3))^n-(2-sqrt(3))^n)-((2-sqrt(3))(2+sqrt(3))^n-(2+sqrt(3))(2-sqrt(3))^n))/sqrt(3)`

`=(4((2+sqrt(3))^n-(2-sqrt(3))^n))/sqrt(3)-((2+sqrt(3))^(n-1)-(2-sqrt(3))^(n-1))/sqrt(3)`

`=4a_n-a_(n-1)`

`color(white)()`
Bonus

`3a_n^2+4` is always the square of an integer ...

Note that `(2+sqrt(3))^n(2-sqrt(3))^n = 1^n = 1`

So:

`3a_n^2+4 = 3(((2+sqrt(3))^n - (2-sqrt(3))^n)/sqrt(3))^2 + 4`

`color(white)(3a_n^2+4) = ((2+sqrt(3))^n - (2-sqrt(3))^n)^2 + 4`

`color(white)(3a_n^2+4) = (2+sqrt(3))^(2n) - 2(2+sqrt(3))^n(2-sqrt(3))^n+(2-sqrt(3))^(2n) + 4`

`color(white)(3a_n^2+4) = (2+sqrt(3))^(2n) + 2(2+sqrt(3))^n(2-sqrt(3))^n+(2-sqrt(3))^(2n)`

`color(white)(3a_n^2+4) = ((2+sqrt(3))^n + (2-sqrt(3))^n)^2`

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