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 "2018 Putnam B Problems/Problem 4"

(Created page with "==Problem== Given a real number <math>a</math>, we define a sequence by <math>x_0 = 1</math>, <math>x_1 = x_2 = a</math>, and <math>x_{n+1} = 2x_nx_{n-1} - x_{n-2}</math> for...")
 
(→‎See Also)
 
(4 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
 +
Suppose \( x_m = 0 \) for some \( m \geq 0 \). Then using the recurrence
 +
<cmath>
 +
x_{n+1} = 2x_n x_{n-1} - x_{n-2},
 +
</cmath>
 +
we can compute the next few terms explicitly in terms of \( x_{m-2} \) and \( x_{m-1} \):
 +
<cmath>
 +
x_{m+1} = 2x_m x_{m-1} - x_{m-2} = -x_{m-2},
 +
</cmath>
 +
<cmath>
 +
x_{m+2} = 2x_{m+1} x_m - x_{m-1} = -x_{m-1},
 +
</cmath>
 +
<cmath>
 +
x_{m+3} = 2x_{m+2} x_{m+1} - x_m = 2(-x_{m-1})(-x_{m-2}) - 0 = 2x_{m-1} x_{m-2}.
 +
</cmath>
 +
Continuing in this way, each term can be expressed as a polynomial in \( x_{m-2} \) and \( x_{m-1} \) with integer coefficients. In particular, the sequence starting from \( x_m = 0 \) depends only on the fixed pair \( (x_{m-2}, x_{m-1}) \).
 +
 +
Since the pair \( (x_{m-2}, x_{m-1}) \) is fixed, the sequence of consecutive pairs
 +
<cmath>
 +
(x_{m-1}, x_m), \quad (x_m, x_{m+1}), \quad (x_{m+1}, x_{m+2}), \ldots
 +
</cmath>
 +
can take only finitely many distinct values determined algebraically from \( (x_{m-2}, x_{m-1}) \). Therefore, by the Pigeonhole Principle, some pair must eventually repeat. Once a pair repeats, the recurrence determines all subsequent terms uniquely, so the sequence becomes periodic.
 +
 +
So, if \( x_n = 0 \) for some \( n \), the sequence is periodic.
 +
 +
Note: I saw this problem also had no solution so here it is. I am new to AoPS so if there is anything I am missing please edit this.
 +
 +
~Pinotation
 +
 +
==See Also==
 +
 +
[[2018 Putnam B Problems|2018 Putnam B Entire Test]]
 +
 +
[[2018 Putnam B Problems/Problem 3|2018 Putnam B Problem 3]]
 +
 +
[[2018 Putnam B Problems/Problem 5|2018 Putnam B Problem 5]]
 +
 +
{{MAA Notice}}

Latest revision as of 18:23, 18 August 2025

Problem

Given a real number $a$, we define a sequence by $x_0 = 1$, $x_1 = x_2 = a$, and $x_{n+1} = 2x_nx_{n-1} - x_{n-2}$ for $n \ge 2$. Prove that if $x_n = 0$ for some $n$, then the sequence is periodic.

Solution

Suppose \( x_m = 0 \) for some \( m \geq 0 \). Then using the recurrence \[x_{n+1} = 2x_n x_{n-1} - x_{n-2},\] we can compute the next few terms explicitly in terms of \( x_{m-2} \) and \( x_{m-1} \): \[x_{m+1} = 2x_m x_{m-1} - x_{m-2} = -x_{m-2},\] \[x_{m+2} = 2x_{m+1} x_m - x_{m-1} = -x_{m-1},\] \[x_{m+3} = 2x_{m+2} x_{m+1} - x_m = 2(-x_{m-1})(-x_{m-2}) - 0 = 2x_{m-1} x_{m-2}.\] Continuing in this way, each term can be expressed as a polynomial in \( x_{m-2} \) and \( x_{m-1} \) with integer coefficients. In particular, the sequence starting from \( x_m = 0 \) depends only on the fixed pair \( (x_{m-2}, x_{m-1}) \).

Since the pair \( (x_{m-2}, x_{m-1}) \) is fixed, the sequence of consecutive pairs \[(x_{m-1}, x_m), \quad (x_m, x_{m+1}), \quad (x_{m+1}, x_{m+2}), \ldots\] can take only finitely many distinct values determined algebraically from \( (x_{m-2}, x_{m-1}) \). Therefore, by the Pigeonhole Principle, some pair must eventually repeat. Once a pair repeats, the recurrence determines all subsequent terms uniquely, so the sequence becomes periodic.

So, if \( x_n = 0 \) for some \( n \), the sequence is periodic.

Note: I saw this problem also had no solution so here it is. I am new to AoPS so if there is anything I am missing please edit this.

~Pinotation

See Also

2018 Putnam B Entire Test

2018 Putnam B Problem 3

2018 Putnam B Problem 5

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_Putnam_B_Problems/Problem_4&oldid=258246"