1973 USAMO 第 2 题

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.

令 $\{X_n\}$ 和 $\{Y_n\}$ 表示两个整数序列，定义如下：

$$X_0=1,$$

$$X_1=1,$$

$$X_{n+1}=X_n+2X_{n-1}$$

$$

(n=1,2,3,\点),

$$

$$Y_0=1,$$

$$Y_1=7,$$

$$Y_{n+1}=2Y_n+3Y_{n-1}$$

$$

(n=1,2,3,\点)。

$$

因此，序列的前几项是：

$$

X:1, 1, 3, 5, 11, 21, \点,

$$

$$

Y:1, 7, 17, 55, 161, 487, \点。

$$

证明，除了“1”之外，没有任何项同时出现在两个序列中。