Chebyshev party!!! The following solution will assume well-known properties of the Chebyshev Polynomials, e.g. that they satisfy trig addition/subtraction formulas, etc. Let $B_k(x)$ denote the unique polynomial so that $B_k(\cos x) = \cos (kx).$ These are known as the Chebyshev Polynomials of the First Kind , and are given by $B_1 = x, B_2 = 2x^2 - 1, B_3 = 4x^2 - 1,$ and $B_{n+1} = 2x B_n - B_{n-1}$ for $n \ge 2.$ Let $A_k(x)$ denote the unique polynomial so that $A_k(\cos x) = \frac{\sin(kx)}{\sin x}.$ These are known as the Chebyshev Polynomials of the Second Kind . We have that $A_1 = 1, A_2 = 2x, A_3 = 4x^2 - 1, A_4 = 8x^3 - 4x$, and in general the $A_i$'s are given by the recurrence $A_{n+1} = 2x A_n - A_{n-1}$ for $n \ge 2.$ Lemma 1. There are integer polynomials $A, B \in \mathbb{Z}[x]$ so that $A \cdot B_k(x) + B \cdot A_k(x) = 1.$ Proof. Indeed, just take $A = A_{k+1}(x)$ and $B = -B_{k+1}(x).$ We have that $A_{k+1} B_k - B_{k+1} A_k = 1$ by the sine subtraction formula. $\blacksquare$ With this preliminary result, we are ready to turn to the problem. Let's start by tying the sequence in the problem to the Chebyshev polynomials. Lemma 2. $a_n = 2 A_n(3).$ Proof. It's very easy to show this by induction on $n$. $\blacksquare$ Suppose, for contradiction, that $a_n$ was a perfect power for $n \in \mathbb{N}.$ Observe that $a_n \equiv 2$ (mod $4$) if $n$ is odd, so hence we have that $n$ is even. Therefore, we have that $$a_n = 2A_n(3) = 4A_{\frac{n}{2}}(3) B_{\frac{n}{2}}(3),$$using the double angle formula for sine. As $B_{\frac{n}{2}} (3)$ is odd, Lemma 1 gives us that $4A_{\frac{n}{2}}(3)$ and $B_{\frac{n}{2}}(3)$ are relatively prime. Hence, as they multiply to a perfect power, $B_{\frac{n}{2}}(3)$ is a perfect power itself. However, the following lemma gives us the desired contradiction. Lemma 3. $B_{n} (3)$ is never a perfect power. Proof. Observe that the sequence $x_n = B_n(3)$ is given by $x_1 = 1, x_2 = 3,$ and $x_{n+1} = 6x_n - x_{n-1}$ for $n \ge 2.$ it's easy to obtain the general formula for $x_n$, which is given by $$x_n = \frac{(3+2\sqrt2)^{n-1} + (3-2\sqrt2)^{n-1}}{2}.$$If $n$ is odd, then if we let $n = 2k+1$ we have $$x_n -1 = \frac{(3+2\sqrt2)^{n-1} + (3-2\sqrt2)^{n-1}-2}{2} = \frac{((1+\sqrt2)^{2k} - (1-\sqrt2)^{2k})^2}{2}.$$However, observe that $(1+\sqrt2)^{2k} - (1-\sqrt2)^{2k}$ is of the form $b \sqrt 2$ for some $b \in \mathbb{N}$, and so hence we have that $x_n - 1 = b^2$ is a perfect square. Hence, by Mihailescu's Theorem , we have that $x_n$ is not a perfect power, since the only perfect powers which are adjacent to each other are $8$ and $9$, and $x_n \neq 9.$ If $n$ is even, then we have that $$x_n + 1 = \frac{(3+2\sqrt2)^{n-1} + (3-2 \sqrt2)^{n-1} + 2}{2} = \frac{((1+\sqrt2)^{n-1} + (\sqrt2-1)^{n-1})^2}{2}$$Since $n-1$ is odd, we have that $(1+\sqrt 2)^{n-1} + (\sqrt2 - 1)^{n-1}$ is of the form $b \sqrt2$ for some $b \in \mathbb{N}$. Therefore, we have that $x_n + 1 = b^2$ is a perfect square. Hence, by Mihailescu's Theorem again, we have that $x_n$ is not a perfect power, since the only adjacent perfect powers are $8$ and $9$, and $x_n \neq 8.$ In conclusion, we've shown that $x_n = B_n(3)$ is never a perfect power. $\blacksquare$ With Lemma 3, we obtain the desired contradiction, and so our initial assumption that there existed an $a_n$ that was a perfect power was incorrect, as desired. $\square$

