Q:

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

A:

2020 is the year we take down problems like Freeze Tag and various Putnam 6’s. Hope and determination abound. In a time like this, a Putnam 4 seems almost too easy. This one is nice, though, and it comes with a very sweet finish, if I do say so myself.

We begin this problem by trying to just get a feel for what the sequence looks like. For a given \(a\), the first few terms are:

\[ x_0 = 1 \] \[ x_1 = a \] \[ x_2 = a \] \[ x_3 = 2a^2 - 1 \] \[ x_4 = 4a^3 - 3a \]

I definitely went about trying many things before I stumbled upon the actual solution, so I don’t claim that I saw this the first time around. However, there is something rather familiar and suggestive about \(x_3\) and \(x_4\). If you are familiar with trig identities, you will notice that these are, in fact, the expansions of the cosine double and triple angle formulas. Namely

\[ \cos{2 \theta} = 2\cos^2 \theta - 1 \] \[ \cos{3 \theta} = 4\cos^3 \theta - 3\cos \theta \]

Thus it probably would behoove us to perform some kind of \(a = \cos \theta\) substitution, if we are allowed to do so. We will first prove that we are indeed allowed.

Remark 1

If \(\lvert a \rvert \gt 1\), then the sequence will never generate a value of \(0\).

Proof Remark 1

We will prove using induction that if \(\lvert a \rvert \gt 1\), then \(\lvert x_{n+1} \rvert \gt \lvert x_n \rvert \gt 1\) for all \(n \geq 2\).

For the base case, we note that

\[ \lvert x_3 \rvert = \lvert 2a^2 - 1 \rvert = 2a^2 - 1 \gt 2a^2 - \lvert a \rvert = \lvert a \rvert(2\lvert a \rvert - 1) \gt \lvert a \rvert (2\lvert a \rvert - \lvert a \rvert) = a^2 \gt \lvert a \rvert = \lvert x_2 \rvert \]

For the inductive step, we have

\[ \lvert x_{n+1} \rvert = \lvert 2 x_n x_{n-1} - x_{n-2} \rvert \] \[ \gt \lvert 2 x_n x_{n-1} \rvert - \lvert x_{n-2} \rvert \] \[ \gt \lvert 2 x_n x_{n-1} \rvert - \lvert x_{n-1} \rvert \] \[ = \lvert x_{n-1} \rvert (2 \lvert x_n \rvert - 1) \] \[ \gt \lvert x_{n-1} \rvert (2 \lvert x_n \rvert - \lvert x_n \rvert) \] \[ = \lvert x_{n-1} \rvert \lvert x_n \rvert \gt \lvert x_n \rvert \]

which completes the proof.

Remark 1 tells us that if \(a\) satisfies \(x_n = 0\), then \(\lvert a \rvert \lt 1\), which means that we can, in fact, make the substitution

\[ a = \cos \theta \]

for some \(\theta \in [0, 2\pi)\). This is where the magic happens.

Remark 2

Let \(a = \cos \theta\) for some \(\theta \in [0, 2\pi)\). Then for all \(n\), we have

\[x_n = \cos (F_n \theta)\]

where \(F_n\) is the \(n\)th Fibonacci number (\(F_0 = 0, F_1 = 1, F_2 = 1, ...\)).

Proof Remark 2

Once again, we will use induction. The base case is true by how we defined the sequence:

\[ x_0 = 1 = \cos 0 = \cos (F_0 \theta) \] \[ x_1 = a = \cos \theta = \cos (F_1 \theta) \] \[ x_2 = a = \cos \theta = \cos (F_2 \theta) \]

For the inductive step, all we need are a few elementary trig identities, namely:

