\section*{Problem 2}

The sequence \(a_{n}\) is defined by \(a_{1}=1, a_{2}=2, a_{n+2}=a_{n+1}+a_{n}\). The sequence \(b_{n}\) is defined by \(b_{1}\) \(=2, b_{2}=1, b_{n+2}=b_{n+1}+b_{n}\). How many integers belong to both sequences?

\section*{Answer}

\(1,2,3\) only


\section*{Solution}

The first few terms are:

\begin{tabular}{llllllrr}
\(\mathrm{n}\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\(\mathrm{a}_{\mathrm{n}}\) & 1 & 2 & 3 & 5 & 8 & 13 & 21 \\
\(\mathrm{~b}_{\mathrm{n}}\) & 2 & 1 & 3 & 4 & 7 & 11 & 18
\end{tabular}

Note that for \(n=4,5\) we have \(a_{n-1}<b_{n}<a_{n}\). So by a trivial induction, the inequality holds for all \(n \geq 4\).