I strongly believe that there is a solution without using Mihailescu's Theorem and that would be more apt. But nice solution _Pathological_

Pathological wrote: Lemma 2. $a_n = 2 A_n(3).$ Proof. It's very easy to show this by induction on $n$. Check it, it's not right! I'd rather get $a_n$ term explicitly using the characteristic equation of the sequence. EDIT: Oh, sorry, I thought of $A_n(x)$ as the Chebyshev polynomial of first kind, you use the notations vise versa. So, it's ok. But why not using the common notations - $T_n$ and $U_n$.

dgrozev wrote: Pathological wrote: Lemma 2. $a_n = 2 A_n(3).$ Proof. It's very easy to show this by induction on $n$. Check it, it's not right! I'd rather get $a_n$ term explicitly using the characteristic equation of the sequence. EDIT: Oh, sorry, I thought of $A_n(x)$ as the Chebyshev polynomial of first kind, you use the notations vise versa. So, it's ok. But why not using the common notations - $T_n$ and $U_n$. Sorry, I decided to let $A_n$ denote the second Chebyshev polynomial because I initially didn't think that I would need the $B_n$'s in the proof, defining the $B_n$'s came later. I didn't know about this standard notation oops .

The official solution first finds the term $a_n$ explicitly: $$a_n = \frac{ \left(3+2\sqrt{2} \right)^n-\left(3-2\sqrt{2} \right)^n}{2\sqrt 2}$$using the characteristic equation of the sequence, which is $x^2-6x+1=0$. Denote $(3+2\sqrt 2)^n=\alpha_n+\beta_n \sqrt 2$. Then $(3-2\sqrt 2)^n=\alpha_n-\beta_n \sqrt 2$, hence $a_n=\beta_n$. Using the trick (used by @Pathological above) $3\pm 2\sqrt 2=(1\pm \sqrt 2)^2$ , one can check $\alpha_n^2 -2\beta_n^2=1$ , which yields: $$\alpha_n^2-2a_n^2=1$$At this point the author proves (he rather proves it beforehand as a lemma) that the equation $2x^{2k}+1=y^2\,,k\in\mathbb{N},k>1$ doesn't have integer pair $(x,y)$ as a solution. In fact it's the essential part. Remark: The problem was proposed by Aleksandar Ivanov.

Observe that x_n is just root of y^2 - 2x^2 = 1 pell equation so we need to prove 2x^{2k}+1=y^2, k>1 has no positive root. First we have 2 lemma: a^p +- 1 / a +- 1 has prime divsor = 1 [p] or p (easily by working with order) and 4k+3 famous lemma Claim 1: x_n | x_m if and only if: Prove similar to Fibonacci property that x_{m+n}=x_m.x_{n+1} + x_{m-1}.x_n by induct down Proof: Case 1: 2|k then equivalent to 2x^4+1=y^2 has no root so 4x^8 = (y^2-1)^2 so x^8 = y^4 - 2y^2 + 1 / 4 = (y^2 + 1 / 2)^2 - y^2. Note that (x,y)=1, (y,y^2+1)=1, (x,y^2+1/2)=1 so it's root of Pythagoras equation but x even (mod 8), y odd so y=m^2-n^2, x^4=2mn, y^2+1=2(m^2+n^2) with (m,n)=1. Hence (m^2-n^2)^2 + 1 = 2(m^2 + n^2) so (m^2 + n^2 - 1)^2 = (2mn)^2 but m,n>0 so m^2 + n^2 - 1 = 2mn so m - n = 1 so 2n(n+1)=x^4 Notice if n even hence (n+1, 2n)=1 so 2n=a^4, n+1=b^4 so 2b^4-a^4=2 so 2(b^4-1)=a^4 so 2(b^2-1)(b^2+1)=a^4 now let a=2y, b=2x+1 we have (x^2+x)(2x^2+2x+1)=y^4 now x^2+x=z^4 hence x=q^4, x+1=r^4 so q^4-r^4=1 which is only true if x=0 so n=0, absurd! Else n odd, it mean (n,2n+2)=1 so n=a^4, 2n+2=b^4 so 2a^4+2=b^4 so b=2y but LHS=4[8] so absurd Case 2: k odd. Notice k>1 has prime divisor so we only need to prove case k=p prime If k odd, if all k prime has no root so forall k note (x^{k})^4 = y^4 - 2y^2 + 1 = (y^2 + 1/2)^2 - y^2. From (y^2,y^2+1/2)=(y^2,x^{2k})=(x^{2k},y^2+1/2)=1 so y=m^2-n^2, x^{2k}=2mn, y^2+1=2(m^2+n^2), similarly m=n+1, now find x^{2k} = 2n(n+1). If n odd: (n, 2n+2) = 1 so n=a^{2k}, 2n+2=b^{2k} hence 2a^{2k}+2=b^{2k} but LHS=4[8] if k>2, 8|RHS absurd so k=2 which is not the case. So we only need to prove when n even. Now we prove that 2(a^{2p} - 1) = b^{2p} has no root. Note that a<b<2a, if RHS has prime divisor > 2a then we done. By lemma, odd prime divisor of a^p - 1 and a^p + 1 different from p is in the form of kp + 1 thus kp + 1 < 2a. Now working modulo p, 2(a^2-1)=b^2 [p], add 4x^2 choose later for both side, now if 2(a^{2p} + 2x^2 - 1) has 4k + 3 divisor not divide by x by lemma 2 we have contradiction. Now we can see that (a^p, b^p/2) is another root of pell equation at first line bút note that Pell sequence cover all their root thus we must have x_m = 8x_n . y_n = 4x_n (4x_n + 2) hence by claim, m=kn and by some small number work, we can restrict by inequality thật 3n < m < 5n thus m = 4n. Now we are left to easy computation and note that (3-2sqrt(2))^n ~ 0 as n large, we have the contradiction, thus we have the conclusion.

