Select Page

# Understand the problem

Find all pairs $(b,c)$ of positive integers, such that the sequence defined by $a_1=b$, $a_2=c$ and $a_{n+2}= \left| 3a_{n+1}-2a_n \right|$ for $n \geq 1$ has only finite number of composite terms.

##### Source of the problem
Bulgarian Mathematical Olympiad 2002
Number theory
Medium
##### Suggested Book
Problem Solving Strategies by Arthur Engel

Do you really need a hint? Try it first!

There exists a general theory of second-order linear difference equations. Read about it here.
Can we have $a_n>a_{n+1}$ for all $n$? What happens if we do? What happens otherwise?

Note that if $a_n for some $n$ then the sequence becomes increasing thereafter. Use this fact to simplify the recurrence relation and solve it explicitly.

The sequence cannot be decreasing because it is a sequence of positive integers. Hence there exists (a smallest) $k$ such that $a_k\le a_{k+1}$. If $a_k=a_{k+1}$ then the sequence becomes constant from the $k$th term onwards (we shall treat this case later). Otherwise $3a_{k+1}-2a_k>a_k$ hence $a_{k+2}>a_{k+1}$. This implies that the sequence becomes increasing from the $k$th term onwards. Also, $a_{n+2}=3a_{n+1}-2a_n$ for $n\ge k$. This difference equation has the characteristic equation $\lambda^2-3\lambda +2=0$ (see the link in hint 1) which has the solutions $\lambda = 2,1$. Thus, $a_{n+k}=2^nA+B$ for $A,B$ satisfying $A+B=a_k, 2A+B=a_{k+1}$. Take any prime divisor $p$ of $A+B$. By Fermat’s little theorem, $2^{m(p-1)} \equiv 1 \; (\text{mod}\; p)$ for every positive integer $m$. Thus $2^{m(p-1)}A+B\equiv A+B\equiv 0\; (\text{mod}\; p)$. Hence the sequence contains infinitely many composites. This cannot be allowed, so the sequence cannot be strictly increasing at any point.

The above discussion shows that, for any permissible sequence, there exists a (smallest) $j$ and a prime $q$ such that $a_n=q$ for all $n\ge j$. For $n, the sequence is decreasing. Note that, either $q=a_{j+1}=3a_j-2a_{j-1}=3q-2a_{j-1}$ or $q =2a_{j-1}-3q$. Hence, either $a_{j-1}=q$ or $a_{j-1}=2q$. The first one can happen only if $j=1$ because otherwise the minimality of $j$ is violated. In that case, the sequence is constant and $b=c=q$. If $a_{j-1}=2q$ then either $j=2$ (in which case $b=2q, c=q$) or $q=|6q-2a_{j-2}|$ hence $a_{j-2}=3q\pm\frac{q}{2}$. The last equality forces $q$ to be 2. Thus $a_{j-2}=6\pm 1$. If $j>3$ then $4=a_{j-1}=|18\pm 3 - 2a_{j-3}|$ which is absurd as $2a_{j-3}$ cannot be an odd number. Hence $j=3$ in this case and $c=4,b=5,7$.

# Connected Program at Cheenta

#### Math Olympiad Program

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.

# Similar Problems

## Ratio with the sum of digits

Understand the problemFind the 3-digit number whose ratio with the sum of its digits is minimal.Albania TST 2013 Number Theory, Inequalities. Easy Problem Solving Strategies by Arthur Engel Start with hintsDo you really need a hint? Try it first!Suppose that the...

## Does there exist a Magic Rectangle?

Magic Squares are infamous; so famous that even the number of letters on its Wikipedia Page is more than that of Mathematics itself. People hardly talk about Magic Rectangles. Ya, Magic Rectangles! Have you heard of it? No, right? Not me either! So, I set off to...

## Coincident Nine-point Circles

Understand the problemLet be a triangle, its circumcenter, its centroid, and its orthocenter. Denote by , and the centers of the circles circumscribed about the triangles , and , respectively. Prove that the triangle is congruent to the triangle and that the...

## An inequality with unit coefficients

Understand the problemLet be positive real numbers. Show that there exist such that:Iberoamerican olympiad 2011InequalitiesEasyInequalities: An Approach Through Problems by B.J. VenkatachalaStart with hintsDo you really need a hint? Try it first!Try using...

## An integer with perfect square digits

Understand the problemFind all positive integers that have 4 digits, all of them perfect squares, and such that is divisible by 2, 3, 5 and 7. Centroamerican olympiad 2016 Number theory Easy An Excursion in Mathematics Start with hintsDo you really need a hint? Try...

## Euler’s theorem and an inequality

Understand the problemLet be the circumcenter and be the centroid of a triangle . If and are the circumcenter and incenter of the triangle, respectively,prove thatBalkan MO 1996 Geometry Easy Let $latex I$ be the incentre. Euler's theorem says that \$latex...

## A trigonometric relation and its implication

Understand the problemProve that a triangle is right-angled if and only ifVietnam National Mathematical Olympiad 1981TrigonometryMediumChallenge and Thrill of Pre-college MathematicsStart with hintsDo you really need a hint? Try it first!Familiarity with the...

## A polynomial equation and roots of unity

Understand the problemFind all polynomials with real coefficients such that divides .Indian National Mathematical Olympiad 2018AlgebraEasyProblem Solving Strategies by Arthur EngelStart with hintsDo you really need a hint? Try it first!Show that, given a zero of...

## Bicentric quadrilaterals inside a triangle

Understand the problemLet be a triangle and be cevians concurrent at a point . Suppose each of the quadrilaterals and has both circumcircle and incircle. Prove that is equilateral and coincides with the center of the triangle.Indian team selection test...

## Trilinear coordinates and locus

Understand the problemLet be an equilateral triangle and in its interior. The distances from to the triangle's sides are denoted by respectively, where . Find the locus of the points for which can be the sides of a non-degenerate triangle.Romanian Master in...