If $u_1=1$ and $u_{n+1} = n+\sum_{k=1}^n u_k^2$, then $u_n$ is never a square.

Cute problem I saw on quora:

If $$u_1 = 1,\qquad u_{n+1} = n+\sum_{k=1}^n u_k^2 $$ show that, for $n \ge 2$, $u_n$ is never a square.

\begin{align} n&=1:& u_2 &= 1+1 = 2\\ n&=2:& u_3 &= 2+1+4 = 7\\ n&=3:& u_4 &= 3+1+4+49 = 57\\ \end{align}

And, as usual, I have a generalization:

If $$a \ge 1,\quad b \ge 0,\quad u_1 = 1,\quad u_{n+1} = an+b+\sum_{k=1}^n u_k^2,$$ where $a, b \in \mathbb{Z}$, then for $n \ge 3$, $u_n$ is never a square.

Note: My solutions to these do not involve any explicit expressions for the $u_n$.

Solution 1:

The recurrence can be rewritten as \begin{eqnarray*} u_{n+1}=u_n^2+u_n+1. \end{eqnarray*} It is easy to show that \begin{eqnarray*} u_n^2 < u_{n+1} <(u_n+1)^2. \end{eqnarray*} Now observe that there is no whole numbers between $u_n$ & $u_n+1$.

Solution 2:

The problem, indeed, is very cute.

We just need to check the condition $\textrm{mod } 5$: $$u_1 \equiv 1 \textrm{ mod } 5$$ $$u_2 \equiv 2 \textrm{ mod } 5$$ $$u_3 \equiv 2 \textrm{ mod } 5$$ etc.

Therefore, one can show by induction that for any $n \in \mathbb{N}$: $$u_{n+1} \equiv \left[ n+1+\sum_{j=2}^n (-1) \right] \textrm{ mod } 5 \equiv 2 \textrm{ mod } 5.$$ The latter is never true for squares, since squares are equal to either 0,1 or 4 mod 5.

To prove the generalization, we use the recurrence relation of type $$u_{n+1} = u_n^2+u_n+a.$$ Notice that $u_{n+1}>u_n^2$ since $a>0$.

Therefore, if $u_{n+1}$ is a perfect square, then $a\geq u_n+1 > u_n$.

But $a>u_n$ is impossible since for any $n \geq 3$: $$u_{n} = u_{n-1}^2+u_{n-1}+a >a.$$ This gives us a contradiction, so $u_n$ is never a perfect square for any $n\geq 3$.