Maths Olympiad Prep

Library / /5 of 11

, 2012

Number theory Difficulty 8.2 Shortlist Prove it Balkan Mathematical Olympiad

A sequence (an)n=1(a_n)_{n=1}^\infty of positive integers satisfies the condition an+1=an+τ(n)a_{n+1} = a_n + \tau(n) for all positive integers nn where τ(n)\tau(n) is the number of positive integer divisors of nn. Determine whether two consecutive terms of this sequence can be perfect squares.

Solution

Solution. There are no two such consecutive terms.
Assume that an=x2a_n = x^2, an+1=y2a_{n+1} = y^2 where x,yx, y are positive integers. Then
(x+1)2y2=an+1=an+τ(n)=x2+τ(n)x2+2n. (x+1)^2 \le y^2 = a_{n+1} = a_n + \tau(n) = x^2 + \tau(n) \le x^2 + 2\sqrt{n}.
Therefore x<nx < \sqrt{n}. The last inequality gives an<na_n < n, which is impossible since the sequence is strictly increasing and a11a_1 \ge 1.
We used the inequality τ(n)2n\tau(n) \le 2\sqrt{n} which follows immediately from the fact that the positive integer divisors of nn can be paired off (with the possible exception of n\sqrt{n}) with one in each pair less than n\sqrt{n}.

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.