I think it's more number theory than algebra . Clearly it suffices to prove that each of the terms has prime divisors of the form $ 8k+1$ or $ 8k+3$ . Then we can easily find by induction that $ x_{n-1}x_{n+1}=x_n^2+2$ so each prime divisor of $ x_{n-1},\ x_{n+1}$ divides $ x_n^2+2$ so $ -2$ is a quadratic residue so this numbers are of the form $ 8k+1$ or $ 8k+3$ and we are done .

Why is from here ob the problem trivial? Because i dont see why every number of the form 8k+1 or 8k+3 is ekspresible as a^2+2b^2

Off topic: there is no country in the world that's called Yugoslavia for many years, so I doubt there is a National Olympiad of the same as well. I should know! Please change your subtitle...

By induction $ a_{2n}=a_n^2+2.(1+a_1+a_2+...+a_{n-1})^2$ and $ a_{2n+1}=a_n^2+2.(1+a_1+a_2+...+a_n)^2$.

Colud someone explain why each number with prime divisors of the form$ 8k+1$ and $ 8k+3$(only) can be expressed in the form $ a^2+2b^2$?

Is is possible to see all the steps in crazyfehmy's proof by induction? It doesn't seem straightforward to me.

Try first for 3 and 4, then assume it's true for 2n-2 and 2n-1, prove that it's true for 2n and 2n+1.

That's what I tried and it didn't seem straightforward which is why I asked to see the proof in full.

I'm still working on a proof by mathematical induction but haven't cracked it yet. Any ideas?

I have tried to locate the source of this question but cannot find any reference to the Yugoslavia National Olympiad 2008 on the internet. Is there any such thing?

Ok, let show this proof; First we will prove that $ 2(1 + a_1 + a_2 + ... + a_n) = a_{n + 1} - a_n$ by induction. For $ n = 1$ , $ 2(1 + 3) = 11 - 3$ true. Let it's true for $ n = k$. Because of $ a_{k + 2} = 4a_{k + 1} - a_k \Longrightarrow$ $ 2(a_1 + a_2 + ... + a_k + a_{k + 1}) = a_{k + 1} - a_k + 2a_{k + 1} = a_{k + 2} - a_{k + 1}$. Now we will prove that $ a_{2n} = a_n^2 + 2.(1 + a_1 + a_2 + ... + a_{n - 1})^2$ and $ a_{2n + 1} = a_n^2 + 2.(1 + a_1 + a_2 + ... + a_n)^2$ by induction. For $ n = 1 , 11 = 3^2 + 2(1)^2$ and $ a_3 = 41 = 3^2 + 2(1 + 3)^2$ true.Let it's true for $ n = k \Longrightarrow$ $ a_{2k + 2} = 4a_{2k + 1} - a_{2k} = 3{a_k}^2 + 8(1 + a_1 + a_2 + ... + a_k)^2 - 2(1 + a_1 + a_2 + ... + a_{k - 1})^2 =$ $ [3a_k + 2(1 + a_1 + a_2 + ... + a_{k - 1})]^2 + 2(a_1 + a_2 + ... + a_k)^2 = {a_{k + 1}}^2 + 2(a_1 + a_2 + ... + a_k)^2$ and by same way; $ a_{2k + 3} = {a_{k + 1}}^2 + 2.(1 + a_1 + a_2 + ... + a_{k + 1})^2$

AndrewTom wrote: I have tried to locate the source of this question but cannot find any reference to the Yugoslavia National Olympiad 2008 on the internet. Is there any such thing? As milin alrady pointed out, there's no such country in the world anymore. The problem is from Serbian Mathematical Olympiad 2008.

Wonderful crazyfehmy. Would you mind posting the steps for the case a(2k+3)?

By using $ 2(1+a_1+a_2+...+a_k)=a_{k+1}-a_k$ $ 4[{a_{k+1}}^2+2(1+a_1+a_2+...+a_k)^2]-a_k^2-2(1+a_1+a_2+...+a_k)^2=$ $ {a_{k+1}}^2+2(1+a_1+a_2+...+a_{k+1})^2 \Longrightarrow$ $ 4a_{2k+2}-a_{2k+1}={a_{k+1}}^2+2(1+a_1+a_2+...+a_{k+1})^2=a_{2k+3}$

