Two Integer Sequences

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Two Integer Sequences

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 1973

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1948 posts

#1 h Mar 7, 2010, 12:16 AM • 2 Y

Y by Adventure10, Mango247

Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined as follows:
$\begin{align*} X_0 = 1,\ X_1 = 1,\ X_{n + 1} = X_n + 2X_{n - 1} \quad (n = 1,2,3,\ldots), \\ Y_0 = 1,\ Y_1 = 7,\ Y_{n + 1} = 2Y_n + 3Y_{n - 1} \quad (n = 1,2,3,\ldots).\end{align*}$ Prove that, except for the "1", there is no term which occurs in both sequences.

This post has been edited 2 times. Last edited by djmathman, Dec 20, 2016, 9:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

955 posts

ocha

#2 h Mar 7, 2010, 1:49 AM • 3 Y

Y by rayfish, Adventure10, Mango247

Assuming you actually mean $X_{n+1}=X_n + 2X_{n-1}$ and the same for $Y_n$ then,

taking the sequences $\mod 8$

$\{X_i\} = \{1,1,3, - 3,3, - 3,3,...\}$

$\{Y_i\} = \{1, - 1,1, - 1,1, - 1,...\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1948 posts

#3 h Mar 7, 2010, 2:25 AM • 2 Y

Y by Adventure10, Mango247

ocha wrote:

Assuming you actually mean $X_{n + 1} = X_n + 2X_{n - 1}$ and the same for $Y_n$ then,

taking the sequences $\mod 8$

$\{X_i\} = \{1,1,3, - 3,3, - 3,3,...\}$

$\{Y_i\} = \{1, - 1,1, - 1,1, - 1,...\}$

Yes, it was a typo. My bad.
How does this finish the problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

955 posts

ocha

#4 h Mar 7, 2010, 2:50 AM • 2 Y

Y by Adventure10, Mango247

Brut3Forc3 wrote:

How does this finish the problem?

if $X_a=Y_b$ then we would have $\pm 3\equiv \pm 1 \mod 8$ ...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1948 posts

#5 h Mar 7, 2010, 2:56 AM • 2 Y

Y by Adventure10, Mango247

Oh. I think I misread it and thought that your sets repeated (the whole pattern, not just the plus minus 3 only), but now I get what you mean.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1221 posts

tc1729

#6 h May 14, 2012, 12:27 AM • 1 Y

Y by Adventure10

Solving the first recurrence yields $x_n=X(-1)^n+Y2^n.$ Using $x_1$ and $x_2$ yields $x_n=\frac{2^n+(-1)^{n+1}}{3}.$ Similarly, solving for the second recurrence yields $y_n=2\cdot 3^{n-1}+(-1)^n.$ So if $x_m=y_n$ then $2\cdot 3^n+3(-1)^n=2^m+(-1)^{m+1}$ or $2\cdot 3^n+3(-1)^n+(-1)^m$ .

If $m=1$ or $2$ , then $n=1$ is the only solution, corresponding the the fact that the term $1$ is in both sequences. If $m>2$ , then $2^m\equiv 0\pmod 8$ . But we have $3^n\equiv (-1)^n\pmod 4$ , so $2\cdot 3^n+3(-1)^n+(-1)^m\equiv 5(-1)^n+(-1)^m\pmod 8$ which cannot be $0\mod 8$ . Hence there are no solutions for $m>2$ , and the only integer in both sequences is indeed $1$ . $\Box$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17019 posts

#7 h Apr 12, 2021, 3:42 AM • 1 Y

Y by Mango247

This is probably overkill, but I still like it

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

290 posts

jred

#8 h Jun 3, 2021, 8:04 AM

Y by

OlympusHero wrote:

This is probably overkill, but I still like it

Solution

But you just proved that $X_n$ cannot be equal to $Y_n$ . :blush:

:blush:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wateringanddrowned

68 posts

wateringanddrowned

#9 h Jun 3, 2021, 8:45 AM • 1 Y

Y by Mango247

I really want to know how to proof a more general case,what if characteristic roots are irrational?(in this case,someone told me if the sequence is different,they had only finite terms which occur in both sequences.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeismathematics

1188 posts

lifeismathematics

#10 h Jul 25, 2022, 1:38 PM

Y by

cute sequences

This post has been edited 4 times. Last edited by lifeismathematics, Jul 25, 2022, 1:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#11 h Apr 13, 2023, 2:34 AM

Y by

jred wrote:

OlympusHero wrote:

This is probably overkill, but I still like it

Solution

But you just proved that $X_n$ cannot be equal to $Y_n$ . :blush:

:blush:

Yes, that is what we are trying to prove.

Back to the problem. We can prove this by induction. Base Case: Y_1>X_1, Y_2=2x7+3x1=17>3=1+2x1=X_2. Now suppose this is true for some k. Since Y_k>X_k, 2Y_k>X_k, and 3Y_(k-1)>2X_(k-1), so adding these two gives Y_(k+1)>X_(k+1), which means Y_n will always be greater than X_n for all $n\geq1$ .

Also, can someone tell me the latex for putting a black/white square at the end of your proofs?

Thanks @below and @2below.

This post has been edited 1 time. Last edited by huashiliao2020, Apr 13, 2023, 2:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

703 posts

#12 h Apr 13, 2023, 2:38 AM • 1 Y

Y by huashiliao2020

white square is \square and black square is \blacksquare

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

707 posts

#13 h Apr 13, 2023, 2:41 AM • 1 Y

Y by huashiliao2020

huashiliao2020 wrote:

Yes, that is what we are trying to prove.

Back to the problem. We can prove this by induction. Base Case: $Y_1>X_1, Y_2=2\cdot7+3\cdot1=17>3=1+2\cdot1=X_2$ . Now suppose this is true for some $k$ . Since $Y_k>X_k, 2Y_k>X_k$ , and $3Y_{k-1}>2X_{k-1}$ , so adding these two gives $Y_{k+1}>X_{k+1}$ , which means $Y_n$ will always be greater than $X_n$ for all $n\geq1$ . $\blacksquare$

Also, can someone tell me the latex for putting a black/white square at the end of your proofs?

This post has been edited 3 times. Last edited by S.Das93, Apr 13, 2023, 2:43 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a