Simple proof for the Legendary Question 6. International Mathematical Olympiad (IMO) 1988

Question

Question number 6 posed at the 1988 International Mathematical Olympiad (IMO) has become famous for its relative complexity. It consisted in showing that:

Let $n_{i}$ and $n_{i+1}$ be positive integers such that $(1+n_{i} × n_{i+1})$ divides $(n_{i}^2+n_{i+1}^2)$. Show that

$$ \frac{n_{i}^2+n_{i+1}^2}{1+n_{i} n_{i+1}} \tag{1}$$

is the square of an integer.

This problem has been made famous also through the work of popularizers, therefore I think that a simple proof of it could be of interest even for those who are not particularly skilled in mathematics.

So I tried to formulate an accessible one for anyone who has minimal confidence with the equations of the second degree.

$ \ $ Any suggestions or clarifications will be welcome!!

Answer 1

$\mathbf{ The}\ \mathbf{ proof:} $

Let's put the above problem in a different but equivalent way:

think of $ n_ {i} $ and $ n_ {i + 1} $ not as positive integers but as solutions of the following equation:

$$ \frac{n_{i}^2+n_{i+1}^2}{1+n_{i} n_{i+1}}=s \tag{2}$$

Show that $ n_ {i} $ and $ n_ {i+ 1} $ can be integers only if $ s $ is a perfect square.

Let $ n_ {i} $ be a known solution, let's look for the other solution $ x $ through the famous solution formula of the second degree equations: $$ a x^{2}+b x+c=0 \\ x_{1,2}=\frac{-b \pm \sqrt{b^2 - 4 ac}}{2a} $$

So

$$ \frac{n_{i}^2+x^2}{1+n_{i} x}=s \tag{3}$$

$ \ $

$$n_{i}^2+x^2=s(1+n_{i} x) \\ x^2 + (-s n_{i})x+(n_{i}^2-s)=0 \\ x_{1,2}=\frac{1}{2}\bigg(n_{i} s\pm \sqrt{n_{i}^2 s^2+4(s-n_{i}^2)}\bigg) $$

if $(n_{i}s) \neq 0$

$$x_{1,2}=\frac{n_{i} s}{2}\bigg(1\pm \sqrt{1+4 \bigg( \frac{s-n_{i}^2}{n_{i}^2 s^2} \bigg)} \bigg) \tag{4} $$

Note that the element under the square root looks a lot like the square of a binomial:

$$ 1+4 \bigg( \frac{s-n_{i}^2}{n_{i}^2 s^2}\bigg)=\bigg(1-2 \frac{ q}{n_{i} s} \bigg)^2=1+4 \frac{q^2}{n_{i}^2 s^2}-4\frac{q}{n_{i} s} \tag{5} $$

So we can rewrite $(4)$ as:

$$ x_{1} =\frac{n_{i} s}{2} \Bigg(1 - \bigg(1-\frac{2 q}{n_{i} s} \bigg) \Bigg)=q \\ x_{2} =\frac{n_{i} s}{2} \Bigg(1 + \bigg(1-\frac{2 q}{n_{i} s} \bigg) \Bigg)= n_{i} s -q $$

We have the beautiful result that $ q = x_ {1} $ this allows us in one fell swoop to: determine the value of $ q $, and make sure that the two solutions of $(3)$ are linked by the following relation:

$$ x_{2}=n_{i} s -x_{1} \tag{6} $$

But what is $ n_ {i} $? $ n_ {i} $ is also a solution! so if we know two solutions $ n_ {i} $ and $ x_ {1} $ we can automatically get a third one!

This is so amazing because we now have a formula to generate all the solutions $n_{i}$ for $ (2) $ (when $n_{i} s \neq 0$) as long as we know at least two of them.

Since the equation $(2)$ is symmetric for $n_{i}$ and $n_{i+1}$, the procedure done in $ (3) $ to get $ x $ can be used equivalently to get $ n_ {i} $ and vice versa, we can write $ (6) $ as: $$ n_{i+1}=n_{i} s -n_{i-1} \tag{7} $$

Now we will use the case $ n_ {i} s = 0 $ to get the first two solutions:

$$n_ {i} s=0\begin{cases} \text{if $n_{i}=0, n_{i} \neq s \tag{a}$} \\ \text{if $s=0, n_{i} \neq s \tag{b}$} \\ \text{if $s=0=n_{i} \tag{c} $ } \end{cases} $$

We have that $(c)$ implies $n_{i}=n_{i+1}=0$ is a solution, and the case $ (b) $ can never be verified:

$$ \frac{n_{i}^2+n_{i+1}^2}{1+n_{i} n_{i+1}}=0 \Leftarrow\Rightarrow n_{i}=n_{i+1}=0 $$

Since if we use $ n_ {i} = n_ {i + 1} = 0 $ in $ (7) $ we don't get new solutions, so we use the case $ (a) $ to get a solution $ n_ {i + 1} \neq n_ {i} $:

$$ \frac{0^2+n_{i+1}^2}{1+0 n_{i+1}} =n_{i+1}^2=s \Leftarrow\Rightarrow n_{i+1}=\sqrt{s} $$

The solutions $ n_ {i} $ must be positive so the solution $ n_ {i} = 0 $ will surely be the smallest that can be found therefore we call it $ n_ {0} = 0 $ we will then have $ n_ {1 } = \sqrt {s} $. We have found two solutions, which if compared with all the others, with the same $ s $ take smaller values:

$$ \forall i , s>1 : 0=n_{0}< \sqrt{s}=n_{1}<n_{i}. $$

Known the first two solutions we can find the third and so on:

$$n_{0}=(0 )\sqrt{s} \\ n_{1}=(1) \sqrt{s} \\ n_{2}=s n_{1}-n_{0}=(s) \sqrt{s}\\ n_{3}=(s^{5}-1)\sqrt{s} \\ \vdots$$

Looking at the equation $ (7) $ we notice that if $ (s) $ is integer and $ n_ {i} $ and $ n_ {i-1} $ can be written as $ \alpha, \beta, \gamma \in \mathbb{Z}$: $$ n_ {i-1} = \alpha \sqrt {s}, \ \ n_ {i} = \beta \ \sqrt {s}$$

Then we have that all solutions can be written as:

$$n_ {i + 1} = s \beta \sqrt {s} - \alpha \sqrt {s} = (\beta s - \alpha) \sqrt {s} = \gamma \sqrt {s} $$

And this is our case! so we have that $n_ {i}$ can be integer if and only if $ s $ is the square of an integer!

$$ \square $$