# 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$$.

• I see the answer from considering modulo $5$. I wonder if it could also be proved that $u_n$ is never a square because $u_{n-1}<\sqrt{u_n}<u_{n-1}+1$ – J. W. Tanner May 14 '19 at 0:15

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$$.

• although, I need to think a bit more about the generalization – Jane May 14 '19 at 0:12
• That is very nice, and it is completely different than my solution, so I will accept it. Now, how about the generalization? – marty cohen May 14 '19 at 0:12
• thank you! i am thinking about the generalization right now. – Jane May 14 '19 at 0:13
• I added the proof for the generalization by editing this post. – Jane May 14 '19 at 0:34
• Minor correction: "squares are equal to 0 or 1 or 4 mod 5" – aschepler May 14 '19 at 6:53

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$$.

• This was the idea I expressed in my comment; I just didn't take the time to flesh it out; thank you for doing so – J. W. Tanner May 14 '19 at 0:36