2018 Putnam B Problems/Problem 4

Problem

Given a real number , we define a sequence by , , and for . Prove that if for some , then the sequence is periodic.

Solution

Suppose \( x_m = 0 \) for some \( m \geq 0 \). Then using the recurrence we can compute the next few terms explicitly in terms of \( x_{m-2} \) and \( x_{m-1} \): 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 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.