Maths Olympiad Prep

Library / /1161 of 1394

, 2020

Algebra Difficulty 5.7 AIME, harder Prove it United States

Problem:

We call a positive integer tt good if there is a sequence a0,a1,a_{0}, a_{1}, \ldots of positive integers satisfying a0=15a_{0}=15, a1=ta_{1}=t, and
an1an+1=(an1)(an+1) a_{n-1} a_{n+1} = (a_{n} - 1)(a_{n} + 1)
for all positive integers nn. Find the sum of all good numbers.

Solution

Solution:

By the condition of the problem statement, we have
an2an1an+1=1=an12an2an a_{n}^{2} - a_{n-1} a_{n+1} = 1 = a_{n-1}^{2} - a_{n-2} a_{n}
This is equivalent to
an2+anan1=an1+an+1an \frac{a_{n-2} + a_{n}}{a_{n-1}} = \frac{a_{n-1} + a_{n+1}}{a_{n}}
Let k=a0+a2a1k = \frac{a_{0} + a_{2}}{a_{1}}. Then we have
an1+an+1an=an2+anan1=an3+an1an2==a0+a2a1=k. \frac{a_{n-1} + a_{n+1}}{a_{n}} = \frac{a_{n-2} + a_{n}}{a_{n-1}} = \frac{a_{n-3} + a_{n-1}}{a_{n-2}} = \cdots = \frac{a_{0} + a_{2}}{a_{1}} = k.
Therefore we have an+1=kanan1a_{n+1} = k a_{n} - a_{n-1} for all n1n \geq 1. We know that kk is a positive rational number because a0,a1a_{0}, a_{1}, and a2a_{2} are all positive integers. We claim that kk must be an integer. Suppose that k=pqk = \frac{p}{q} with gcd(p,q)=1\operatorname{gcd}(p, q) = 1. Since kan=an1+an+1k a_{n} = a_{n-1} + a_{n+1} is always an integer for n1n \geq 1, we must have qanq \mid a_{n} for all n1n \geq 1. This contradicts a22a1a3=1a_{2}^{2} - a_{1} a_{3} = 1. Conversely, if kk is an integer, inductively all aia_{i} are integers.

Now we compute a2=t2115a_{2} = \frac{t^{2} - 1}{15}, so k=t2+22415tk = \frac{t^{2} + 224}{15 t} is an integer. Therefore 15kt=224t15 k - t = \frac{224}{t} is an integer. Combining with the condition that a2a_{2} is an integer limits the possible values of tt to 1,4,14,16,56,2241, 4, 14, 16, 56, 224. The values t<15t < 15 all lead to an=0a_{n} = 0 for some nn whereas t>15t > 15 leads to a good sequence. The sum of the solutions is
16+56+224=296 16 + 56 + 224 = 296

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 reproduced verbatim; metadata (topic, difficulty) added by this project.