Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1973 USAMO Problems/Problem 2"

(phew done)
 
(→‎Solution 2)
 
(10 intermediate revisions by 4 users not shown)
Line 3: Line 3:
  
 
<center> <math>X_0=1</math>, <math>X_1=1</math>, <math>X_{n+1}=X_n+2X_{n-1}</math> <math>(n=1,2,3,\dots),</math></center>
 
<center> <math>X_0=1</math>, <math>X_1=1</math>, <math>X_{n+1}=X_n+2X_{n-1}</math> <math>(n=1,2,3,\dots),</math></center>
−
<center><math>Y_0=1</math>, <math>Y_1=1</math>, <math>Y_{n+1}=2Y_n+3Y_{n-1}</math> <math>(n=1,2,3,\dots)</math>.</center>
+
<center><math>Y_0=1</math>, <math>Y_1=7</math>, <math>Y_{n+1}=2Y_n+3Y_{n-1}</math> <math>(n=1,2,3,\dots)</math>.</center>
  
 
Thus, the first few terms of the sequences are:
 
Thus, the first few terms of the sequences are:
  
−
<center> <math>1</math>, <math>1</math>, <math>3</math>, <math>5</math>, <math>11</math>, <math>21</math>, <math>\dots</math>,</center>
+
<center> <math>X:1, 1, 3, 5, 11, 21, \dots</math>,</center>
−
<center> <math>1</math>, <math>7</math>, <math>17</math>, <math>55</math>, <math>161</math>, <math>487</math>, <math>\dots</math>.</center>
+
<center> <math>Y:1, 7, 17, 55, 161, 487, \dots</math>.</center>
  
 
Prove that, except for the "1", there is no term which occurs in both sequences.
 
Prove that, except for the "1", there is no term which occurs in both sequences.
Line 30: Line 30:
 
Combining both results, we see that <math>X_i</math> and <math>Y_j</math> are not congruent <math>\bmod{8}</math> when <math>i\geq 3</math> and <math>j\geq 2</math>. Thus after the "1", the terms of each sequence are not equal.
 
Combining both results, we see that <math>X_i</math> and <math>Y_j</math> are not congruent <math>\bmod{8}</math> when <math>i\geq 3</math> and <math>j\geq 2</math>. Thus after the "1", the terms of each sequence are not equal.
  
−
==See also==
+
 
 +
 
 +
 
 +
{{alternate solutions}}
 +
 
 +
==Solution 2==
 +
 
 +
We can solve this problem by finding a particular solution for each linear recurrence.
 +
 
 +
<math>X_{n+1} - X_n - 2X_{n-1} = 0</math> with characteristic polynomial
 +
 
 +
<math>X^2 - X - 2 = (X - 2)(X + 1)</math>, so <math>X = -1, 2</math>
 +
 
 +
<math>X_n = A(2)^n + B(-1)^n</math>
 +
 
 +
After plugging in to find the particular solution:
 +
 
 +
<math>X_0 = 1 = A + B</math>
 +
 
 +
<math>X_1 = 1 = 2A - B</math>
 +
 
 +
<math>A = \frac{1}{3}</math> and <math>B = \frac{2}{3}</math>, so
 +
 
 +
<math>X_n = \frac{1}{3}(2)^n + \frac{2}{3}(-1)^n</math>
 +
 
 +
Doing the same for <math>Y_n</math>, we get
 +
 
 +
<math>Y_n = 2(3)^n - (-1)^n</math>
 +
 
 +
We know they're equal at <math>n = 0</math>, so let's set them equal and compare.
 +
 
 +
<math>2(3)^n - (-1)^n = \frac{1}{3}((2)^n + 2(-1)^n)</math>
 +
 
 +
<math>6(3)^n - 3(-1)^n = (2)^n + 2(-1)^n</math>
 +
 
 +
<math>6(3)^n - 2^n = 5(-1)^n</math>
 +
 
 +
By induction, we know in general that <math>(\alpha + 1)^n > \alpha^n</math> for all <math>\alpha, n > 0</math>, so <math>6(3)^n > 2^n</math> for all <math>n > 1</math>.
 +
 
 +
Therefore, the left hand side is always increasing and will never equal 5 again, so equality between <math>X_n</math> and <math>Y_n</math> only holds when <math>n = 0</math>, so they only share 1 term.
 +
 
 +
==See Also==
  
 
{{USAMO box|year=1973|num-b=1|num-a=3}}
 
{{USAMO box|year=1973|num-b=1|num-a=3}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 10:38, 3 June 2024

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.



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

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.

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1973_USAMO_Problems/Problem_2&oldid=220014"