Two Integer Sequences
Source: USAMO 1973
March 7, 2010
modular arithmetic
Problem Statement
Let and denote two sequences of integers defined as follows:
\begin{align*} X_0 \equal{} 1,\ X_1 \equal{} 1,\ X_{n \plus{} 1} \equal{} X_n \plus{} 2X_{n \minus{} 1} (n \equal{} 1,2,3,\ldots), \\
Y_0 \equal{} 1,\ Y_1 \equal{} 7,\ Y_{n \plus{} 1} \equal{} 2Y_n \plus{} 3Y_{n \minus{} 1} (n \equal{} 1,2,3,\ldots).\end{align*}
Prove that, except for the "1", there is no term which occurs in both sequences.