Thanks. I've just done it but yours is shorter.

Having proved that a(n-2)a(n) = (a(n-1))^2 + 2, I am now looking at silouan's post and would like to see much more detail as I am presuming that this means -2 is a quadratic residue of a(n) but don't know why this means that the prime factors of a(n) are 1 or 3 (mod 8), although I've noticed that the first few terms, 3, 11, 41, 153, 571, 2131, 7953 and 29681 are, nor do I know why this means that a(n) is of the form a^2 + 2b^2.

A generalization one . . Let $ a_n$ be a sequence in a algebraically closed field defined by $ \ a_0 = 1, \ a_1 = B - 1,\ a_{n + 2} = Ba_{n + 1} - a_n$ . Prove that : $ a_{2n} = a_n^2 + (B - 2)(a_0 + ... + a_{n - 1})^2,\ a_{2n + 1} = a_n^2 + (B - 2)(a_0 + ... + a_n)^2$

I calculated some values and got the results $a_1=(1,1)$ $a_2=(3,1)$ $a_3=(3,4)$ $a_4=(11,4)$ $a_5=(11,15)$ $a_6=(41,15)$ here $(x,y)$ denotes $x^2+2y^2$. From these I guessed that the sequence works in the following way: if $a_n=a^2+2b^2$ then $a_{n+1}$ is either $a^2+2(a+b)^2$ or $(a+2b)^2+2b^2$ and these two happen alternately. This fact is easy to prove by induction.

