Maths Olympiad Prep

Library / /460 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

By the condition of the problem statement, we have an2an1an+1=1=an12an2ana_{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,561,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=29616+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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.