Olympiad Maths Prep

Library / /22 of 33

Algebra Difficulty 6.7 National olympiad Prove it Belarus

An infinite sequence (an)(a_n), nNn \in \mathbb{N}, of positive numbers is called *lacunar* if there exists a number q>1q > 1 such that an+1/anqa_{n+1}/a_n \ge q for all nNn \in \mathbb{N}. Also, the sequence is called *rare* if there exists a positive integer kk such that the interval (x,2x)(x, 2x) contains at most kk terms of this sequence for any positive xx.

a) Is it true that any lacunar sequence is rare?

b) Is it true that any increasing rare sequence is lacunar?

Solution

a) Let the sequence (an)(a_n), nNn \in \mathbb{N}, be lacunar. Then there exists a number q>1q > 1 such that
an+1qannN.(1) a_{n+1} \ge q a_n \quad \forall n \in \mathbb{N}. \qquad (1)
In particular, any lacunar sequence is increasing. From (1) it follows that any half-interval (x,qx](x, qx] contains at most one term of this sequence. Indeed, if we assume that ana_n and an+1a_{n+1} belong to this half-interval, then an+1an<qxx=q\frac{a_{n+1}}{a_n} < \frac{qx}{x} = q, contrary to (1).

Consider any positive integer kk such that qk>2q^k > 2 (e.g., k=[log22]+1k = [\log_2 2] + 1, where [y][y] stands for the integer part of yy). It is evident that
(x,2x)i=1k(qi1x,qix].(2) (x, 2x) \subset \bigcup_{i=1}^{k} (q^{i-1}x, q^i x]. \qquad (2)
Since at most one term of (an)(a_n) belongs to the half-interval (qi1x,qix](q^{i-1}x, q^i x], from inclusion (2) it follows that at most kk terms of (an)(a_n) belong to the interval (x,2x)(x, 2x).

b) We define the sequence (an)(a_n), nNn \in \mathbb{N}, as
a2n1=2n,a2n=2n(1+1n+1),nN.(3) a_{2n-1} = 2^n, \quad a_{2n} = 2^n \left(1 + \frac{1}{n+1}\right), \quad n \in \mathbb{N}. \qquad (3)
This sequence is increasing since from (3) it follows that a2n1<a2n<a2n+1a_{2n-1} < a_{2n} < a_{2n+1} for all nNn \in \mathbb{N}. Moreover, this sequence is rare since at most one number of the form 2m2^m, mNm \in \mathbb{N}, belongs to any interval (x,2x)(x, 2x), and so at most three terms of this sequence belong to this interval.

On the other hand, we have
a2na2n1=1+1n+1,nN, \frac{a_{2n}}{a_{2n-1}} = 1 + \frac{1}{n+1}, \quad n \in \mathbb{N},
but the numbers 1+1n+11 + \frac{1}{n+1} may be arbitrary close to 11 (for nn large enough), hence, the sequence (an)(a_n), nNn \in \mathbb{N}, is not lacunar.

Looking for a route rather than 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.