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
Difficulty Level
Suggested Book
Problem Solving Strategies by Arthur Engel

Start with hints

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<a_{n+1} 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 kth 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 kth 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<j, 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.

Watch the video (Coming Soon)

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...