We can let $a_n=b_n^2+c_n$, where $0<=c_n<=2b_n$ for a start? We arrive at $2b_n^2=b_{n+1}^2+c_{n+1}-c_n$. So we want to prove that there are infinitely many even and odd $c_n$.

Can someone finish it?

Let $a_n=b_{n}^{2}+c_n$, where $0\leq c_n \leq 2b_n$. Then $b_n=\lfloor\sqrt{a_n}\rfloor$. Claim 1: $0\leq 2b_n-b_{n+2}\leq 1$ $\forall n\geq 1$. For all $n\geq 1$: $a_{n+1}-a_{n}=b_{n}^{2} \Rightarrow a_{n+1}=a_{n}+b_{n}^{2}\leq 2a_n$. First, we will show that $b_{n+2}\leq 2b_n$. We have: $$b_{n}^{2}\leq a_n<(b_n+1)^2$$$$\Rightarrow 2b_{n}^{2}\leq a_{n+1}<b_{n}^{2}+(b_n+1)^2$$$$\Rightarrow (2b_n)^2\leq 2a_{n+1}<4b_{n}^{2}+4b_n+2=(2b_n+1)^2+1$$$$\Rightarrow 2a_{n+1}<(2b_n+1)^2$$(note that $2a_{n+1}\not\equiv (2b_n+1)^2$ (mod $2$)). Since $a_{n+2}\leq 2a_{n+1}$, we get $a_{n+2}<(2b_n+1)^2$. Moreover, $a_{n+2}\geq b_{n+2}^{2}$ so $b_{n+2}^{2}<(2b_n+1)^2 \Rightarrow b_{n+2}<2b_n+1 \Rightarrow b_{n+2}\leq 2b_n$. Second, we will prove that $b_{n+2}+1>2b_n-1$, which leads to $b_{n+2}+1\geq 2b_n$. Apparently $a_{n+2}<(b_{n+2}+1)^2$. It suffices to show that: $$a_{n+2}> (2b_n-1)^2 \Leftrightarrow a_n+b_{n+1}^{2}+b_{n}^{2}>4b_{n}^{2}-4b_n+1$$We have $2b_{n}^{2}\leq a_{n+1}<(b_{n+1}+1)^2$ so $b_{n+1}>b_n\sqrt{2}-1$. Hence: $$a_n + b_{n+1}^{2} + b_{n}^{2}> 2b_n^2 + (b_n\sqrt{2}-1)^2=4b_n^2 - 2b_n\sqrt{2} + 1>4b_n^2 - 4b_n + 1$$ Claim 2: Let $A=\{n: 2b_n-b_{n+2}=1\}$. Then $A$ is infinite. Suppose that $A$ is finite, then there exists $m$ so that $2b_n=b_{n+2}$ for all $n\geq m$. We have: $$a_{n+1}-a_n=b_n^2$$$$\Leftrightarrow b_{n+1}^2+c_{n+1}-b_{n}^2-c_n=b_n^2$$$$\Leftrightarrow 2b_n^2=b_{n+1}^2+c_{n+1}-c_n$$$$\Rightarrow 2b_{n+1}^2=b_{n+2}^2+c_{n+2}-c_{n+1}$$Thus: $4b_n^2=b_{n+2}^2+c_{n+2}+c_{n+1}-2c_n \Rightarrow c_{n+2}+c_{n+1}-2c_n=0$ for all $n\geq m$. Hence: $c_n=a+b\cdot (-2)^{n-m}$ for all $n\geq m$, in which $a,b\in \mathbb{Z}$. If $b>0$, choose large enough $n$ so that $n-m$ is odd, we get $c_n<0$, a contradiction. If $b<0$, choose large enough $n$ so that $n-m$ is even, we also get a contradiction. So $b=0 \Rightarrow c_n=a$ for all $n\geq m$. But then $2b_n^2=b_{n+1}^2 \Rightarrow b_n=0$ for all $n\geq m$, a contradiction. Suppose that $(a_n)$ has finitely many odd (or even) numbers, then there exists $M$ so that $a_n$ is even (or odd) for all $n\geq M$. Hence, $b_n$ is even for all $n\geq M$. Since $A$ is infinite, we get $A\cap \mathbb{Z}_{\geq M}\neq \emptyset$. For all $n\in A\cap \mathbb{Z}_{\geq M}$, we have $2b_n-b_{n+2}=1$, so $b_{n+2}$ is odd, which is a contradiction.

