Competition problem — Algebra — Maths Olympiad Prep

Library / /20 of 133

Algebra Difficulty 5.0 AIME Prove it Saudi Arabia

Let $\left(a_{n}\right)_{n \geq 0}$ and $\left(b_{n}\right)_{n \geq 0}$ be sequences defined by $a_{n+2}= a_{n+1}+a_{n}$ , $n=0,1, \ldots$ , $a_{0}=1$ , $a_{1}=2$ , and $b_{n+2}=b_{n+1}+b_{n}$ , $n=0,1, \ldots$ , $b_{0}=2$ , $b_{1}=1$ . How many integers do the sequences have in common?

Solution

We have $a_{2}=3$ , $a_{3}=5$ , $a_{4}=8$ , $\ldots$ and $b_{2}=3$ , $b_{3}=4$ , $b_{4}=7$ , $\ldots$ It follows $a_{0}=b_{0}$ , $a_{1}=b_{1}$ , $a_{2}=b_{2}$ , and $b_{3}<a_{3}<b_{4}<a_{4}<b_{5}$ . We prove by induction of step 2 that for $m \geq 3$ we have $b_{m}<a_{m}<b_{m+1}$ . The basis cases $m=3$ , $m=4$ are verified above. Assume that
$b_{k}<a_{k}<b_{k+1} \quad \text{ and } \quad b_{k+1}<a_{k+1}<b_{k+2}$
Adding these inequalities we get $b_{k}+b_{k+1}<a_{k}+a_{k+1}<b_{k+1}+ b_{k+2}$ , that is $b_{k+2}<a_{k+2}<b_{k+3}$ .
The sequences have in common only three integers: $1,2,3$ .

Want a route through all this instead of 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.