IMO Problem Shortlist

At first we notice that $$\begin{array}{rl}(1-\alpha {)}^{\frac{1}{2}}(1-\beta {)}^{\frac{1}{2}}& =\left(1-\frac{1}{2}\cdot \alpha -\frac{1}{8}\cdot {\alpha }^2-\cdots \right)\left(1-\frac{1}{2}\cdot \beta -\frac{1}{8}\cdot {\beta }^2-\cdots \right)\\ & =\sum _{k,\ell \ge 0}{c}_{k,\ell }\cdot {\alpha }^k{\beta }^{\ell }\text{ for all }\alpha ,\beta \in (0,1)\end{array}$$ where $c_{0,0}=1$ and $c_{k,\ell }$ are certain coefficients. For an indirect proof, we suppose that $x_n=\sqrt{(a^n-1)(b^n-1)}\in \mathbb{Z}$ for all positive integers $n$. Replacing $a$ by $a^2$ and $b$ by $b^2$ if necessary, we may assume that $a$ and $b$ are perfect squares, hence $\sqrt{ab}$ is an integer. At first we shall assume that $a^{\mu }\ne b^{\nu }$ for all positive integers $\mu ,\nu$. We have $$\begin{array}{c}{x}_n=(\sqrt{ab}{)}^n{\left(1-\frac{1}{a^n}\right)}^{\frac{1}{2}}{\left(1-\frac{1}{b^n}\right)}^{\frac{1}{2}}=\sum _{k,\ell \ge 0}{c}_{k,\ell }{\left(\frac{\sqrt{ab}}{a^k{b}^{\ell }}\right)}^n.\end{array}$$ Choosing $k_0$ and ${\ell }_0$ such that $a^{k_0}>\sqrt{ab},b^{{\ell }_0}>\sqrt{ab}$, we define the polynomial $$P(x)=\prod _{k=0,\ell =0}^{k_0-1,{\ell }_0-1}\left(a^k{b}^{\ell }x-\sqrt{ab}\right)=:\sum _{i=0}^{k_0\cdot {\ell }_0}{d}_i{x}^i$$ with integer coefficients $d_i$. By our assumption, the zeros $$\frac{\sqrt{ab}}{a^k{b}^{\ell }},k=0,\dots ,k_0-1,\ell =0,\dots ,{\ell }_0-1,$$ of $P$ are pairwise distinct. Furthermore, we consider the integer sequence $$\begin{array}{c}{y}_n=\sum _{i=0}^{k_0\cdot {\ell }_0}{d}_i{x}_{n+i},n=1,2,\dots \end{array}$$ By the theory of linear recursions, we obtain $$\begin{array}{c}{y}_n=\sum _{\begin{array}{c}k,\ell \ge 0\\ k\ge k_0\text{ or }\ell \ge {\ell }_0\end{array}}{e}_{k,\ell }{\left(\frac{\sqrt{ab}}{a^k{b}^{\ell }}\right)}^n,n=1,2,\dots ,\end{array}$$ with real numbers $e_{k,\ell }$. We have $$|y_n|\le \sum _{\begin{array}{c}k,\ell \ge 0\\ k\ge k_0\text{ or }\ell \ge {\ell }_0\end{array}}|e_{k,\ell }|{\left(\frac{\sqrt{ab}}{a^k{b}^{\ell }}\right)}^n=:M_n.$$ Because the series in (4) is obtained by a finite linear combination of the absolutely convergent series (1), we conclude that in particular $M_1<\infty$. Since $$\frac{\sqrt{ab}}{a^k{b}^{\ell }}\le \lambda :=\max \left\{\frac{\sqrt{ab}}{a^{k_0}},\frac{\sqrt{ab}}{b^{{\ell }_0}}\right\}\text{ for all }k,\ell \ge 0\text{ such that }k\ge k_0\text{ or }\ell \ge {\ell }_0,$$ we get the estimates $M_{n+1}\le \lambda M_n,n=1,2,\dots$. Our choice of $k_0$ and ${\ell }_0$ ensures $\lambda <1$, which implies $M_n\to 0$ and consequently $y_n\to 0$ as $n\to \infty$. It follows that $y_n=0$ for all sufficiently large $n$. So, equation (3) reduces to ${\sum }_{i=0}^{k_0\cdot {\ell }_0}{d}_i{x}_{n+i}=0$. Using the theory of linear recursions again, for sufficiently large $n$ we have $$x_n=\sum _{k=0,\ell =0}^{k_0-1,{\ell }_0-1}{f}_{k,\ell }{\left(\frac{\sqrt{ab}}{a^k{b}^{\ell }}\right)}^n$$ for certain real numbers $f_{k,\ell }$. Comparing with (2), we see that $f_{k,\ell }=c_{k,\ell }$ for all $k,\ell \ge 0$ with $k<k_0,\ell <{\ell }_0$, and $c_{k,\ell }=0$ if $k\ge k_0$ or $\ell \ge {\ell }_0$, since we assumed that $a^{\mu }\ne b^{\nu }$ for all positive integers $\mu ,\nu$. In view of (1), this means $$\begin{array}{c}(1-\alpha {)}^{\frac{1}{2}}(1-\beta {)}^{\frac{1}{2}}=\sum _{k=0,\ell =0}^{k_0-1,{\ell }_0-1}{c}_{k,\ell }\cdot {\alpha }^k{\beta }^{\ell }\end{array}$$ for all real numbers $\alpha ,\beta \in (0,1)$. We choose $k^{\ast }<k_0$ maximal such that there is some $i$ with $c_{k^{\ast },i}\ne 0$. Squaring (5) and comparing coefficients of ${\alpha }^{2k^{\ast }}{\beta }^{2i^{\ast }}$, where $i^{\ast }$ is maximal with $c_{k^{\ast },i^{\ast }}\ne 0$, we see that $k^{\ast }=0$. This means that the right hand side of (5) is independent of $\alpha$, which is clearly impossible. We are left with the case that $a^{\mu }=b^{\nu }$ for some positive integers $\mu$ and $\nu$. We may assume that $\mu$ and $\nu$ are relatively prime. Then there is some positive integer $c$ such that $a=c^{\nu }$ and $b=c^{\mu }$. Now starting with the expansion (2), i.e., $$x_n=\sum _{j\ge 0}{g}_j{\left(\frac{\sqrt{c^{\mu +\nu }}}{c^j}\right)}^n$$ for certain coefficients $g_j$, and repeating the arguments above, we see that $g_j=0$ for sufficiently large $j$, say $j>j_0$. But this means that $${\left(1-x^{\mu }\right)}^{\frac{1}{2}}{\left(1-x^{\nu }\right)}^{\frac{1}{2}}=\sum _{j=0}^{j_0}{g}_j{x}^j$$ for all real numbers $x\in (0,1)$. Squaring, we see that $$\left(1-x^{\mu }\right)\left(1-x^{\nu }\right)$$ is the square of a polynomial in $x$. In particular, all its zeros are of order at least $2$, which implies $\mu =\nu$ by looking at roots of unity. So we obtain $\mu =\nu =1$, i.e., $a=b$, a contradiction.

