Maths Olympiad Prep

Library / /9 of 14

Algebra Difficulty 8.3 Shortlist Prove it Estonia

A sequence of positive real numbers a1,a2,a3,a_1, a_2, a_3, \dots satisfies an=an1+an2a_n = a_{n-1} + a_{n-2} for all n3n \ge 3. A sequence b1,b2,b3,b_1, b_2, b_3, \dots is defined by equations b1=a1b_1 = a_1, bn=an+(b1+b2++bn1)b_n = a_n + (b_1 + b_2 + \dots + b_{n-1}) for even n>1n > 1, bn=an+(b2+b4++bn1)b_n = a_n + (b_2 + b_4 + \dots + b_{n-1}) for odd n>1n > 1. Prove that if n3n \ge 3, then 13<bnnan<1\frac{1}{3} < \frac{b_n}{n \cdot a_n} < 1.

Solution

The definition of sequence (bn)(b_n) indicates that bnbn2=anan2+bn1b_n - b_{n-2} = a_n - a_{n-2} + b_{n-1} for all n3n \ge 3. Therefore bnbn2=an1+bn1b_n - b_{n-2} = a_{n-1} + b_{n-1}, i.e., bn=an1+bn1+bn2b_n = a_{n-1} + b_{n-1} + b_{n-2}.

Notice that the left-hand inequality 13<bnnan\frac{1}{3} < \frac{b_n}{n \cdot a_n} holds for n=2n=2 and n=3n=3 as b22a2=a2+b12a2=a1+a22a2>a22a2=12>13\frac{b_2}{2a_2} = \frac{a_2+b_1}{2a_2} = \frac{a_1+a_2}{2a_2} > \frac{a_2}{2a_2} = \frac{1}{2} > \frac{1}{3} and b33a3=a3+b23a3=2(a1+a2)3(a1+a2)=23>13\frac{b_3}{3a_3} = \frac{a_3+b_2}{3a_3} = \frac{2(a_1+a_2)}{3(a_1+a_2)} = \frac{2}{3} > \frac{1}{3}.

Now assume that n4n \ge 4 and that the statement is true for n1n-1 and n2n-2. Then bn=an1+bn1+bn2>an1+13(n1)an1+13(n2)an2=13n(an1+an2)+23(an1an2)>13nanb_n = a_{n-1} + b_{n-1} + b_{n-2} > a_{n-1} + \frac{1}{3}(n-1)a_{n-1} + \frac{1}{3}(n-2)a_{n-2} = \frac{1}{3}n(a_{n-1} + a_{n-2}) + \frac{2}{3}(a_{n-1} - a_{n-2}) > \frac{1}{3}na_n, where the last inequality holds as an1=an2+an3>an2a_{n-1} = a_{n-2} + a_{n-3} > a_{n-2}.

By induction we get that bn>13nanb_n > \frac{1}{3}na_n for all n2n \ge 2.

Now notice that the right-hand inequality bnnan<1\frac{b_n}{n \cdot a_n} < 1 holds for n=3n = 3 and n=4n = 4 as b33a3=23<1\frac{b_3}{3a_3} = \frac{2}{3} < 1 and b44a4=a4+b3+b14a4=a4+a3+a2+a14a4<1\frac{b_4}{4a_4} = \frac{a_4+b_3+b_1}{4a_4} = \frac{a_4+a_3+a_2+a_1}{4a_4} < 1.

Let n5n \ge 5 and assume that the statement is valid for n1n-1 and n2n-2. Then bn=an1+bn1+bn2<an1+(n1)an1+(n2)an2=n(an1+an2)2an2<nanb_n = a_{n-1} + b_{n-1} + b_{n-2} < a_{n-1} + (n-1)a_{n-1} + (n-2)a_{n-2} = n(a_{n-1} + a_{n-2}) - 2a_{n-2} < na_n.

By induction, bn<nanb_n < na_n holds for all n3n \ge 3.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.