2018 Putnam B Problems/Problem 4

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

Page

Toolbox

Search

2018 Putnam B Problems/Problem 4

Problem

Solution

See Also