Spanija 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 \mathrm{5.827...}$ $a_5/a_4=985/169\approx \mathrm{5.828...}$ $a_6/a_5=5743/985\approx \mathrm{5.828...}$ $a_7/a_6=33553/5743\approx \mathrm{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-5a_{n-1}^2=4(-1{)}^n$.

Let us check:

$a_2^2-5a_1^2=25-5\cdot 1=20$ $a_3^2-5a_2^2=841-5\cdot 25=841-125=716$ $a_4^2-5a_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=6a_{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=6a_{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=6a_{n-1}-a_{n-2},a_1=1,a_2=5$$

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