Maths Olympiad Prep

Library / /59 of 426

Algebra Difficulty 4.8 AIME Prove it Saudi Arabia

Let (an)n1(a_n)_{n \ge 1} be a sequence given by a1=45a_1 = 45 and
an=an12+15an1 a_n = a_{n-1}^2 + 15a_{n-1}
for n>1n > 1. Prove that the sequence contains no perfect squares.

Solution

By induction we can show that an>0a_n > 0 for all positive integer nn. Suppose that there exists a positive integer nn such that ana_n is a perfect square.
an=an12+15an1=an1(an1+15) a_n = a_{n-1}^2 + 15a_{n-1} = a_{n-1}(a_{n-1} + 15)
so an1ana_{n-1} \mid a_n for all positive integers nn. Thus, it follows that
a1=45an,for all positive integers n. a_1 = 45 \mid a_n, \quad \text{for all positive integers } n.
Let k>1k > 1 be the smallest positive integer such that aka_k is a perfect square and ak1=45xa_{k-1} = 45x with xx a positive integer. We have
ak=45x(45x+15)=1523x(3x+1) a_k = 45x(45x + 15) = 15^2 \cdot 3x(3x + 1)
is a perfect square. On the other hand, (3x,3x+1)=1(3x, 3x + 1) = 1 implies 3x3x and 3x+13x + 1 are perfect squares, so 3x=03x = 0 and 3x+1=13x + 1 = 1. It is impossible since an>0a_n > 0 for all nn.
\square

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.