Let a1,a2,a3,… be a sequence of positive real numbers satisfying ∑nj=1aj≥√n for all n≥1. Prove that, for all n≥1, n∑j=1a2j>14(1+12+⋯+1n).
Problem
Source: USAMO 1994
Tags: function, inequalities unsolved, inequalities
26.10.2005 17:01
Karamata again... Define a sequence (bn)n∈N by bk=√k−√k−1 for every k. Since bk=√k−√k−1=(√k+√k−1)(√k−√k−1)√k+√k−1 =k−(k−1)√k+√k−1=1√k+√k−1, it is clear that this sequence (bn) is decreasing (since, when k increases, both √k and √k−1 increase, so that √k+√k−1 increases, and thus bk=1√k+√k−1 decreases). Hence, for every index k with 1≤k≤n, the numbers b1, b2, ..., bk are the k greatest numbers among the n numbers b1, b2, ..., bn. Hence, the sum ∑kj=1bj is the sum of the k greatest numbers among the n numbers b1, b2, ..., bn. Since ∑kj=1bj=∑kj=1(√j−√j−1)=√k−√0=√k, we thus can state: The sum of the k greatest numbers among the n numbers b1, b2, ..., bn is √k. For the numbers a1, a2, ..., an, we don't know how they are arranged, and we can only say that the sum of the k greatest numbers among the n numbers a1, a2, ..., an is greater or equal to the sum ∑kj=1aj (in fact, this is obvious: the sum of the k greatest numbers is greater or equal to the sum of just some k numbers). So altogether, for every index k with 1≤k≤n, we have: - The sum of the k greatest numbers among the n numbers a1, a2, ..., an is greater or equal to the sum ∑kj=1aj. - By the condition of the problem, ∑kj=1aj≥√k. - The number √k is the sum of the k greatest numbers among the n numbers b1, b2, ..., bn. Combining this, we see that for every index k with 1≤k≤n, the sum of the k greatest numbers among the n numbers a1, a2, ..., an is greater or equal to the sum of the k greatest numbers among the n numbers b1, b2, ..., bn. Now, we have the following fact: Karamata theorem for "pseudo-majorizing" number arrays: Let a1, a2, ..., an, b1, b2, ..., bn be 2n numbers from an interval I such that for every index k with 1≤k≤n, the sum of the k greatest numbers among the n numbers a1, a2, ..., an is greater or equal to the sum of the k greatest numbers among the n numbers b1, b2, ..., bn (but we don't require equality for k = n, i. e. we don't necessarily have a1+a2+...+an=b1+b2+...+bn, but we only need a1+a2+...+an≥b1+b2+...+bn). Also, let f be a function which is convex and monotonically increasing on the interval I. Then, ∑nj=1f(aj)≥∑nj=1f(bj). This theorem can be easily deduced from the actual Karamata theorem. Now, applying this theorem to our numbers a1, a2, ..., an, b1, b2, ..., bn, with the interval I=R+ and the function f(t)=t2 which is convex and monotonically increasing on R+, we get ∑nj=1a2j≥∑nj=1b2j=∑nj=1(1√j+√j−1)2>∑nj=1(1√j+√j)2=∑nj=1(12√j)2 =∑nj=114j=14∑nj=11j, and the problem is solved. EDIT: I just saw the same problem in a slightly different version being posted at http://www.artofproblemsolving.com/Forum/viewtopic.php?t=21262 . Darij
26.10.2005 17:08
Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality.
26.10.2005 19:48
cezar lupu wrote: Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality. Both names are okay. But even if the name is wrong, who cares?
12.09.2018 19:37
Let us assume that a1≥a2≥a3.....≥an .Also let fn(x):R+−>R+ such that fn(x)=1√xn Let try to prove 2∑ni=1a2i ≥∑i=ni=1aif(x)i Now using Abel's inequality ∑i=ni=1ai(2ai−fi(x))= (a_1 - a_2 )( 2a_1 - f_1(x) ) + (a_2 - a_3)(2a_1 + 2a_2 - f1(x)−f2(x))+.......+(an−1 −an)(2∑n−1i=1ai− ∑n−1i=1fi(x))+xn(2∑i=ni=1ai−∑ni=1fi(x)) Need to prove that 2∑ki=1ai≥∑ki=1fi(x) This means we need to show ∑ki=11√x ≤2√k That's very easy to show.
12.09.2018 19:38
opptoinfinity wrote: Let us assume that a1≥a2≥a3.....≥an .Also let fn(x):R+−>R+ such that fn(x)=1√xn Let try to prove 2∑ni=1a2i ≥∑i=ni=1aif(x)i Now using Abel's inequality ∑i=ni=1ai(2ai−fi(x))= (a_1 - a_2 )( 2a_1 - f_1(x) ) + (a_2 - a_3)(2a_1 + 2a_2 - f1(x)−f2(x))+.......+(an−1 −an)(2∑n−1i=1ai− . ∑n−1i=1fi(x))+xn(2∑i=ni=1ai−∑ni=1fi(x)) Need to prove that 2∑ki=1ai≥∑ki=1fi(x) This means we need to show ∑ki=11√x≤2√k That's very easy to show.
09.04.2019 01:03
24.01.2022 14:10
we proceed by Abel : denonte bk=1√k note that our inequation to prove becomes : n∑i=14(xi)2≥n∑i=1(bi)2then we get that n∑i=14(xi)2−(bi)2≥0and then we get n∑i=1(2xi+bi)(2xi−bi)≥0but we have ∑ni=1(2xi+bi)≥0 then we only need to prove that n∑i=1(2xi−bi)≥0note that ∑ni=1(2xi−bi)=∑ni=1(bi)(2xibi−1)=∑ni=1(Xi)(bi−bi+1) and Xi=∑ij=12xibi−i .... note that bi>bi+1 thus we need to prove that ∑ni=1Xi≥0 now bby AM GM we have ∑ij=1xibi≥i(x1∗x2....xIb1∗b2∗b3...bI)1i which makes ∑ni=1Xi≥0 finally we have n∑i=1(2xi−bi)=n∑i=1(bi)(2xibi−1)=n∑i=1(Xi)(bi−bi+1)≥0
24.01.2022 16:56
MithsApprentice wrote: Let a1,a2,a3,… be a sequence of positive real numbers satisfying ∑nj=1aj≥√n for all n≥1. Prove that, for all n≥1, n∑j=1a2j>14(1+12+⋯+1n). Using Cauchy-Bunyakovsky-Schwarz inequality, we have n∑j=1a2jn∑j=114j≥(n∑j=1aj2√j)2.Thus, it suffices to prove that n∑j=1aj2√j>n∑j=114j. Also, using summation by parts, we have n∑j=1aj2√j=n∑j=1(12√j−12√j+1)j∑i=1ai+12√n+1n∑i=1ai≥n∑j=1(12√j−12√j+1)√j+12√n+1⋅√n=n2+√n2√n+1−12n∑j=1√j√j+1.It suffices to prove that n2+√n2√n+1−12n∑j=1√j√j+1>n∑j=114jwhich can be proved by Mathematical Induction. Remark: There is some similarity between this problem and the following: Problem 1: Let a1,a2,⋯>0 with a1+a2+⋯+an≤n2 for each n∈N>0. Prove that, for each n∈N>0, 1/a1+1/a2+⋯+1/an≥14log2n.https://artofproblemsolving.com/community/c6h2726086p23746406 My proof for Problem 1 (in the link above):
25.01.2022 04:09
Cezar Lupu wrote: Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality. Yes, according to https://artofproblemsolving.com/community/c6h14975, Karamata published later than Hardy,Littlewood and Polya, and in any case majorization was independently discovered many times before and after all these publications. There is a history in Marshall and Olkin's book on majorization. In the Anglo-Saxon countries it is called "majorization inequality" or "Hardy-Littlewood-Polya" majorization inequality". The similar thing: 1) Cauchy inequality: before I called "Cauchy-Schwarz", now I call "Cauchy-Bunyakovsky-Schwarz"
2) Holder inequality: In a book, I saw: 【In 1998, L. Maligranda said it should be called Roger-Holder inequality since Roger discovered it one year earlier than Holder.】