$a_k$=$x^k$ By generating function .... Putting in sequence get x²-6x+1= o Let roots are a,b a=3+2√2 b=3-2√2 $a_n$=c$a^n$ +d$b^n$ U can calculate d,c from $a_1$ and $a_2$

As above, we just need to show that $x^2 - 2y^{2k} = 1$ has no positive integer solutions when $k\geq 2$. Suppose the contrary. We may let $(x_0, y_0)$ be the least positive integer solution. Since $x_0$ is odd, $y_0$ is even, we have $$\left(\frac{x_0+1}{2}\right)\left(\frac{x_0-1}{2}\right)=2^{2k-1}\left(\frac{y_0}{2}\right)^{2k}.$$Thus $\frac{1}{2}(x_0+1)=2^{2k-1}y_1^{2k}$, $\frac{1}{2}(x_0-1)=x_1^{2k}$, or $\frac{1}{2}(x_0-1)=2^{2k-1}y_1^{2k}$, $\frac{1}{2}(x_0+1)=x_1^{2k}$, where $x_1$, $y_1$ satisfies $y_0/2 = x_1y_1$. We have $x_1^{2k} - 2^{2k-1}y_1^{2k} = \pm1$. By module $4$ we see that the right hand side can only take the value $+1$. Now, if we have some positive integer $x_i$, $y_i$ such that $x_i^{2k} - 2^{2k+1-2i} y_i^{2k} = 1$, $1\leq i<k$, then we have $$\left(\frac{x_i^k+1}{2}\right)\left(\frac{x_i^k-1}{2}\right) = 2^{2k-1-2i} y_i^{2k}.$$It follows that $\frac{1}{2}(x_i^k + 1) = x_{i+1}^{2k}$, $\frac{1}{2}(x_i^k - 1) = 2^{2k-1-2i}y_{i+1}^{2k}$, or $\frac{1}{2}(x_i^k-1) = x_{i+1}^{2k}$, $\frac{1}{2}(x_i^k+1)=2^{2k-1-2i}y_{i+1}^{2k}$, where the positive integers $x_{i+1}$, $y_{i+1}$ satisfies $y_i = x_{i+1}y_{i+1}$. Notice that the equation $\frac{1}{2}(x_i^k + 1) = 2^{2k-1-2i}y_{i+1}^{2k}$ cannot hold; because it implies that $x_i^k = (2^{k-i}y_{i+1}^k+1)(2^{k-i}y_{i+1}^k-1)$, so there will be two $k$-th powers with difference $2$, that is impossible. Thus we must have $$x_{i+1}^{2k} - 2^{2k-1-2i}y_{i+1}^{2k} = 1.$$Take $i=k-1$, we arrive at the equation $x_k^{2k} - 2y_k^{2k} = 1$. It follows that $(x_k^k, y_k)$ is also a solution of our original equation. But it is easy to see that $y_k < y_{k-1} < \cdots < y_1 < y_0$, contradiction!

Well, observe that a(i+1)^2= a(i)a(i+2)+4. Then use the lemma proposed by the author. ^^

LTH-0- wrote: Well, observe that $a_{i+1}^2= a_ia_{i+2}+4.$ Then use the lemma proposed by the author. ^^