A shorter way to prove Claim 2: If $b_{n+2}=2b_n$ for all large $n$, then in particular $\frac{b_{2n+2}}{b_{2n+1}}$ is the same rational number for all large $n$. But on the other hand, one easily sees that $\lim_{n \to \infty} \frac{b_{n+1}}{b_{n}}=\sqrt{2}$ which is impossible since $\sqrt{2}$ is irrational.

Very nice problem! We instead look at the sequence $b_n=\lfloor \sqrt{a_n}\rfloor$. Now, $b_{n+1}\in \{\lfloor \sqrt{2}b_n\rfloor, \lceil \sqrt{2}b_n\rceil\}$. Observe that $a_{n+2}\le 4a_n$ and thus $a_{n+2}< 4(b_n+1)^2\implies b_{n+2}<2b_n+2$. Similarly, $a_{n+1}=a_n+b_n^2\implies a_{n+1}\ge 2b_n^2$ and thus, $a_{n+2}\ge 2b_n^2+b_{n+1}^2\ge 2b_n^2+2(\sqrt{2}b_n-1)^2> (2b_n-1)^2\implies b_{n+2}>2(b_n-1)$. Thus, $b_{n+2}\in \{2b_n\pm 1, 2b_n\}$. Now, FTSOC, there are only finitely many odds or finitely many evens in the sequence $a_i$. Then, for some $N$, and all $n>N$, we must have $b_n$ is even. Thus, $b_{n+2}=2b_n$ and $b_{n+3}=2b_{n+1}$. Now, observe that if $b_{n+1}=\lfloor \sqrt{2}b_n\rfloor$ then $\sqrt{2}b_{n+1}<2b_n$ and thus, $b_{n+2}=\lceil \sqrt{2}b_{n+1}\rceil$. And similarly, if $b_{n+1}=\lceil \sqrt{2}b_n\rceil$ then $b_{n+2}=\lfloor \sqrt{2}b_{n+1}\rfloor$. Thus, the sequence alternates in floors and ceilings. WLOG, for some $m>N$, we have $b_{m+1}=\lceil \sqrt{2}b_{m}\rceil$. Now, observe that $2^k\lceil \sqrt{2}b_m\rceil=b_{m+1+2k}=b_{m+2k+1}=\lceil \sqrt{2}b_{m+2k}\rceil=\lceil \sqrt{2}2^kb_m\rfloor$. Thus, for arbitrarily large $k$ we have $2^k\lceil b_m\sqrt{2}\rceil-\sqrt{2}2^kb_m<1\implies 2^k(\lceil b_m\sqrt{2}\rceil-\sqrt{2}b_m)<1$ but we can just pick $k$ large enough so that this fails and thus we are done!

Nice and unique! Define positive integer sequences $\{b_i\}$ and $\{r_i\}$ such that $a_i=b_i^2+r_i$ where $0 \leq r_i \leq 2b_i$ for all $i$. We have the following key claim. Claim: In general, we have $b_{i+2} \in \{2b_i,2b_i-1\}$ for all large enough $b_i$ Proof: Note that $a_{i+1}=2b_i^2+r_i$, so $a_{i+2} \leq 4b_i^2+2r_i \leq 4b_i^2+4b_i<(2b_i+1)^2$. On the other hand, in general we also have $a_{k+1} \geq 2a_k-2\sqrt{a_k}$, so $$a_{i+2} \geq 4b_i^2+2r_i-2\sqrt{2b_i^2+r_i} \geq 4b_i^2-2\sqrt{2b_i^2} \geq 4b_i^2-(4b_i-1) \geq (2b_i-1)^2$$for sufficiently large $b_i$. This implies the result. $\blacksquare$ We also have $\lim_{n \to \infty} \tfrac{a_{n+1}}{a_n}=\sqrt{2}$, since this fraction is at most $2$ but at least $2-\tfrac{2}{\sqrt{a_n}}$ and obviously $a_n \to \infty$ as $n \to \infty$. If $a_n$ is eventually fixed parity, $b_n$ must eventually be even, so we must have $b_{i+2}=2b_i$ for all $i$. But then the ratio $\tfrac{b_{2i+1}}{b_{2i}}$ is fixed and rational for all large enough $i$, yet converges to $\sqrt{2} \not \in \mathbb{Q}$: contradiction. $\blacksquare$