\[ \cos (\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta \] \[ \cos 2 \alpha = 2 \cos^2 \alpha - 1 \] \[ \sin 2 \alpha = 2 \sin \alpha \cos \alpha \]

We have, for all \(n \geq 2\):

\[ x_{n+1} = 2 x_n x_{n-1} - x_{n-2} = 2 \cos (F_n \theta) \cos (F_{n-1} \theta) - \cos (F_{n-2} \theta) \] \[ = 2 \cos (F_{n-1}\theta + F_{n-2}\theta) \cos (F_{n-1}\theta) - \cos (F_{n-2} \theta) \] \[ = 2 \left [ \cos (F_{n-1}\theta) \cos (F_{n-2}\theta) - \sin (F_{n-1}\theta) \sin (F_{n-2}\theta) \right ] \cos (F_{n-1}\theta) - \cos (F_{n-2} \theta) \] \[ = 2 \cos^2 (F_{n-1}\theta) \cos (F_{n-2}\theta) - 2 \sin (F_{n-1}\theta) \sin (F_{n-2}\theta) \cos (F_{n-1}\theta) - \cos (F_{n-2} \theta) \] \[ = 2 \cos^2 (F_{n-1}\theta) \cos (F_{n-2}\theta) - \sin (2F_{n-1}\theta) \sin (F_{n-2}\theta) - \cos (F_{n-2} \theta) \] \[ = [ 2 \cos^2 (F_{n-1}\theta) - 1] \cos (F_{n-2}\theta) - \sin (2F_{n-1}\theta) \sin (F_{n-2}\theta) \] \[ = \cos (2F_{n-1}\theta) \cos (F_{n-2}\theta) - \sin (2F_{n-1}\theta) \sin (F_{n-2}\theta) \] \[ = \cos (2F_{n-1}\theta + F_{n-2}\theta) = \cos (F_{n-1}\theta + F_{n-1}\theta + F_{n-2}\theta) = \cos (F_{n-1}\theta + F_{n}\theta) = \cos (F_{n+1}\theta) \]

which completes the induction.

Remark 2 is the crux of the problem, and once we have this observation, the proof of periodicity is a natural side effect from the periodicity of the \(\cos\) function.

Let the real number \(a\) satisfy \(x_n = 0\), for some \(n\). By Remark 1, we can make the substitution \(a = \cos \theta\), and by Remark 2, we have

\[ 0 = x_n = \cos (F_n\theta) \]

which implies that \(F_n\theta = \frac{\pi}{2} + m\pi\) for some integer \(m\), which we can rearrange into \(\theta = \frac{\left(\frac{1}{2} + m \right)\pi}{F_n}\).

Since \(\cos\) has period \(2\pi\), the problem boils down to an examination of the sequence \(\lbrace F_k \rbrace_{k \geq 0} \pmod{4F_n}\). More precisely, we note that if

\[ F_k \equiv F_j \pmod{4F_n} \]

then we can write \(F_j = F_k + t4F_n\) for some integer \(t\). Then

\[ x_j = \cos (F_j\theta) = \cos (F_k\theta + t4F_n\theta) \] \[ = \cos \left (F_k\theta + t4F_n \cdot \frac{\left(\frac{1}{2} + m \right)\pi}{F_n} \right) \] \[ = \cos (F_k\theta + t2\pi + tm4\pi) \] \[ = \cos (F_k\theta) = x_k \]

This fact that \(F_k \equiv F_j \pmod{4F_n} \implies x_k = x_j\) is the heart of our periodicity. If we can prove that the sequence of Fibonacci numbers \(\lbrace F_k \rbrace_{k \geq 0} \pmod{4F_n}\) is periodic, then we will have also proven that the sequence \(\lbrace x_k \rbrace_{k \geq 0}\) is periodic as well.

Remark 3

The sequence \(\lbrace F_k \rbrace \pmod N\) is periodic for any positive integer \(N\).

Proof Remark 3

We first note that any tail of the sequence \(\lbrace F_k \rbrace \pmod N\) is uniquely determined by its first two elements. In other words, if we are given the values of \(F_i\) and \(F_{i+1}\), then \(F_j\) is uniquely determined for all \(j > i+1\). This is observed from the Fibonacci recurrence \(F_n = F_{n-1} + F_{n-2}\), which only takes in account the previous two terms when generating the next term.

Specifically, if there exist \(i\) and \(j\) such that \(F_i \equiv F_j, F_{i+1} \equiv F_{j+1} \pmod N\), then we know that the sequence must be eventually periodic with period \(j - i\), since in this case we know that the consecutive elements \(F_i, F_{i+1}\) generate a sequence which generates \(F_i, F_{i+1}\), which means it’ll generate the same sequence infinitely.

But there are only \(N\) unique residuals \(\pmod N\), which means that there are only \(N (N-1)\) unique ordered pairs of residuals \(\pmod N\). Consider the first \(N (N-1) + 1\) terms of the sequence \(\lbrace F_k \rbrace \pmod N\). By the pidgeonhole principle, there must exist \(i, j\) such that

\[ 0 \leq i \lt j \leq N (N-1) \]

and

\[ F_i \equiv F_j, F_{i+1} \equiv F_{j+1} \]

Thus the sequence \(\lbrace F_k \rbrace \pmod N\) is eventually periodic with period \(j - i\).

WLOG assume \(i\) is the smallest integer that satisfies the above periodicity conditions. To show that the sequence \(\lbrace F_k \rbrace_{k \geq 0} \pmod N\) is fully periodic, we need to show \(i = 0\), i.e. the periodic behavior begins with the first element in the sequence.

Consider \(\lbrace R_k \rbrace\), the Reverse Fibonacci sequence, defined by the recurrence

\[ R_n = R_{n-2} - R_{n-1} \]

Intuitively, \(\lbrace R_k \rbrace\) is the sequence generated by reading the Fibonacci sequence in reverse, since it is easy to show that if \(R_0 = F_M, R_1 = F_{M-1}\), then \(R_i = F_{M-i}\) for all \(0 \leq i \leq M\). As with the Fibonacci sequence, tails of this sequence are uniquely determined by their first two terms.

Let \(R_0 = F_{j+1}, R_1 = F_j\), where \(i\) and \(j\) are the indices defined above. Then \(\lbrace R_k \rbrace_{k \geq 0} \pmod N\) is fully periodic, since we have \(R_{j-i} = F_{i+1} = F_{j+1} = R_0, R_{j-1+1} = F_i = F_j = R_1\).

But \(\lbrace R_k \rbrace\) generates \(\lbrace F_k \rbrace\) in reverse, which means it must generate the beginning of \(\lbrace F_k \rbrace\), namely \(F_0\) and \(F_1\). This means that \(F_0\) and \(F_1\) are elements in the fully periodic part of the \(\lbrace R_k \rbrace\), which means that they must be part of the fully periodic part of \(\lbrace F_k \rbrace\), which implies that \(\lbrace F_k \rbrace_{k \geq 0} \pmod N\) is fully periodic.

Finishing Touches

Thus the sequence \(\lbrace F_k \rbrace \pmod{4F_n}\) is fully periodic, meaning there exists an integer \(T\) such that for all \(k \geq 0\),

\[ F_{k+T} \equiv F_k \pmod{4F_n} \]

which implies

\[ x_{k+T} = \cos (F_{k+T}\theta) = \cos (F_k\theta) = x_k \]