Bulgarian National Mathematical Olympiad

We shall use the following assertion.

Lemma. Let $k\ge 2$ be a positive integer. Then the equation $2x^{2k}+1=y^2$ does not have solutions in positive integers.

Proof. Assume that $x,y$ and $k\ge 2$ are positive integers such that $2x^{2k}+1=y^2$ and $x$ is minimum possible. It is obvious that $x$ is even and $y$ is odd. Let us denote $x=2a$ and $y=2b+1$. Then $2^{2k-1}{a}^{2k}=b(b+1)$ and $(b,b+1)=1$. There are two possibilities: - if $b=x_1^{2k}$ and $b+1=2^{2k-1}{x}_2^{2k}$, $x_1,x_2\in \mathbb{N}$, $x_1{x}_2=a$, then $2^{2k-1}{x}_2^{2k}-x_1^{2k}=1$, which gives a contradiction modulo 4; - if $b=2^{2k-1}{x}_1^{2k}$ and $b+1=x_2^{2k}$, $x_1,x_2\in \mathbb{N}$, $x_1{x}_2=a$, then $x_2^{2k}-2^{2k-1}{x}_1^{2k}=1$, which leads to the equation $y_1^2=2^{2k-1}{x}_1^{2k}+1$, $y_1=x_2^k$, where

we notice that $x_1<x$. It is clear that the above argument of decreasing the degrees of 2 can be continued until we have degree at most 5. Therefore we reach the equation $y_0^2=8x_0^{2k}+1$, where $x_0<x$ and $y_0=y_2^k$, $y_2\in \mathbb{N}$. Clearly, $y_0$ is odd and we set $y_0=2c+1$. We obtain $c(c+1)=2x_0^{2k}$, where $(c,c+1)=1$. We have again two possibilities: - if $c=x_3^{2k}$ and $c+1=2x_4^{2k}$, $x_3,x_4\in \mathbb{N}$, $x_3{x}_4=x_0$, then $4x_4^{2k}=2c+2=y_2^k+1$, whence $(2x_4^k-1)(2x_4^k+1)=y_2^k$. This leads to $2x_4^k-1=y_3^k$, $2x_4^k+1=y_4^k$, $y_3,y_4\in \mathbb{N}$, $y_3{y}_4=y_2$, and finally $y_4^k-y_3^k=2$, which is impossible; - if $c=2x_3^{2k}$ and $c+1=x_4^{2k}$, $x_3,x_4\in \mathbb{N}$, $x_3{x}_4=x_0$, then $2x_3^{2k}+1=(x_4^k{)}^2$, which contradicts to the choice of $x$ as minimal. This completes the proof of the lemma.

The roots of the characteristic equation $t^2-6t+1=0$ of our sequence are $t_{1,2}=3\pm 2\sqrt{2}$. Therefore we find (using the conditions $a_1=2$ and $a_2=12$) $$a_n=\frac{(3+2\sqrt{2}{)}^n-(3-2\sqrt{2}{)}^n}{2\sqrt{2}}.$$ Denote $(3+2\sqrt{2}{)}^n={\alpha }_n+{\beta }_n\sqrt{2}$, ${\alpha }_n,{\beta }_n\in \mathbb{N}$. Then $(3-2\sqrt{2}{)}^n={\alpha }_n-{\beta }_n\sqrt{2}$, ${\alpha }_n={\beta }_n$ and ${\alpha }_n^2-2{\beta }_n^2=1$. Now, if $a_n$ is perfect power for some $n$, then the last two equalities give a contradiction with the lemma.