Let $ (b_n)_{n\ge 1}$ the sequence defined by $b_1=1$, $b_2=4$ and $b_n=4b_{n-1}-b_{n-2}$, for $n\geq 3$ and we assumed and we assume for convenience that $a_1=1,a_2=3$ and $a_n=4a_{n-1}-a_{n-2}$, for $n\geq 3$ We prove by induction on $n$ that: $a_{n+1}-a_{n}$ $=$ $2b_n...(\star)$. For $n=1,2$ we get $3-1=2.1$ and $11-3=2.4$ which satisfies $(\star)$ For $n\geq 2$, assuming the result is true for $1,2, . . . , n$, we have: $a_{n}-a_{n-1}$ $=$ $2b_{n-1}$ and $a_{n+1}$ $-$ $a_{n}$ $=$ $2b_{n}$. Since $b_{n+1}$ $=$ $4b_{n}-b_{n-1}$ $\Longrightarrow$ $2b_{n+1}$ $=$ $8b_{n}-2b_{n-1}$ $\Longrightarrow$ $2b_{n+1}$ $=$ $(4a_{n+1}-4a_{n})-(a_n-a_{n-1})$ $=$ $4a_{n+1}$ $-$ $5a_n$ $+$ $4a_{n}$ $-$ $a_{n+1}$ $=$ $a_{n+2}$ $-$ $a_{n+1}$ which satisfies $(\star)$. We prove by induction on $n$ that: $(a_{2n-1}$ $=$ $a_{n}^2$ $+$ $2b_{n}^2$ and $a_{2n}$ $=$ $a_{n+1}^{2}$ $+$ $2b_{n}^2)$ $...(\star\star)$. For $n=1$, we get $3=1^2+2.1^2$ and $11$ $=$ $3^2+2.1^2$ and which satisfies $(\star\star)$ For $n\geq 1$, assuming the result is true for $1, . . . , n$, we have: $a_{2n-1}$ $=$ $a_{n}^2$ $+$ $2b_{n}^2$ and $a_{2n}$ $=$ $a_{n+1}^{2}$ $+$ $2b_{n}^2$. Since $a_{2n+1}$ $=$ $4a_{2n}$ $-$ $a_{2n-1}$ $\Longrightarrow$ $a_{2n+1}$ $=$ $(4a_{n+1}^2$ $+$ $8b_{n}^2)$ $-$ $(a_{n}^{2}$ $+$ $2b_{n}^2)$ $\Longrightarrow$ $2a_{2n+1}$ $=$ $8a_{n+1}^2$ $+$ $12b_{n}^2$ $-$ $2a_n^2$, replacing $12b_n^2$ $=$ $3$ $.$ $(a_{n+1}-a_{n})^2$ we get $2a_{2n+1}$ $=$ $11a_{n+1}^2$ $+$ $a_n^2$ $-$ $6a_n$ $.$ $a_n$ $=$ $2a_{n+1}^2$ $+$ $(3a_{n+1}$ $-$ $a_n)^2=$ $2a_{n+1}^2$ $+$ $(a_{n+2}$ $-$ $a_{n+1})^2$ $=$ $2a_{n+1}^2$ $+$ $4b_{n+1}^2$ $\Longrightarrow$ $a_{2n+1}$ $=$ $a_{n+1}^2$ $+$ $2b_{n+1}^2$. Since $a_{2n+2}$ $=$ $4a_{2n+1}$ $-$ $a_{2n}$ $\Longrightarrow$ $a_{2n+2}$ $=$ $(4a_{n+1}^2$ $+$ $8b_{n+1}^2)$ $-$ $(a_{n+1}^{2}$ $+$ $2b_{n}^2)$ $\Longrightarrow$ $2a_{2n+2}$ $=$ $6a_{n+1}^2$ $+$ $16b_{n+1}^2$ $-$ $4b_{n}^2$, replacing $12b_{n+1}^2$ $=$ $3$ $.$ $(a_{n+2}$ $-$ $a_{n+1})^2$ and $4b_n^2$ $=$ $(a_{n+1}$ $-$ $a_{n})^2$ and $a_{n+2}$ $=$ $4a_{n+1}$ $-$ $a_n$ we get $2a_{2n+2}$ $=$ $2a_{n+2}^2$ $+$ $4b_{n+1}^2$ $\Longrightarrow$ $a_{2n+2}$ $=$ $a_{n+2}^{2}$ $+$ $2b_{n+1}^2$ hence $(a_{2n+1}$ $=$ $a_{n+1}^2$ $+$ $2b_{n+1}^2$ and $a_{2n+2}$ $=$ $a_{n+2}^{2}$ $+$ $2b_{n+1}^2)$ therefore induction is complete $\Longrightarrow$ each term of this sequence is of the form $ a^2 + 2b^2$ for some natural numbers $ a$ and $ b$.

Lemma :A number $K$ can be expressed $a^2+2b^2$ if and only if for primes $p \equiv 1,3 \pmod8$$v_p(K) \equiv 0 \pmod 2$ Proof: if part is trivial .For the only if part we should prove for a prime $p \equiv 1,3 \pmod8$ there exist positive integers $a ,b$ such that $p=a^2+2b^2$ (indeed these $a$ and $b$ are unique) .Becasue of $p \equiv 1,3 \pmod8$ there is a integer $x^2 \equiv -2 \pmod p$ By thue's lemma there exist integers $a,b$ such that $0<a^2,b^2<p$ and $a \equiv xb \pmod p $ so $p|a^2+2b^2$ and $0<a^2+2b^2<3p$ then $p=a^2+2b^2$ or $2p=a^2+2b^2$ for first case we are done for second case $a$ is even $a=2a'$ then we are done again .$2=0^2+2.1^2$ for prime $p \equiv 1,3 \pmod8$ $p^2=p^2+2.0^2$ By Brahmagupta identity , $(x^2+2y^2)(a^2+2b^2)=(ax+by)^2+2(xb-ay)^2$ lemma is proven . $\square$ Beyond this theory problem is trivial .By induction $a_n^2-4a_na_{n+1}+a_{n+1}^2=-2$ if $p|a_n$ then $p|a_{n+1}^2+2$ then $p \not\equiv 5 ,7 \pmod8$. $\blacksquare$