Maths Olympiad Prep

Library / /11 of 24

Algebra Difficulty 6.2 National olympiad Prove it Belarus

A sequence (an)(a_n), nNn \in \mathbb{N} is defined as
a1=1, a2=2, a3=3 and an=an1an2+7an3, for n4. a_1 = 1,\ a_2 = 2,\ a_3 = 3 \text{ and } a_n = \frac{a_{n-1} a_{n-2} + 7}{a_{n-3}}, \text{ for } n \ge 4.
Prove that all terms of this sequence are integers.

Solution

It is evident that all terms of the sequence are positive. Find a4a_4. Since a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, we have
a4=a3a2+7a1=13.(1) a_4 = \frac{a_3 a_2 + 7}{a_1} = 13. \quad (1)
By condition,
an+1=anan1+7an2=[7=anan3an1an2]==anan1+anan3an1an2an2=anan1+an3an2an1,n4.(2) \begin{aligned} a_{n+1} &= \frac{a_n a_{n-1} + 7}{a_{n-2}} = [7 = a_n a_{n-3} - a_{n-1} a_{n-2}] = \\ &= \frac{a_n a_{n-1} + a_n a_{n-3} - a_{n-1} a_{n-2}}{a_{n-2}} = a_n \frac{a_{n-1} + a_{n-3}}{a_{n-2}} - a_{n-1}, \quad n \ge 4. \end{aligned} \quad (2)
If we prove that all numbers an1+an3an2\frac{a_{n-1} + a_{n-3}}{a_{n-2}}, n4n \ge 4, are integers, then we obtain
that all numbers ana_n, n5n \ge 5, are integers, since the numbers a1,a2,a3,a4a_1, a_2, a_3, a_4 are integers. Let bn=(an1+an3)/an2b_n = (a_{n-1} + a_{n-3})/a_{n-2}, n4n \ge 4. In particular
b4=a3+a1a2=3+12=2andb5=a4+a2a3=13+23=5.(3) b_4 = \frac{a_3 + a_1}{a_2} = \frac{3+1}{2} = 2 \quad \text{and} \quad b_5 = \frac{a_4 + a_2}{a_3} = \frac{13+2}{3} = 5. \quad (3)
Show that the sequence (bn)(b_n), n4n \ge 4, is periodic with 2 as its period, i.e. bn=bn2b_n = b_{n-2} for all n6n \ge 6. From definition of the sequences (bn)(b_n) and (an)(a_n) it follows that
bn=an1+an3an2=an2an3+7an4+an3an2==an2an3+7+an3an4an4an2=[7=an2an5an3an4]==an2an3+(an2an5an3an4)+an3an4an4an2==an2an3+an2an5an4an2=an3+an5an4=bn2,n6. \begin{aligned} b_n &= \frac{a_{n-1} + a_{n-3}}{a_{n-2}} = \frac{\frac{a_{n-2} a_{n-3} + 7}{a_{n-4}} + a_{n-3}}{a_{n-2}} = \\ &= \frac{a_{n-2} a_{n-3} + 7 + a_{n-3} a_{n-4}}{a_{n-4} a_{n-2}} = [7 = a_{n-2} a_{n-5} - a_{n-3} a_{n-4}] = \\ &= \frac{a_{n-2} a_{n-3} + (a_{n-2} a_{n-5} - a_{n-3} a_{n-4}) + a_{n-3} a_{n-4}}{a_{n-4} a_{n-2}} = \\ &= \frac{a_{n-2} a_{n-3} + a_{n-2} a_{n-5}}{a_{n-4} a_{n-2}} = \frac{a_{n-3} + a_{n-5}}{a_{n-4}} = b_{n-2}, \quad n \ge 6. \end{aligned}
Therefore, taking into account (3), we have b2k=b4=2b_{2k}=b_4=2 and b2k+1=b5=5b_{2k+1}=b_5=5 for all k=2,3,k=2,3,\dots. Since (see (2)) an+1=anbnan1a_{n+1} = a_n b_n - a_{n-1} for all n4n \ge 4, and all numbers bnb_n, n4n \ge 4, and numbers a1,a2,a3,a4a_1, a_2, a_3, a_4 are integers, it follows that all terms of the sequence (an)(a_n) are integers.

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.