, 2012

Let us compute the first few terms:

$a_1 = 1$

$a_2 = 5$

$a_3 = \frac{5^2 + 4}{1} = \frac{25 + 4}{1} = 29$

$a_4 = \frac{29^2 + 4}{5} = \frac{841 + 4}{5} = \frac{845}{5} = 169$

$a_5 = \frac{169^2 + 4}{29} = \frac{28561 + 4}{29} = \frac{28565}{29} = 985$

$a_6 = \frac{985^2 + 4}{169} = \frac{970225 + 4}{169} = \frac{970229}{169} = 5743$

$a_7 = \frac{5743^2 + 4}{985} = \frac{32984149 + 4}{985} = \frac{32984153}{985} = 33553$

We see that all terms are integers.

Let us try to find an explicit formula. Notice that the sequence seems to be related to powers of $5$ and $1$.

Let us try to guess a closed formula. Let us look for a pattern. Compute the ratios:

$a_2/a_1 = 5/1 = 5$
$a_3/a_2 = 29/5 = 5.8$
$a_4/a_3 = 169/29 \approx 5.827...$
$a_5/a_4 = 985/169 \approx 5.828...$
$a_6/a_5 = 5743/985 \approx 5.828...$
$a_7/a_6 = 33553/5743 \approx 5.843...$

This suggests that the sequence grows exponentially.

Let us try to solve the recurrence:

$a_n = \frac{a_{n-1}^2 + 4}{a_{n-2}}$

Multiply both sides by $a_{n-2}$:

$a_n a_{n-2} = a_{n-1}^2 + 4$

This is a second-order recurrence. Let us try to find a closed formula.

Let us try to write $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$:

$a_n a_{n-2} - a_{n-1}^2 = 4$

Or:

$a_n a_{n-2} - a_{n-1}^2 = 4$

This is similar to the recurrence for Chebyshev polynomials of the first kind, $T_n(x)$, which satisfy:

$T_n(x) = 2x T_{n-1}(x) - T_{n-2}(x)$

But our recurrence is different. Let us try to find a pattern.

Let us try to write $a_n$ as $k a_{n-1} - a_{n-2}$ for some $k$.

Alternatively, let us try to solve the recurrence by induction.

Let us try to prove by induction that all $a_n$ are integers.

Base cases: $a_1 = 1$, $a_2 = 5$ are integers.

Inductive step: Assume $a_{n-1}$ and $a_{n-2}$ are integers. Then $a_n = \frac{a_{n-1}^2 + 4}{a_{n-2}}$. We need to show that $a_{n-2}$ divides $a_{n-1}^2 + 4$.

But from the recurrence:

$a_{n-1} a_{n-3} = a_{n-2}^2 + 4$

So $a_{n-2}^2 + 4 = a_{n-1} a_{n-3}$

Therefore,

$a_{n-1}^2 + 4 = a_n a_{n-2}$

So $a_{n-2}$ divides $a_{n-1}^2 + 4$ because $a_n$ is defined as $\frac{a_{n-1}^2 + 4}{a_{n-2}}$.

Therefore, by induction, all $a_n$ are integers.

Now, let us try to find an explicit formula.

Let us try to solve the recurrence:

$a_n a_{n-2} - a_{n-1}^2 = 4$

Let us try to find a solution of the form $a_n = r^n + s r^{-n}$ for some $r$.

Suppose $a_n = \alpha \lambda^n + \beta \mu^n$.

Let us try to find $\lambda$ and $\mu$ such that the recurrence is satisfied.

Let us try $a_n = k a_{n-1} - a_{n-2}$.

Alternatively, let us try to find a pattern in the numbers:

$1, 5, 29, 169, 985, 5743, 33553, ...$

These are the sequence A001834 in OEIS, which is related to the solutions of Pell's equation $x^2 - 5y^2 = -4$.

In fact, the sequence satisfies $a_n^2 - 5 a_{n-1}^2 = 4 (-1)^n$.

Let us check:

$a_2^2 - 5 a_1^2 = 25 - 5 \cdot 1 = 20$
$a_3^2 - 5 a_2^2 = 841 - 5 \cdot 25 = 841 - 125 = 716$
$a_4^2 - 5 a_3^2 = 28561 - 5 \cdot 841 = 28561 - 4205 = 24356$

But this does not match $4 (-1)^n$.

Alternatively, let us try to find a closed formula.

