1973 USAMO Problems/Problem 2

Problem

Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined as follows:

$X_0=1$ , $X_1=1$ , $X_{n+1}=X_n+2X_{n-1}$ $(n=1,2,3,\dots),$ $Y_0=1$ , $Y_1=7$ , $Y_{n+1}=2Y_n+3Y_{n-1}$ $(n=1,2,3,\dots)$ .

Thus, the first few terms of the sequences are:

$X:1, 1, 3, 5, 11, 21, \dots$ , $Y:1, 7, 17, 55, 161, 487, \dots$ .

Prove that, except for the "1", there is no term which occurs in both sequences.

Solution

We can look at each sequence $\bmod{8}$ :

$X$ : $1$ , $1$ , $3$ , $5$ , $3$ , $5$ , $\dots$ , $Y$ : $1$ , $7$ , $1$ , $7$ , $1$ , $7$ , $\dots$ .

Proof that $X$ repeats $\bmod{8}$ :

The third and fourth terms are $3$ and $5$ $\bmod{8}$ . Plugging into the formula, we see that the next term is $11\equiv 3\bmod{8}$ , and plugging $5$ and $3$ , we get that the next term is $13\equiv 5\bmod{8}$ . Thus the sequence $X$ repeats, and the pattern is $3,5,3,5,\dots$ .

Proof that $Y$ repeats $\bmod{8}$ :

The first and second terms are $1$ and $7$ $\bmod{8}$ . Plugging into the formula, we see that the next term is $17\equiv 1\bmod{8}$ , and plugging $7$ and $1$ , we get that the next term is $23\equiv 7\bmod{8}$ . Thus the sequence $Y$ repeats, and the pattern is $1,7,1,7,\dots$ .

Combining both results, we see that $X_i$ and $Y_j$ are not congruent $\bmod{8}$ when $i\geq 3$ and $j\geq 2$ . Thus after the "1", the terms of each sequence are not equal.

Solution 2

We can solve this problem by finding a particular solution for each linear recurrence.

$X_{n+1} - X_n - 2X_{n-1} = 0$ with characteristic polynomial

$X^2 - X - 2 = (X - 2)(X + 1)$ , so $X = -1, 2$

$X_n = A(2)^n + B(-1)^n$

After plugging in to find the particular solution:

$X_0 = 1 = A + B$

$X_1 = 1 = 2A - B$

$A = \frac{1}{3}$ and $B = \frac{2}{3}$ , so

$X_n = \frac{1}{3}(2)^n + \frac{2}{3}(-1)^n$

Doing the same for $Y_n$ , we get

$Y_n = 2(3)^n - (-1)^n$

We know they're equal at $n = 0$ , so let's set them equal and compare.

$2(3)^n - (-1)^n = \frac{1}{3}((2)^n + 2(-1)^n)$

$6(3)^n - 3(-1)^n = (2)^n + 2(-1)^n$

$6(3)^n - 2^n = 5(-1)^n$

By induction, we know in general that $(\alpha + 1)^n > \alpha^n$ for all $\alpha, n > 0$ , so $6(3)^n > 2^n$ for all $n > 1$ .

Therefore, the left hand side is always increasing and will never equal 5 again, so equality between $X_n$ and $Y_n$ only holds when $n = 0$ , so they only share 1 term.

Solution 3 (simple)

First, $X_n$ and $Y_n$ are both positive for all nonnegative integers $n$ . This is since $X_1$ , $X_2$ , $Y_1$ , and $Y_2$ are all positive, and if $X_n$ and $X_{n-1}$ is positive then $X_{n+1}$ as a sum of two positive numbers is positive, and similarly for $Y_n$ . Simple.

Next, consider $Z_n = Y_n - X_n$ . We have $Z_{n+1} = Y_n + Z_n + 3 Z_{n-1} + X_{n-1}$ . Another easy inductive argument like above shows that $Z_n >0$ if $n>0$ . But if $Z_n >0$ then $Z_n \ne 0$ , so $X_n \ne Y_n$ as desired.

~ Ddk001

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1973 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1973 USAMO Problems/Problem 2

Contents

Problem

Solution

Solution 2

Solution 3 (simple)

See Also