Blog

EGMO 2015, Problem 4. Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \] for every positive integer $n$.

My first thought is that these numbers grow, but not too quickly: roughly speaking, since $a_n < a_{n+1}$, one has $a_{n+2} \leq \sqrt{a_n}(\sqrt{a_n} + \sqrt{2}) < (\sqrt{a_n}+1)^2$. So in particular setting $b_n=\sqrt{a_n}$ I find that $b_{n+1} \leq b_n+1$. The reason I'm interested in this is that $a_{n+1}+a_n$ needs to be a square for every $n$ (so it grows fast!); maybe let's give this square a name: $c_n^2=a_{n+1}+a_n$. Now clearly $c_{n+1} \geq c_n + 1$, so the hope is that comparing the two inequalities will give a contradiction. Let's see: in deriving the first one I haven't been very careful, so I might as well do some rough estimates on the second one too. For example, $c_n^2 \leq 2a_{n+1}$, so $a_{n+1} \geq \frac{c_n^2}{2} \geq \frac{n^2}{2}$, which unfortunately is not good enough to contradict $a_n \leq n^2$ (which is what I get, at least as order of magnitude, from $b_{n+1} \leq b_n + 1$).

Long, more honest version
Ok, I was hoping for too much, clearly. Let's be somewhat more precise. The same computation as before gives $a_{n+1} \leq (\sqrt{a_n} + \frac{\sqrt{2}}{2})^2$, so $b_n \leq \frac{\sqrt{2}n}{2}$ and $a_n \leq \frac{n^2}{2}$. Uhm... this is exactly the same as the upper bound, so now I need to do things properly. It's not clear that it will work, though: the precise additive constants in the inequalities will be important. Let's see: the true versions of the rough inequalities are
\[
b_n \leq b_0 + \frac{n\sqrt{2}}{2} \Rightarrow a_n \leq \frac{n^2}{2} + \sqrt{2a_0}n + a_0
\]
and
\[
c_n \geq c_0+n =\sqrt{a_0+a_1}+n \Rightarrow a_{n+1} \geq \frac{c_n^2}{2} = \frac{n^2+2\sqrt{a_0+a_1}n+(a_0+a_1)}{2}
\]
which maybe works? That is, maybe these inequality give a contradiction? Replacing $n+1$ by $n$ and comparing the upper and lower bound for $a_n$, the terms $n^2/2$ cancel out, and we find that
\[
\sqrt{2a_0}n + a_0 \geq \frac{-2n+1+2\sqrt{a_0+a_1}(n-1)+(a_0+a_1)}{2},
\]
which gives a contradiction for $n$ large provided that $\sqrt{2a_0} < \sqrt{a_0+a_1}-1$. But this needs not be true, if $a_1$ is smaller than $a_0$. Which makes me realize: my inequalities are not even technically correct, because I've assumed $a_n$ to be increasing, which is only true from $a_2$ onward! This is getting way too complicated, I think I just want a better lower bound on $c_n$ or a better upper bound on $a_n$.

Abridged version – also continuation of the long (and true) version.
Do I know anything more about these numbers $a_n, c_n$? Something that sticks out is that there are parity conditions, namely $a_{n+1}$ has the same parity as $a_{n-1}$. And this implies that the parity of $c_n^2 = a_n+a_{n-1}$ is constant. Ah, this is great, because it gives $c_{n+1} \geq c_n+2$, and not just $+1$! Is this quite true? I guess $a_n > a_{n-1}$ is true at least for $n \geq 2$, so $c_{n}$ is increasing for $n \geq 1$. So to be on the safe side let's say $c_n \geq (c_0+c_1)+2(n-1)$. So for $n$ 'large' (which probably just means $2$ or more) $a_{n+1} \geq \frac{c_n^2}{2} \geq 2n^2 + (\text{stuff that is either constant or linear in }n)$, while we know $a_n \leq (\text{constant} + \frac{\sqrt{2}}{2}n)^2 \leq \frac{n^2}{2} + (\text{stuff which is constant or linear in }n)$, which is clearly a contradiction for $n$ large. Done: there's no such sequence $a_n$!

Some additional comments

I'm sure there are a number of different solutions to this problem, but this one is instructive at least because it's an instance (yet another one!) of the general principle that in many number-theoretical questions one needs to combine congruences and inequalities to get to the solution. Furthermore, this solution came naturally to me, at least in the sense that a very common technique to prove that a certain expression is not a square is to show that it lies strictly between two consecutive squares; while this is not what I ended up doing, such an idea would have required good upper and lower bounds on $a_{n+1}+a_{n}$, so I thought it couldn't hurt to start with those. And then, sometimes, you get lucky...