Two positive valued sequences {an} and {bn} satisfy: (a): a0=1≥a1, an(bn+1+bn−1)=an−1bn−1+an+1bn+1, n≥1. (b): ∑ni=1bi≤n32, n≥1. Find the general term of {an}.
Problem
Source: China TST Quiz 2006
Tags: induction, ratio, inequalities, limit, algebra unsolved, algebra
25.06.2006 13:14
shobber wrote: Two sequences {an} and {bn} satisfy: (a): a0=1≥a1, an(bn+1+bn−1)=an−1bn−1+an+1bn+1, n≥1. (b): ∑ni=1bi≤n32, n≥1. Find the general term of {an}. What about b0?
25.06.2006 19:15
shobber wrote: Two sequences {an} and {bn} satisfy: (a): a0=1≥a1, an(bn+1+bn−1)=an−1bn−1+an+1bn+1, n≥1. (b): ∑ni=1bi≤n32, n≥1. Find the general term of {an}. It is incorrect problem. Let an any strongly decrease sequence. From a) we have bn+1=bn−1(an−1−an)an−an+1. If an−1−anan−an+1≤1,b0=0,b1≤1 we have 0≤bn≤1, therefore (b) is true. General term of an not defined.
12.07.2006 09:36
shobber wrote: Two sequences {an} and {bn} satisfy: (a): a0=1≥a1, an(bn+1+bn−1)=an−1bn−1+an+1bn+1, n≥1. (b): ∑ni=1bi≤n32, n≥1. Find the general term of {an}. Actually shobber had made a mistake during the translation. The original question required the two sequences be positive, not arbitrary, and in this case, an=1 is the only solution
12.07.2006 12:18
Thanks for pointing out the mistake. I have editted my post.
07.09.2006 08:39
Time for a solution now? Claim: an=1 for all n integer. Proof by contradiction: Note ai is a decreasing sequence, since: bn−1(an−an−1)=bn+1(an+1−an) note a0>a1 and so by induction since bi are positive, it follows an>an+1. Next, in that equality, if an=an−1, then an+1)=an, and backwards so by another induction and contrapositive if an<1 for some n then a1<1. It remains to show this is impossible, ie it doesn't meet the second criteria. Consider positive sequence {c_i} with c0=1−a1, ci=ai−ai+1. note c1+c2+⋯+cn<1 for all integers n. Now it is possible to see, after finding out the horrendous formulaes for bi in terms of b0,b1 and ai with induction that: b2nb2n+1=b0b1c0c2n b2n−1b2n=b0b1c0c2n−1 therefore: b1+b2+⋯+b2n≥√(b1b2)+√(b2b3)+⋯√(b2n−1b2n). But note that we can vary bi by a linear factor and not change much, so the question actually boils down to proving that b1+b2+⋯+bnn(32) is unbounded as n tends to infinity. So ignoring the constant stuff in the last expression: √(b1b2)+√(b2b3)+⋯√(b2n−1b2n) it reduces to proving, using the previous inducted formulas, that the ratio c(1−12)+⋯+c(n−12)n(32) is unbounded. assume a counterexample exists. now we can assume that the sum c1+c2+⋯+cn tends to 1, because if it doesn't and limits to something smaller we can multiply it by a certain factor and then we will have a satisfactory sequence. Next we note the very easy inequality: (√(c1+c2+⋯+cn))(c(1−12)+⋯+c(n−12)≥n(32). I need to go now, but it's not hard to finish off from here, i'll finish posting later, basically you just use the inequality and say for arbitrarily large m that if it holds, you extend it to n as n approaches infinity and find using easy limits that the sum c1+..+cm is bounded by constant 1−C(−2), which isn't true since it tends to 1 .. i'll post the rest sometime .. anyway very nice pb.
07.06.2007 15:49
Could someone explain to me why (√c1+c2+⋯+cn)(c−121+⋯+c−12n)≥n32 implies that (c−121+⋯+c−12n)/n3/2 is unbounded? Why can't (c−121+⋯+c−12n)/n3/2→t<1? Thanks, Jack
24.09.2011 00:16
Let ci=ai−ai+1 for all i≥0, so c0≥0, S=∑i≥0ci≤1, and bn+1cn=bn−1cn−1 for all n≥1. Then ci=0⟺ci+1=0, so if cj=0 for some j≥0 then ci=0 for all i≥0 and so ai=1 for all i≥0. Otherwise, ci≠0⟹ci>0 for all i≥0, so by induction on n≥0, b2n=b0c0c2⋯c2n−2c1c3⋯c2n−1 and b2n+1=b1c1c3⋯c2n−1c2c4⋯c2n, whence by AM-GM, bn+bn+1≥2√b0b1c0cn for all n≥0. Summing up, we get 2n3/2≥b1+2b2+⋯+2bn−1+bn≥2√b0b1c0n−1∑k=11√ck,so by Hölder's inequality, n3b0b1c0∑k≥mck≥(n−1∑i=m1√ck)2(n−1∑k=mck)≥(n−m)3for n>m≥1. Taking n→∞ for fixed m yields S−∑m−1k=0ck=∑k≥mck≥b0b1c0 for all m≥1, which is impossible since lim (which is valid since S\le 1).
01.07.2018 00:46
If a_1=a_0=1 we can easily show with induction that a_i=1 for all i and that many choices for \{b_i\} satisfy condition (b), so this is a valid sequence. Now assume a_1<1. I'll show \displaystyle\sum_{i=1}^n b_i is eventually greater than cn\sqrt{n} for any constant c. Note the first condition rewrites as b_{n+1} = b_{n-1} \cdot \dfrac{a_{n-1}-a_n}{a_n-a_{n+1}}. Letting c_{n-1} = a_{n-1}-a_n this is just b_{n+1} = b_{n-1} \dfrac{c_{n-1}}{c_n}, and since c_0>0 an easy induction shows c_i>0 for all i. We also trivially have \sum_{i=1}^n c_i <1 for all n. Now let b = \min (b_0, b_1, b_2). We can easily verify that b_{2n} =b_2 \dfrac{c_2c_4...c_{2n-2}}{c_3c_5...c_{2n-1}}, b_{2n-1} = b_1\dfrac{c_1c_3...c_{2n-3}}{c_2c_4...c_{2n-2}} so by AM-GM b_{2n-1}+b_{2n} \ge 2b\sqrt{\dfrac{c_1}{c_{2n-1}}}. Similarly we can show b_{2n}+b_{2n+1} \ge 2b\sqrt{\dfrac{c_1}{c_{2n}}}. Therefore, after clearing some constant terms, it's enough to show that for any constant c, we eventually have \displaystyle\sum_{i=1}^n \dfrac{1}{\sqrt{c_i}} \ge cn\sqrt{n}. Let A_k = \displaystyle\sum_{i=1}^{2^k} \dfrac{1}{\sqrt{c_i}} and B_k = \displaystyle\sum_{i=1}^{2^k} c_i. By Jensen on the convex function f(x) = x^{-\frac{1}{2}}, we have A_{k+1} - A_k = \displaystyle\sum_{i=2^k+1}^{2^{k+1}} \dfrac{1}{\sqrt{c_i}} \ge \dfrac{2^k}{\sqrt{\frac{B_{k+1}-B_k}{2^k}}} = \dfrac{2^k\sqrt{2}^k}{\sqrt{B_{k+1}-B_k}}. Since \displaystyle\sum_{k\ge 0} (B_{k+1}-B_k) \le 1 and each of the terms in parentheses is positive, there is some k>0 for which B_{k+1}-B_k \le \dfrac{1}{8c^2}, and for this choice of n=2^{k+1} we have \displaystyle\sum_{i=1}^n \dfrac{1}{\sqrt{c_i}} > A_{k+1}-A_k = \dfrac{2^k\sqrt{2}^k}{\sqrt{B_{k+1}-B_k}} \ge 2^{k+1}\sqrt{2}^{k+1} c= cn\sqrt{n}, as desired. Hence the only valid sequence is a_i\equiv 1 for all i.