Maths Olympiad Prep

Library / /10 of 33

Algebra Difficulty 7.8 National olympiad, round 2 Prove it Turkey

Let a1,a2,,a1000a_1, a_2, \dots, a_{1000} be a sequence of integers such that a1=3a_1 = 3, a2=7a_2 = 7 and for all n=2,3,,999n = 2, 3, \dots, 999
an+1an=4(a1+a2)(a2+a3)(an1+an). a_{n+1} - a_n = 4(a_1 + a_2)(a_2 + a_3) \cdots (a_{n-1} + a_n).
Find the number of indices 1n10001 \le n \le 1000 for which an+2018a_n + 2018 is a perfect square.

Solution

For n2n \ge 2, we have
an+1ananan1=4(a1+a2)(a2+a3)(an1+an)4(a1+a2)(a2+a3)(an2+an1)=an1+an \frac{a_{n+1} - a_n}{a_n - a_{n-1}} = \frac{4(a_1 + a_2)(a_2 + a_3) \cdots (a_{n-1} + a_n)}{4(a_1 + a_2)(a_2 + a_3) \cdots (a_{n-2} + a_{n-1})} = a_{n-1} + a_n
and hence an+1=an2+anan12a_{n+1} = a_n^2 + a_n - a_{n-1}^2. a2=a122a_2 = a_1^2 - 2 and by induction assuming an=an122a_n = a_{n-1}^2 - 2 we can show that an+1=an22a_{n+1} = a_n^2 - 2.

We get a2=7=4522018a_2 = 7 = 45^2 - 2018, a3=a222=47a_3 = a_2^2 - 2 = 47, a4=4722=2207=6522018a_4 = 47^2 - 2 = 2207 = 65^2 - 2018 and hence an+2018a_n+2018 is a perfect square for n=2,4n=2,4. Let us show that an+2018a_n+2018 is not a perfect square for n>4n>4. Let ak+2018=c2a_k+2018 = c^2 for some k>4k > 4, cZ+c \in \mathbb{Z}^+. Then c2ak12=2016c^2 - a_{k-1}^2 = 2016. Since c>ak1c > a_{k-1}, we get 2016=c2ak12(ak1+1)2ak12=2ak1+12016 = c^2 - a_{k-1}^2 \ge (a_{k-1} + 1)^2 - a_{k-1}^2 = 2a_{k-1} + 1 and hence ak1<1008a_{k-1} < 1008. However, the sequence is increasing and for k>4k > 4 we have ak1a4=2207>1008a_{k-1} \ge a_4 = 2207 > 1008 which is a contradiction. The answer is 2.

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.