Let $a_1, a_2, \dots$ be a sequence of real numbers satisfying $a_{i+j} \leq a_i+a_j$ for all $i,j=1,2,\dots$. Prove that \[ a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n} \geq a_n \] for each positive integer $n$.
Problem
Source: APMO 1999
Tags: logarithms, inequalities, inequalities unsolved, induction
fuzzylogic
18.03.2006 08:46
The following is China MO 1993 Problem 6 (See CMO 1993) Quote: Let $f$ be a function from the positive real numbers to the positive real numbers such that $f(xy)\leq f(x)f(y)$ for any positive real numbers $x$ and $y$. Prove that for any positive real number $x$ and all positive integers $n$, $f(x^n)\leq f(x)f(x^2)^{\frac{1}{2}}\cdots f(x^n)^{\frac{1}{n}}$. If we let $a_i = \ln{f(x^i)}$, then $a_{i+j} \leq a_i+a_j$, then the CMO problems immediately follows from the above APMO problem.
shobber
18.03.2006 09:03
I did not know the relation between these two problems because it was not me who translated CMO 1993......
jgnr
28.11.2008 15:31
We will prove this by induction. Note that the inequality holds for $ n=1$. Assume that the inequality holds for $ n=1,2,\ldots,k$, that is,
\[ a_1\ge a_1, \\ a_1+\frac{a_2}2\ge a_2, \\ a_1+\frac{a_2}2+\frac{a_3}3\ge a_3, \\ \vdots \\ a_1+\frac{a_2}3+\frac{a_3}3+\cdots+\frac{a_k}k\ge a_k.
\]
Sum them up:
\[ ka_1+(k-1)\frac{a_2}2a_2+\cdots+\frac{a_k}{k}\ge a_1+a_2+\cdots+a_k.
\]Add $ a_1+\ldots+a_k$ to both sides:
\[ (k+1)\left(a_1+\frac{a_2}2+\cdots+\frac{a_k}k\right)\ge (a_1+a_k)+(a_2+a_{k-1})+\cdots+(a_k+a_1)\ge ka_{k+1}.
\]
Divide both sides by $ k+1$:
\[ a_1+\frac{a_2}2+\cdots+\frac{a_k}k\ge\frac{ka_{k+1}}{k+1},
\] i.e.
\[ a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n} \geq a_n.
\]
Tintarn
18.09.2016 20:16
I just read in Titu Andreescu's book "104 Number Theory Problems" where he gave another, combinatorial solution to this problem (ascribed to Andreas Kaseorg) and I felt that this proof is too beautiful to not mention it here:
We can extend the condition by induction to $a_{i_1+i_2+\dotsc+i_k} \le a_{i_1}+a_{i_2}+\dotsc+a_{i_k}$. We apply a combinatorial argument.
For any permutation $\pi$ in $S_n$, define $f(\pi,k)$ to be the number of $k$-cycles in $\pi$. Clearly,
\[1 \cdot f(\pi,1)+2 \cdot f(\pi,2)+\dotsc+n \cdot f(\pi,n)=n\]Note also that $\sum_{\pi \in S_n} f(\pi,k)$ is the total number of $k$-cycles in all permutations of $n$ elements, which is $\binom{n}{k} (k-1)!(n-k)!=\frac{n!}{k}$.
Therefore, we have
\begin{align*}
a_1+\frac{a_2}{2}+\dotsc+\frac{a_n}{n}&=\frac{1}{n!} \sum_{\pi \in S_n} \left(f(\pi,1)a_1+f(\pi,2)a_2+\dotsc+f(\pi,n)a_n\right)\\
&\ge \frac{1}{n!} \sum_{\pi \in S_n} a_{1\cdot f(\pi,1)+2 \cdot f(\pi,2)+\dotsc+n \cdot f(\pi,n)}\\
&=\frac{1}{n!} \sum_{\pi \in S_n} a_n=a_n
\end{align*}
oty
18.09.2016 20:22
Quote: Let $f$ be a function from the positive real numbers to the positive real numbers such that $f(xy)\leq f(x)f(y)$ for any positive real numbers $x$ and $y$. Prove that for any positive real number $x$ and all positive integers $n$, $f(x^n)\leq f(x)f(x^2)^{\frac{1}{2}}\cdots f(x^n)^{\frac{1}{n}}$. have you a solution to this beautifull problem ? thanks
Tintarn
18.09.2016 20:25
oty wrote: have you a solution to this beautifull problem ? thanks Well, as noted above by fuzzylogic, the CMO problem follows immediately from the APMO problem.
oty
18.09.2016 21:21
Sorry I didn't notice his post , thank you a lot Dear Tintarn
WolfusA
18.06.2018 13:07
@post#2 You showed, that there exists a sequence $a_i$ satisfying assumptions, that also satisfies thesis. But that's no proof, that every sequence $a_i$ satisfying condition $a_{i+j} \leq a_i+a_j$ gives $a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n} \geq a_n $. Your proof is incomplete then.
Tintarn
18.06.2018 18:50
WolfusA wrote: Your proof is incomplete then. Sure. Read it properly. It's not even attempting to be a proof of the APMO problem. It is just to show how the CMO problem follows from the APMO problem. And that is perfectly correct.
gghx
08.03.2020 03:59
jgnr wrote:
Divide both sides by $ k+1$:
\[ a_1+\frac{a_2}2+\cdots+\frac{a_k}k\ge\frac{ka_{k+1}}{k+1},
\]i.e.
\[ a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n} \geq a_n.
\]
Im sorry, how does this work?
rocketscience
08.03.2020 04:09
Tintarn wrote: I just read in Titu Andreescu's book "104 Number Theory Problems" where he gave another, combinatorial solution to this problem (ascribed to Andreas Kaseorg) and I felt that this proof is too beautiful to not mention it here:
We can extend the condition by induction to $a_{i_1+i_2+\dotsc+i_k} \le a_{i_1}+a_{i_2}+\dotsc+a_{i_k}$. We apply a combinatorial argument.
For any permutation $\pi$ in $S_n$, define $f(\pi,k)$ to be the number of $k$-cycles in $\pi$. Clearly,
\[1 \cdot f(\pi,1)+2 \cdot f(\pi,2)+\dotsc+n \cdot f(\pi,n)=n\]Note also that $\sum_{\pi \in S_n} f(\pi,k)$ is the total number of $k$-cycles in all permutations of $n$ elements, which is $\binom{n}{k} (k-1)!(n-k)!=\frac{n!}{k}$.
Therefore, we have
\begin{align*}
a_1+\frac{a_2}{2}+\dotsc+\frac{a_n}{n}&=\frac{1}{n!} \sum_{\pi \in S_n} \left(f(\pi,1)a_1+f(\pi,2)a_2+\dotsc+f(\pi,n)a_n\right)\\
&\ge \frac{1}{n!} \sum_{\pi \in S_n} a_{1\cdot f(\pi,1)+2 \cdot f(\pi,2)+\dotsc+n \cdot f(\pi,n)}\\
&=\frac{1}{n!} \sum_{\pi \in S_n} a_n=a_n
\end{align*}
Very nice. I just wonder, why has Titu written a combinatorial solution to an algebra problem in his number theory book?
DrYouKnowWho
10.01.2022 09:16
Inductively, one can get \[a_k\geq \frac{ka_n}{n}\]Hence the conclusion easily follows.
Tintarn
10.01.2022 12:27
DrYouKnowWho wrote: Inductively, one can get \[a_k\geq \frac{ka_n}{n}\]Hence the conclusion easily follows. Unfortunately just wrong. Consider the sequence $(1,0,1,0,0,\dots)$ with $k=2, n=3$ as a direct counter-example. As a general hint, it often helps to read previous solutions to a problem to judge its difficulty before claiming it to be "easy".