, 2021

Suppose there are not infinitely many odd numbers or not infinitely many even numbers, then there exists an $N$ such that the sequence $a_N, a_{N+1}, a_{N+2}, \dots$ all have the same parity. So when $n \ge N$,
$$b_n := \lfloor \sqrt{a_n} \rfloor = \sqrt{a_{n+1} - a_n}$$
is even. Let $k_n = a_n - b_n^2$, then $0 \le k_n \le 2b_n$. We have
$$a_{n+1} = a_n + b_n^2 = 2b_n^2 + k_n \implies b_{n+1} \le \sqrt{2b_n^2 + k_n} < b_{n+1} + 1,$$
therefore from $a_{n+2} = 2b_{n+1}^2 + k_{n+1} = 2b_n^2 + k_n + b_{n+1}^2$,
$$a_{n+2} \le 4b_n^2 + 2k_n \le 4b_n^2 + 4b_n < (2b_n + 1)^2$$
$$a_{n+2} > 2b_n^2 + k_n + (\sqrt{2b_n^2 + k_n} - 1)^2 = 4b_n^2 + 2k_n + 1 - 2\sqrt{2b_n^2 + k_n}.$$
Note that
$$4b_n^2 + 2k_n + 1 - 2\sqrt{2b_n^2 + k_n} \ge (2b_n - 1)^2 \iff 2b_n + k_n \ge \sqrt{2b_n^2 + k_n},$$
and the latter is clearly true, so we have $b_{n+2} = \lfloor a_{n+2} \rfloor = 2b_n - 1$ or $2b_n$. Since $b_{n+2}$ is even when $n + 2 \ge N$, we have $b_{n+2} = 2b_n$. Thus we have $b_{N+2s} = 2^s b_N, b_{N+2s+1} = 2^s b_{N+1}$.
$$b_{N+2s}^2 = a_{N+2s+1} - a_{N+2s} = b_{N+2s+1}^2 - b_{N+2s}^2 + k_{N+2s+1} - k_{N+2s},$$
we have
$$k_{N+2s+1} - k_{N+2s} = 2b_{N+2s}^2 - b_{N+2s+1}^2 = 2^{2s}(2b_N^2 - b_{N+1}^2),$$
from $0 \le k_n \le 2b_n$, we have
$$2^{2s}|2b_N^2 - b_{N+1}^2| \le 2b_{N+2s+1} + 2b_{N+2s} = 2^{s+1}(b_{N+1} + b_N).$$
Note that $2$ is not a perfect square, so $2b_N^2 - b_{N+1}^2 \ne 0$, hence taking $s$ sufficiently large yields a contradiction.