Difference between revisions of "1973 USAMO Problems/Problem 2"
Juicefruit (talk | contribs) (→Solution 2) |
|||
(6 intermediate revisions by the same user not shown) | |||
Line 34: | Line 34: | ||
{{alternate solutions}} | {{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== | ==See Also== |
Latest revision as of 11:38, 3 June 2024
Contents
Problem
Let and
denote two sequences of integers defined as follows:
![$X_0=1$](http://latex.artofproblemsolving.com/c/e/b/cebce4cef53ec8891f6b19b9e15609f8f67e3ce4.png)
![$X_1=1$](http://latex.artofproblemsolving.com/4/c/9/4c98f37726f1b237003a06d40752524a28e99f47.png)
![$X_{n+1}=X_n+2X_{n-1}$](http://latex.artofproblemsolving.com/7/9/f/79f9ae578208dd5fd22233a74eb9958b7fa123db.png)
![$(n=1,2,3,\dots),$](http://latex.artofproblemsolving.com/a/2/7/a27887235fc6fe223896299960f50abedf4113f4.png)
![$Y_0=1$](http://latex.artofproblemsolving.com/7/9/7/79793a5127f0c02da1cd1496fc8a96c10a26232a.png)
![$Y_1=7$](http://latex.artofproblemsolving.com/e/0/e/e0e33be65971d1a5f4e92726ac4f5928d8c6ab59.png)
![$Y_{n+1}=2Y_n+3Y_{n-1}$](http://latex.artofproblemsolving.com/0/e/7/0e713f61302bc1d06796c423e76fcc2e456b6df5.png)
![$(n=1,2,3,\dots)$](http://latex.artofproblemsolving.com/0/3/8/0382bde36fe67f5296e632643ceb5d774545d3b6.png)
Thus, the first few terms of the sequences are:
![$X:1, 1, 3, 5, 11, 21, \dots$](http://latex.artofproblemsolving.com/4/2/3/423b49eb7fcf22e80c66be8b01f2cbdd2d9c34fe.png)
![$Y:1, 7, 17, 55, 161, 487, \dots$](http://latex.artofproblemsolving.com/8/9/3/89343c5c6c83f02fb1b692cc7d7d845c7d56e3fe.png)
Prove that, except for the "1", there is no term which occurs in both sequences.
Solution
We can look at each sequence :
![$X$](http://latex.artofproblemsolving.com/6/a/4/6a47ca0fe7cb276abc022af6ac88ddae1a9d6894.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$3$](http://latex.artofproblemsolving.com/7/c/d/7cde695f2e4542fd01f860a89189f47a27143b66.png)
![$5$](http://latex.artofproblemsolving.com/7/9/0/79069377f91364c2f87a64e5f9f562a091c8a6c1.png)
![$3$](http://latex.artofproblemsolving.com/7/c/d/7cde695f2e4542fd01f860a89189f47a27143b66.png)
![$5$](http://latex.artofproblemsolving.com/7/9/0/79069377f91364c2f87a64e5f9f562a091c8a6c1.png)
![$\dots$](http://latex.artofproblemsolving.com/6/4/6/64683f315744c851898c8d65dace1a8aa31b93ab.png)
![$Y$](http://latex.artofproblemsolving.com/c/e/5/ce58e4af225c93d08606c26554caaa5ae32edeba.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$\dots$](http://latex.artofproblemsolving.com/6/4/6/64683f315744c851898c8d65dace1a8aa31b93ab.png)
- Proof that
repeats
:
The third and fourth terms are and
. Plugging into the formula, we see that the next term is
, and plugging
and
, we get that the next term is
. Thus the sequence
repeats, and the pattern is
.
- Proof that
repeats
:
The first and second terms are and
. Plugging into the formula, we see that the next term is
, and plugging
and
, we get that the next term is
. Thus the sequence
repeats, and the pattern is
.
Combining both results, we see that and
are not congruent
when
and
. 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.
with characteristic polynomial
, so
After plugging in to find the particular solution:
and
, so
Doing the same for , we get
We know they're equal at , so let's set them equal and compare.
By induction, we know in general that for all
, so
for all
.
Therefore, the left hand side is always increasing and will never equal 5 again, so equality between and
only holds when
, 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.