Maths Olympiad Prep

Library / Balkan Shortlist /5 of 10

Balkan Shortlist, 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)2≤y2=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 a1≥1a_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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.