Problem A. 652. (October 2015)

A. 652. Prove that there exists a real number $\displaystyle C>1$ with the following property: whenever $\displaystyle n>1$ and $\displaystyle a_0<a_1<\cdots<a_n$ are positive integers such that $\displaystyle \frac1{a_0},\frac1{a_1},\ldots,\frac1{a_n}$ form an arithmetic progression, then $\displaystyle a_0> C^n$.

CIIM 2015, Mexico

(5 pont)

Deadline expired on November 10, 2015.

Solution. Assume that $\displaystyle a_0<a_1<\ldots<a_n$ are positive integers such that $\displaystyle \frac1{a_0},\frac1{a_1},\ldots,\frac1{a_n}$ form an arithmetic progression. For convenience, let $\displaystyle x_i=\tfrac1{a_i}$ and $\displaystyle \Delta=x_0-x_1=x_1-x_2=\ldots=x_{n-1}-x_n$.

First we prove by induction on $\displaystyle k$ that

For $\displaystyle k=0$ this is trivial. The induction step is done by applying the induction hypothesis to the sequences $\displaystyle (a_0,\ldots,a_k)$ and $\displaystyle (a_1,\ldots,a_{k+1})$:

$\displaystyle \sum_{\ell=0}^{k+1}(-1)^{k+1-\ell}\binom{k+1}{\ell} a_\ell = \left(\sum_{\ell=0}^{k}(-1)^{k-\ell}\binom{k}{\ell} a_\ell\right) - \left(\sum_{\ell=0}^{k}(-1)^{k-\ell}\binom{k}{\ell} a_{\ell+1}\right) =$

$\displaystyle = \frac{k! \cdot \Delta^k}{x_0x_1\cdots x_k} - \frac{k! \cdot \Delta^k}{x_1x_2\cdots x_{k+1}} = \frac{k! \cdot \Delta^k \cdot (x_0-x_{k+1})}{x_0x_1\cdots x_{k+1}} = \frac{(k+1)! \cdot \Delta^{k+1}}{x_0x_1\cdots x_{k+1}}.$

Finally, notice that the LHS is an integer, so $\displaystyle LHS>0$ is equivalent with $\displaystyle LHS\ge1$.

Next we prove that

Consider

$\displaystyle \Sigma = \sum_{k=0}^m \binom{m}{k} \left( \sum_{\ell=0}^k(-1)^{k-\ell}\binom{k}{\ell} a_\ell \right).$

The first term (when $\displaystyle k=0$) is $\displaystyle a_0$. In the other terms apply (1):

On the other hand, swapping the sums,

$\displaystyle \Sigma = \sum_{\ell=0}^m a_\ell \left( \sum_{k=\ell}^m (-1)^{k-\ell} \binom{m}{k} \binom{k}{\ell} \right) = \sum_{\ell=0}^m a_\ell \binom{m}{\ell} \left( \sum_{k=\ell}^m (-1)^{k-\ell} \binom{m-\ell}{k-\ell} \right).$

For $\displaystyle \ell<m$ the last sum is $\displaystyle (1-1)^{m-\ell}=0$ by the binomial theorem. For $\displaystyle \ell=m$ this sum is $\displaystyle 1$. Therefore, $\displaystyle \Sigma=a_m$ and (3) finishes the proof of (2).

In order to prove the problem statement, we set $\displaystyle m=n-1$ in (2) and get $\displaystyle a_{n-1}\ge a_0+2^{n-1}-1$. From

$\displaystyle x_{n-1}>x_{n-1}-x_n = \frac{x_0-x_{n-1}}{n-1}$

we get $\displaystyle n x_{n-1}>x_0$, i.e. $\displaystyle na_0>a_{n-1}$. Then

$\displaystyle n a_0 \ge a_{n-1}+1 \ge a_0+2^{n-1}$

For $\displaystyle n=2$, $\displaystyle n=3$, the bound (4) provides $\displaystyle a_0\ge2$; if $\displaystyle n=4$ then $\displaystyle a_0\ge 3$.

If $\displaystyle n\ge5$ then $\displaystyle 2(n-1) = \binom{n}2 \frac4{n} \le \binom{n}2 \left(\frac9{10}\right)^2 < \left(1+\frac9{10}\right)^n$, so

$\displaystyle a_0 \ge \frac{2^{n-1}}{n-1} > \left(\frac{20}{19}\right)^n.$

Hence,

$\displaystyle C = \min\left(\sqrt[2]{2},\sqrt[3]{2},\sqrt[4]{3},\frac{20}{19}\right) = \frac{20}{19}$

is a suitable choice.

Remark. For every $\displaystyle C<2$, the relation (4) proves the statement for sufficiently large $\displaystyle n$.

On the other hand, the sequence $\displaystyle a_i=\dfrac{\mathrm{lcm}(1,2,\ldots,n+1)}{n+1-i}$ ($\displaystyle i=0,1,\ldots,n$) obviously satisfies the conditions. It is equivalent with the prime number theorem that $\displaystyle \log \mathrm{lcm}(1,2,\ldots,n)\sim n$. This shows that the statement is false for $\displaystyle C>e$.

Statistics:

8 students sent a solution.
5 points:	Baran Zsuzsanna, Williams Kada.
4 points:	Lajkó Kálmán.
3 points:	1 student.
2 points:	2 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, October 2015