Blog

Thinking Out Loud – EGMO 2015 Problem 4

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

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... Davide is a Researcher in Number Theory at the University of Pisa. Soon after being awarded a bronze medal at IMO 2008, he joined the ranks of the Italian Maths Olympiad organisers, and has been a dedicated coach, problem creator and forum moderator ever since. He is part of the Problem Selection Committee for EGMO 2018. When he’s not too overwhelmed by his teaching duties and pending article reviews he likes to unwind by playing and designing video games, singing out of tune and spending time at the beach.