---

Alternative solution.

We set $a^2=A,b^2=B$, and $z_n=\sqrt{(A^n-1)(B^n-1)}$. Let us assume that $z_n$ is an integer for $n=1,2,\dots$ Without loss of generality, we may suppose that $b<a$. We determine an integer $k\ge 2$ such that $b^{k-1}\le a<b^k$, and define a sequence ${\gamma }_1,{\gamma }_2,\dots$ of rational numbers such that $$2{\gamma }_1=1\text{ and }2{\gamma }_{n+1}=\sum _{i=1}^n{\gamma }_i{\gamma }_{n-i}\text{ for }n=1,2,\dots$$ It could easily be shown that ${\gamma }_n=\frac{1\cdot 1\cdot 3\dots (2n-3)}{2\cdot 4\cdot 6\dots 2n}$, for instance by reading Vandermonde's convolution as an equation between polynomials, but we shall have no use for this fact. Using Landau's $O$-Notation in the usual way, we have $$\begin{array}{rl}& {\left\{(ab{)}^n-{\gamma }_1{\left(\frac{a}{b}\right)}^n-{\gamma }_2{\left(\frac{a}{b^3}\right)}^n-\cdots -{\gamma }_k{\left(\frac{a}{b^{2k-1}}\right)}^n+O{\left(\frac{b}{a}\right)}^n\right\}}^2\\ & =A^n{B}^n-2{\gamma }_1{A}^n-\sum _{i=2}^k\left(2{\gamma }_i-\sum _{j=1}^{i-1}{\gamma }_j{\gamma }_{i-j}\right){\left(\frac{A}{B^{i-1}}\right)}^n+O{\left(\frac{A}{B^k}\right)}^n+O\left(B^n\right)\\ & =A^n{B}^n-A^n+O\left(B^n\right)\end{array}$$ whence $$z_n=(ab{)}^n-{\gamma }_1{\left(\frac{a}{b}\right)}^n-{\gamma }_2{\left(\frac{a}{b^3}\right)}^n-\cdots -{\gamma }_k{\left(\frac{a}{b^{2k-1}}\right)}^n+O{\left(\frac{b}{a}\right)}^n.$$ Now choose rational numbers $r_1,r_2,\dots ,r_{k+1}$ such that $$(x-ab)\cdot \left(x-\frac{a}{b}\right)\dots \left(x-\frac{a}{b^{2k-1}}\right)=x^{k+1}-r_1{x}^k+\cdots \pm r_{k+1},$$ and then a natural number $M$ for which $M{r}_1,M{r}_2,\dots M{r}_{k+1}$ are integers. For known reasons, $$M\left(z_{n+k+1}-r_1{z}_{n+k}+\cdots \pm r_{k+1}{z}_n\right)=O{\left(\frac{b}{a}\right)}^n$$ for all $n\in \mathbb{N}$ and thus there is a natural number $N$ which is so large, that $$z_{n+k+1}=r_1{z}_{n+k}-r_2{z}_{n+k-1}+\cdots \mp r_{k+1}{z}_n$$ holds for all $n⩾N$. Now the theory of linear recursions reveals that there are some rational numbers ${\delta }_0,{\delta }_1,{\delta }_2,\dots ,{\delta }_k$ such that $$z_n={\delta }_0(ab{)}^n-{\delta }_1{\left(\frac{a}{b}\right)}^n-{\delta }_2{\left(\frac{a}{b^3}\right)}^n-\cdots -{\delta }_k{\left(\frac{a}{b^{2k-1}}\right)}^n$$ for sufficiently large $n$, where ${\delta }_0>0$ as $z_n>0$. As before, one obtains $$\begin{array}{rl}& A^n{B}^n-A^n-B^n+1=z_n^2\\ & ={\left\{{\delta }_0(ab{)}^n-{\delta }_1{\left(\frac{a}{b}\right)}^n-{\delta }_2{\left(\frac{a}{b^3}\right)}^n-\cdots -{\delta }_k{\left(\frac{a}{b^{2k-1}}\right)}^n\right\}}^2\\ & ={\delta }_0^2{A}^n{B}^n-2{\delta }_0{\delta }_1{A}^n-\sum _{i=2}^{i=k}\left(2{\delta }_0{\delta }_i-\sum _{j=1}^{j=i-1}{\delta }_j{\delta }_{i-j}\right){\left(\frac{A}{B^{i-1}}\right)}^n+O{\left(\frac{A}{B^k}\right)}^n.\end{array}$$ Easy asymptotic calculations yield ${\delta }_0=1,{\delta }_1=\frac{1}{2},{\delta }_i=\frac{1}{2}{\sum }_{j=1}^{j=i-1}{\delta }_j{\delta }_{i-j}$ for $i=2,3,\dots ,k-2$, and then $a=b^{k-1}$. It follows that $k>2$ and there is some $P\in \mathbb{Q}[X]$ for which $(X-1)(X^{k-1}-1)=P(X{)}^2$. But this cannot occur, for instance as $X^{k-1}-1$ has no double zeros. Thus our assumption that $z_n$ was an integer for $n=1,2,\dots$ turned out to be wrong, which solves the problem.