Two positive valued sequences $\{ a_{n}\}$ and $\{ b_{n}\}$ satisfy: (a): $a_{0}=1 \geq a_{1}$, $a_{n}(b_{n+1}+b_{n-1})=a_{n-1}b_{n-1}+a_{n+1}b_{n+1}$, $n \geq 1$. (b): $\sum_{i=1}^{n}b_{i}\leq n^{\frac{3}{2}}$, $n \geq 1$. Find the general term of $\{ a_{n}\}$.
Problem
Source: China TST Quiz 2006
Tags: induction, ratio, inequalities, limit, algebra unsolved, algebra
25.06.2006 13:14
shobber wrote: Two sequences $\{ a_n \}$ and $\{ b_n \}$ satisfy: (a): $a_0=1 \geq a_1$, $a_n(b_{n+1}+b_{n-1})=a_{n-1}b_{n-1}+a_{n+1}b_{n+1}$, $n \geq 1$. (b): $\sum_{i=1}^{n} b_i \leq n^{\frac{3}{2}}$, $n \geq 1$. Find the general term of $\{ a_n \}$. What about $b_0$?
25.06.2006 19:15
shobber wrote: Two sequences $\{ a_n \}$ and $\{ b_n \}$ satisfy: (a): $a_0=1 \geq a_1$, $a_n(b_{n+1}+b_{n-1})=a_{n-1}b_{n-1}+a_{n+1}b_{n+1}$, $n \geq 1$. (b): $\sum_{i=1}^{n} b_i \leq n^{\frac{3}{2}}$, $n \geq 1$. Find the general term of $\{ a_n \}$. It is incorrect problem. Let $a_n$ any strongly decrease sequence. From a) we have $b_{n+1}=\frac{b_{n-1}(a_{n-1}-a_n)}{a_n-a_{n+1}}$. If $\frac{a_{n-1}-a_n}{a_n-a_{n+1}}\le 1,b_0=0,b_1\le 1$ we have $0\le b_n\le 1$, therefore (b) is true. General term of $a_n$ not defined.
12.07.2006 09:36
shobber wrote: Two sequences $\{ a_{n}\}$ and $\{ b_{n}\}$ satisfy: (a): $a_{0}=1 \geq a_{1}$, $a_{n}(b_{n+1}+b_{n-1})=a_{n-1}b_{n-1}+a_{n+1}b_{n+1}$, $n \geq 1$. (b): $\sum_{i=1}^{n}b_{i}\leq n^{\frac{3}{2}}$, $n \geq 1$. Find the general term of $\{ a_{n}\}$. Actually shobber had made a mistake during the translation. The original question required the two sequences be positive, not arbitrary, and in this case, $a_{n}= 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: $a_{n}=1$ for all $n$ integer. Proof by contradiction: Note ${a_{i}}$ is a decreasing sequence, since: $b_{n-1}(a_{n}-a_{n-1}) = b_{n+1}(a_{n+1}-a_{n})$ note $a_{0}> a_{1}$ and so by induction since $b_{i}$ are positive, it follows $a_{n}>a_{n+1}$. Next, in that equality, if $a_{n}=a_{n-1}$, then $a_{n+1) = a_{n}}$, and backwards so by another induction and contrapositive if $a_{n}<1$ for some $n$ then $a_{1}<1$. It remains to show this is impossible, ie it doesn't meet the second criteria. Consider positive sequence {c_i} with $c_{0}= 1-a_{1}$, $c_{i}= a_{i}-a_{i+1}$. note $c_{1}+c_{2}+\cdots+c_{n}< 1$ for all integers $n$. Now it is possible to see, after finding out the horrendous formulaes for $b_{i}$ in terms of $b_{0}, b_{1}$ and $a_{i}$ with induction that: $b_{2n}b_{2n+1}= b_{0}b_{1}\frac{c_{0}}{c_{2n}}$ $b_{2n-1}b_{2n}= b_{0}b_{1}\frac{c_{0}}{c_{2n-1}}$ therefore: $b_{1}+b_{2}+\cdots+b_{2n}\geq \sqrt (b_{1}b_{2})+\sqrt (b_{2}b_{3})+\cdots \sqrt (b_{2n-1}b_{2n})$. But note that we can vary $b_{i}$ by a linear factor and not change much, so the question actually boils down to proving that $\frac{b_{1}+b_{2}+\cdots+b_{n}}{n^{(}\frac{3}{2})}$ is unbounded as $n$ tends to infinity. So ignoring the constant stuff in the last expression: $\sqrt (b_{1}b_{2})+\sqrt (b_{2}b_{3})+\cdots \sqrt (b_{2n-1}b_{2n})$ it reduces to proving, using the previous inducted formulas, that the ratio $\frac{c_{1}^{(}\frac{-1}{2})+\cdots+c_{n}^{(}\frac{-1}{2})}{n^{(}\frac{3}{2})}$ is unbounded. assume a counterexample exists. now we can assume that the sum $c_{1}+c_{2}+\cdots+c_{n}$ 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: $(\sqrt(c_{1}+c_{2}+\cdots+c_{n}))(c_{1}^{(}\frac{-1}{2})+\cdots+c_{n}^{(}\frac{-1}{2}) \geq n^{(}\frac{3}{2})$. 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 $c_{1}+..+c_{m}$ 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 $(\sqrt{c_{1}+c_{2}+\cdots+c_{n}})(c_{1}^{-\frac{1}{2}}+\cdots+c_{n}^{-\frac{1}{2}}) \geq n^{\frac{3}{2}}$ implies that $(c_{1}^{-\frac{1}{2}}+\cdots+c_{n}^{-\frac{1}{2}})/n^{3/2}$ is unbounded? Why can't $(c_{1}^{-\frac{1}{2}}+\cdots+c_{n}^{-\frac{1}{2}})/n^{3/2}\rightarrow t<1$? Thanks, Jack
24.09.2011 00:16
Let $c_i=a_i-a_{i+1}$ for all $i\ge0$, so $c_0\ge 0$, $S=\sum_{i\ge 0} c_i \le 1$, and $b_{n+1}c_n = b_{n-1}c_{n-1}$ for all $n\ge1$. Then $c_i=0\Longleftrightarrow c_{i+1}=0$, so if $c_j=0$ for some $j\ge0$ then $c_i=0$ for all $i\ge0$ and so $a_i=1$ for all $i\ge0$. Otherwise, $c_i\ne0\implies c_i>0$ for all $i\ge0$, so by induction on $n\ge0$, $b_{2n}=\frac{b_0c_0c_2\cdots c_{2n-2}}{c_1c_3\cdots c_{2n-1}}$ and $b_{2n+1}=\frac{b_1c_1c_3\cdots c_{2n-1}}{c_2c_4\cdots c_{2n}}$, whence by AM-GM, $b_n+b_{n+1}\ge 2\sqrt{\frac{b_0b_1c_0}{c_n}}$ for all $n\ge0$. Summing up, we get \[2n^{3/2}\ge b_1+2b_2+\cdots+2b_{n-1}+b_n\ge 2\sqrt{b_0b_1c_0}\sum_{k=1}^{n-1}\frac{1}{\sqrt{c_k}},\]so by Hölder's inequality, \[\frac{n^3}{b_0b_1c_0}\sum_{k\ge m}c_k \ge \left(\sum_{i=m}^{n-1}\frac{1}{\sqrt{c_k}}\right)^2\left(\sum_{k=m}^{n-1}c_k\right) \ge (n-m)^3\]for $n>m\ge1$. Taking $n\to\infty$ for fixed $m$ yields $S-\sum_{k=0}^{m-1}c_k = \sum_{k\ge m}c_k\ge b_0b_1c_0$ for all $m\ge1$, which is impossible since $\lim_{m\to\infty}S-\sum_{k=0}^{m-1}c_k = S-S=0$ (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$.