Let us try to fit $a_n = \frac{(\alpha + \beta \sqrt{5})^n + (\alpha - \beta \sqrt{5})^n}{2}$ for some $\alpha, \beta$.

Let us try $a_n = \frac{(1 + 2 \sqrt{5})^n + (1 - 2 \sqrt{5})^n}{2}$.

Let us check for $n = 1$:

$a_1 = \frac{(1 + 2 \sqrt{5}) + (1 - 2 \sqrt{5})}{2} = \frac{2}{2} = 1$

For $n = 2$:

$(1 + 2 \sqrt{5})^2 = 1 + 4 \sqrt{5} + 4 \cdot 5 = 1 + 4 \sqrt{5} + 20 = 21 + 4 \sqrt{5}$
$(1 - 2 \sqrt{5})^2 = 1 - 4 \sqrt{5} + 20 = 21 - 4 \sqrt{5}$
Sum: $21 + 4 \sqrt{5} + 21 - 4 \sqrt{5} = 42$
$a_2 = \frac{42}{2} = 21$

But $a_2 = 5$ in our sequence.

So this does not match.

Alternatively, let us try to find a recurrence of the form $a_n = k a_{n-1} - a_{n-2}$.

Let us try to fit $a_n = 6 a_{n-1} - a_{n-2}$.

$a_3 = 6 \cdot 5 - 1 = 29$
$a_4 = 6 \cdot 29 - 5 = 169$
$a_5 = 6 \cdot 169 - 29 = 985$
$a_6 = 6 \cdot 985 - 169 = 5743$
$a_7 = 6 \cdot 5743 - 985 = 33553$

This matches the sequence!

Therefore, the sequence satisfies the linear recurrence:

$a_n = 6 a_{n-1} - a_{n-2}$, with $a_1 = 1$, $a_2 = 5$

The explicit formula for such a recurrence is:

Let the characteristic equation be $x^2 - 6x + 1 = 0$

The roots are $x = 3 \pm 2 \sqrt{2}$

So the general solution is:

$a_n = \alpha (3 + 2 \sqrt{2})^{n-1} + \beta (3 - 2 \sqrt{2})^{n-1}$

Let us solve for $\alpha$ and $\beta$ using $a_1 = 1$, $a_2 = 5$:

For $n = 1$:
$a_1 = \alpha (3 + 2 \sqrt{2})^0 + \beta (3 - 2 \sqrt{2})^0 = \alpha + \beta = 1$

For $n = 2$:
$a_2 = \alpha (3 + 2 \sqrt{2})^1 + \beta (3 - 2 \sqrt{2})^1 = \alpha (3 + 2 \sqrt{2}) + \beta (3 - 2 \sqrt{2}) = 5$

So:
$\alpha + \beta = 1$
$\alpha (3 + 2 \sqrt{2}) + \beta (3 - 2 \sqrt{2}) = 5$

Let us solve for $\alpha$ and $\beta$:

Let $S = 3 + 2 \sqrt{2}$, $T = 3 - 2 \sqrt{2}$

$\alpha S + \beta T = 5$
$\alpha + \beta = 1$

So $\beta = 1 - \alpha$

$\alpha S + (1 - \alpha) T = 5$
$\alpha S + T - \alpha T = 5$
$\alpha (S - T) + T = 5$

$S - T = (3 + 2 \sqrt{2}) - (3 - 2 \sqrt{2}) = 4 \sqrt{2}$

So:
$\alpha (4 \sqrt{2}) + T = 5$
$\alpha = \frac{5 - T}{4 \sqrt{2}}$

$T = 3 - 2 \sqrt{2}$

$5 - T = 5 - 3 + 2 \sqrt{2} = 2 + 2 \sqrt{2}$

So:
$\alpha = \frac{2 + 2 \sqrt{2}}{4 \sqrt{2}} = \frac{2(1 + \sqrt{2})}{4 \sqrt{2}} = \frac{1 + \sqrt{2}}{2 \sqrt{2}}$

$\beta = 1 - \alpha = 1 - \frac{1 + \sqrt{2}}{2 \sqrt{2}}$

Therefore, the explicit formula is:

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

Alternatively, since all terms are integers, the closed formula is:

$$a_n = 6 a_{n-1} - a_{n-2}, \quad a_1 = 1, \ a_2 = 5$$

Therefore, every term in the sequence is an integer, and the explicit formula is as above.