Library / China Hong Kong Mathematical Olympiad /20 of 89

China Hong Kong Mathematical Olympiad

Algebra Difficulty 5.3 AIME, harder Prove it Hong Kong

Given that $\{a_n\}$ and $\{b_n\}$ are two sequences of integers defined by
$a_1 = 1,\ a_2 = 10,\ a_{n+1} = 2a_n + 3a_{n-1} \quad \text{for } n = 2, 3, 4, \dots,$
$b_1 = 1,\ b_2 = 8,\ b_{n+1} = 3b_n + 4b_{n-1} \quad \text{for } n = 2, 3, 4, \dots$
Prove that, besides the number ‘1’, no two numbers in the sequences are identical.

Solution

The two sequences are $a_n = 1, 10, 23, 76, \dots$ and $b_n = 1, 8, 28, 116, \dots$ . Considering modulo $9$ , we have
$a_n \equiv 1, 1, 5, 4, 5, 4, \dots \pmod{9},$
$b_n \equiv 1, 8, 1, 8, \dots \pmod{9}.$
Since each term of the two sequences only depends on the two previous terms, we can show by induction that $a_n \equiv 4, 5 \pmod{9}$ for $n \ge 3$ and $b_n \equiv 1, 8 \pmod{9}$ for all $n$ . Therefore, $a_m \ne b_n$ whenever $m \ge 3$ .

Clearly the two sequences are strictly increasing. Thus, it is easy to see that the number $10$ does not appear in the second sequence. Therefore, the only common number appearing in both sequences is $a_1 = b_1 = 1$ .

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.