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
\(\displaystyle \sum_{\ell=0}^k(-1)^{k-\ell}\binom{k}{\ell} a_\ell = \frac{k! \cdot \Delta^k}{x_0x_1\cdots x_k} \ge1. \) | (1) |
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
\(\displaystyle a_m\ge a_0+2^m-1 \quad\text{for}\quad 1\le m\le n. \) | (2) |
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):
\(\displaystyle \Sigma \ge a_0 + \sum_{k=1}^m \binom{m}{k}\cdot 1 = a_0+2^m-1. \) | (3) |
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} \)
\(\displaystyle a_0 \ge \frac{2^{n-1}}{n-1}. \) | (4) |
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