So sequence

We proceed inductively. As a base case, note that $a_9=16=(2^2)^2$ . In particular, $a_k=(2^{j})^2$ for some $j$ (in this case, $j=2$ ). We now show that, if $2^{2j}=(2^j)^2$ appears in our sequence, a greater power of two (specifically, $(2^{j+1})^2$ ) must also appear in our sequence. To that end, let $a_n=x^2$ for $x=2^j$ , for some $j\geq 2$ . Then, $\begin{aligned} a_{n+1} &= x^2 + x &< (x+1)^2 \\ a_{n+2} &= a_{n+1} + \left\lfloor\sqrt{a_{n+1}}\right\rfloor = x^2 + x + x = x^2 + 2x &< (x+1)^2 \\ a_{n+3} &= a_{n+2} + \left\lfloor\sqrt{a_{n+2}}\right\rfloor = x^2 + 3x + x = x^2 + 3x &> (x+1)^2\\ a_{n+4} &= a_{n+3} + \left\lfloor\sqrt{a_{n+3}}\right\rfloor = x^2 + 3x + (x+1) = x^2 + 4x + 1 &< (x+2)^2\\ a_{n+5} &= a_{n+4} + \left\lfloor\sqrt{a_{n+4}}\right\rfloor = x^2 + 4x + 1 + (x+1) = x^2 + 5x + 2 &> (x+2)^2\\ a_{n+6} &= a_{n+5} + \left\lfloor\sqrt{a_{n+5}}\right\rfloor = x^2 + 5x + (x+2) = x^2 + 6x + 4 &< (x+3)^2\\ a_{n+7} &= a_{n+6} + \left\lfloor\sqrt{a_{n+6}}\right\rfloor = x^2 + 6x + 4 + (x+2) = x^2 + 7x + 6 &> (x+3)^2 \end{aligned}$

The inequalities for $a_{n+5}$ and $a_{n+7}$ hold because $x\geq 4$ . This pattern continues for $k<2x+1$ , with $a_{n+k} = \begin{cases} x^2 + kx + (\frac{k-2}{2})^2 & k\text{ is even} \\ x^2 + kx + [(\frac{k-3}{2})^2 + \frac{k-3}{2}] & k\text{ is odd} \end{cases}$

Let $k=2x+1$ . Then $a_{n+2x+1} = x^2 + (2x+1) x + \left[\left(\frac{2x-2}{2}\right)^2 + \frac{2x-2}{2}\right] = x^2 + (2x)x + x + (x^2-2x+1) + (x-1) = x^2 + 2x^2 + x^2 = (2x)^2$

Since $x=2^j$ , $a_{n+2x+1}=(2x)^2=2^{j+2}$ . Thus, there are infinitely $a_n$ that are powers of two (specifically, all powers of two with an even exponent will appear in our sequence).