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

  • 1
    $\begingroup$ 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$ $\endgroup$ – 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$.

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

  • 1
    $\begingroup$ 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 $\endgroup$ – J. W. Tanner May 14 '19 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.