Let a1,a2,… be an infinite sequence of positive real numbers satisfying
a1+a2+⋯+a2n−1=an2
for all positive integers n. Prove that an≥2n−1 for all positive integers n.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Ilya I. Bogdanov, MIPT, Moscow and Aleksandr Kuznetsov, SPbU, Saint Petersburg)
Solution 1. The condition applied to n=1 gives a1=1, so the desired inequality holds for n=1.
Denote δn=an+1−an. Say that an index i is regular if ai+1≥2i+1; otherwise i is irregular. Our aim is to prove that all indices are regular.
Say that our sequence is μ-good if δi≥μ for all irregular indices i. We will show that our sequence is μ-good for all μ<2. This yields the desired inequality; indeed, otherwise, choosing the minimum irregular index n, we get an+1−an<(2n+1)−(2n−1)=2, so the sequence would not be μ-good for some μ<2.
Notice that an+12−an2=a2n+a2n+1>0, so an+1>an for all n, and hence the sequence is 0-good. Now the desired statement follows from the Claim below.
Claim. If our sequence (an) is μ-good for some 0≤μ<2, then it is also ν-good for ν=2μ+1.
Proof. Consider any irregular index n. Notice that ak−an+1≥(k−n−1)μ for every k>n+1; indeed, if all indices n+1,n+2,…,k−1 are irregular, then this follows from (an) being μ-good. Otherwise, let i be the maximum regular index not exceeding k−1. Then
This inequality easily yields δn>1, so in particular an+1>2. Then the function f(x)=x(2an+1−x) increases on x∈[0,2], and in order to prove δn≥ν it suffices to show that f(ν)≤2an+1+(2n−1)μ. This inequality rewrites as
μan+1−(2μ+1)2≤(2n−1)μ⟺μ(an+1−2n−1)≤(2μ−1)2.
This last inequality holds, since the left hand part is negative, while the right hand part is positive.
Solution 2. First, let us prove that the required inequality holds asymptotically, namely
Lemma.n→∞liminf2n−1an≥1
Proof. Let A denote this limit inferior. Clearly, the sequence is monotonically increasing. Then an2=a1+a2+⋯+a2n−1≥nan, hence A≥21>0.
Let ε>0. We know that an≥(A−ε)(2n−1) for all sufficiently large n. Then, from the inequality
we obtain A2≥A−ε. Letting ε tend to zero, we get A≥1.
Let us make the substitution bn=an−(2n−1). The recurrence relation takes the form
bn(bn+2(2n−1))=b1+…+b2n−1,
and the lemma implies that n→∞liminf2n−1bn≥0. Consider B=ninf2n−1bn. If B<0, then the infimum is attained at some k∈N, i.e. bk=B(2k−1) (otherwise we get a contradiction with the lemma). Then
This yields B<−1. On the other hand, an>0 implies B>−1 and we get a contradiction.
Solution 2 (by Dan Carmon). Begin with observing a1=a12, so a1=1 from positivity. It follows that an2=∑i=12n−1ai≥a1=1 so an≥1=(2n−1)0 for every n. Applying the same technique again gives an2=∑i=12n−1ai≥2n−1 so an≥2n−1=(2n−1)1/2. Applying this technique again and again, we will prove the following claim by induction on m:
Claim. Let m≥0, and set cm=1−2−m. Then there is a constant Cm>0 such that an≥Cm(2n−1)cm for all n≥1.
Moreover, we will get a recurrence relation for Cm, and show that limm→∞Cm=1. It would follow that an≥limm→∞Cm(2n−1)cm=2n−1, as we are asked to show.
Proof. We have already established the m=0,1 (c0=0, c1=1/2) with C0=C1=1. Let m≥1 and suppose an≥Cm(2n−1)cm for every n. Write c=cm and C=Cm for brevity. Since c<1, the function xc is concave, and therefore have xc≥21∫x−1x+1tcdt. Thus
Recall c=cm=1−2−m hence 21+c=cm+1. Taking the square root of the above inequality yields
an≥1−2−m−12−2−mCm⋅(2n−1)cm+1(1)
Which completes the inductions step for Cm+1=BmCm, where Bm=1−2−m−12−2−m.
Observe that Bm→1 as m→∞ (since 2−m→0), and the sequence Cm is obtained by repeatedly averaging (geometrically) the previous term with the terms of Bm. It is well known (a standard exercise in calculus 1) that this implies Cm also converges and to the same limit as Bm, as we claimed. This can be shown directly by limits calculus; another method is to apply Cesaro’s theorem on geometric means to the sequence Dk defined by D1=C1, Dk=B⌈log2(k)⌉ (i.e., the first elements are C1,B1,B2,B2,B3,B3,B3,B3,B4,…), which clearly has the same limit as Bm, and each Cm is just the geometric mean of the first 2m−1 elements of Dk.
Transcribed from the official solutions, pages 5–7. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.