The sequence $a_1, a_2, \ldots, a_n$ of positive real numbers satisfies the following conditions: \begin{align*} \sum_{i=1}^n \frac{1}{a_i} \le 1 \ \ \ \ \hbox{and} \ \ \ \ a_i \le a_{i-1}+1 \end{align*}for all $i\in \lbrace 1, 2, \ldots, n \rbrace$, where $a_0$ is an integer. Prove that \begin{align*} n \le 4a_0 \cdot \sum_{i=1}^n \frac{1}{a_i} \end{align*}
Problem
Source: 2019 Polish MO Finals
Tags: algebra, inequalities, real number
09.07.2019 19:31
Note that minimum of $\sum_{i=1}^n \frac{1}{a_i}$ is achieved iff $a_i=a_{i-1}+1\mbox{ }\forall i=\overline{1,n}$, thus we can consider only this case. Then, by computing the integral $\int\limits_{a_0+1}^{a_0+n+1}\frac{1}{x}\,dx$ we obtain that $\sum\limits_{i=a_0+1}^{a_0+n}\frac{1}{i}>\ln{(a_0+n+1)}-\ln{(a_0+1)}$, thus $$ 1\ge \sum\limits_{i=a_0+1}^{a_0+n}\frac{1}{i}>\ln{(a_0+n+1)}-\ln{(a_0+1)}=\ln\left(\frac{a_0+n+1}{a_0+1}\right)\Rightarrow a_0>\frac{n+1-e}{e-1} $$Finally, using $AM-HM$, we obtain $$ 4a_0\sum\limits_{i=a_0+1}^{a_0+n}\frac1i\ge\frac{4a_0n}{a_0+(n+1)/2}\ge n\Leftrightarrow 4a_0\ge a_0+\frac{n+1}{2}\Leftrightarrow a_0\ge \frac{n+1}{6}, $$which is true for $n>4$ since $a_0>\frac{n+1-e}{e-1}$. For $n\le 4$ compute $\int\limits_{a_0}^{a_0+n}\frac{1}{x}\,dx$ to get $$ 4a_0\sum\limits_{i=a_0+1}^{a_0+n}\frac1i>4a_0\int\limits_{a_0}^{a_0+n}\frac{1}{x}\,dx=4a_0\ln\left(\frac{a_0+n}{a_0}\right)=4\ln\left(1+\frac{n}{a_0}\right)^{a_0}\ge 4\ln(1+n), $$where the last inequality follows from Bernoulli's inequality $(1+x)^h\ge 1+xh$ for $x>-1$ and $h\ge 0$. One can easily see that $4\ln(1+n)>n$ for $n\le 4$, so we are done.
12.10.2021 22:00
Since $\frac{1}{a_i}\ge \frac{1}{a_{i-1}+1}$, we may assume that $a_i=a_{i-1}+1$ for all $i=1,2,\cdots ,n$. Then, $a_i=a_0+i$ for all $i=1,2,\cdots ,n$. Hence, $\sum_{i=1}^n \frac{1}{a_i}=\sum_{i=1}^n \frac{1}{a_0+i}$. We will prove that $\sum_{i=1}^n \frac{4a_0}{a_0+i}\ge n$ by induction over $n$.
We have $\sum_{i=1}^n \frac{4a_0}{a_0+i}\ge n$ for $n=1,2$ since $a_0\ge 1$. Assume that $\sum_{i=1}^{k-1} \frac{4a_0}{a_0+i}\ge k-1$ where $k\ge 3$. Let's prove that $\sum_{i=1}^k \frac{4a_0}{a_0+i}\ge k$. See that it suffices to prove that $\frac{4a_0}{a_0+k}\ge 1\Leftrightarrow a_0\ge \frac k3$. Suppose that $a_0<\frac k3$. Then, $1\ge \sum_{i=1}^k \frac{1}{a_i}=\sum_{i=1}^k \frac{1}{a_0+i}>\sum_{i=1}^k \frac{1}{\frac k3+i}>(Lemma)>1$, contradiction. Hence, $a_0\ge \frac k3$. This completes the proof.
12.10.2021 22:45
Note that $a_i \leq a_0 + i$ for all $i \geq 1$. Thus, $\sum_{i=1}^{n} \frac{1}{a_i} \geq \sum_{i=1}^{n} \frac{1}{a_0 + i} \geq \frac{n^2}{na_0 + \frac{n(n+1)}{2}}$ by Cauchy-Schwarz. So our inequality is equivalent to $$\frac{4a_0n^2}{na_0 + \frac{n(n+1)}{2}} \geq n \iff 3a_0n \geq \frac{n(n+1)}{2} \iff a_0 \geq \frac{n+1}{6}$$Now assume that $a_0 < \frac{n+1}{6}$. Then, $a_i \leq a_0 + i < \frac{n+1}{6} + i = \frac{n + 6i + 1}{6}$. So, $\sum_{i=1}^{n} \frac{1}{a_i} > 6\sum_{i=1}^{n} \frac{1}{n+6i+1} \geq \frac{6n^2}{n^2 + n + 6\frac{n(n+1)}{2}} = \frac{6n^2}{4n^2 + 4n} > 1$ if $n \geq 3$. Thus, if $n \geq 3$, inequality is proven. If $n = 1$, then $1\geq \frac{1}{a_1} \geq \frac{1}{a_0 + 1}$ and so $4a_0 \cdot \frac{1}{a_1} \geq \frac{4a_0}{a_0 + 1} \geq 2 > 1$ since $a_0 \geq 1$. If $n = 2$, then $\frac{1}{a_1} + \frac{1}{a_2} \leq 1$ and $a_2 \leq a_1 + 1 \leq a_0 + 2$, so $4a_0(\frac{1}{a_1} + \frac{1}{a_2}) \geq 4a_0(\frac{1}{a_0 + 1} + \frac{1}{a_0 + 2}) > \frac{8a_0}{a_0 + 2} \geq \frac{8}{3} > 2$, we are done.