Putnam 2017, Problem A-2

Let \( Q_0(x) = 1 \), \( Q_1(x) = x \), and  
\[
Q_n(x) = \frac{(Q_{n-1}(x))^2 - 1}{Q_{n-2}(x)}
\]  
for all \( n \geq 2 \). Show that, whenever \( n \) is a positive integer, \( Q_n(x) \) is equal to a polynomial with integer coefficients.

Solution:
### First solution
Define \( P_n(x) \) for \( P_0(x) = 1 \), \( P_1(x) = x \), and \( P_n(x) = xP_{n-1}(x) - P_{n-2}(x) \). We claim that \( P_n(x) = Q_n(x) \) for all \( n \geq 0 \); since \( P_n(x) \) clearly is a polynomial with integer coefficients for all \( n \), this will imply the desired result.  

Since \( \{P_n\} \) and \( \{Q_n\} \) are uniquely determined by their respective recurrence relations and the initial conditions \( P_0, P_1 \) or \( Q_0, Q_1 \), it suffices to check that \( \{P_n\} \) satisfies the same recurrence as \( Q \): that is, \( (P_{n-1}(x))^2 - P_n(x)P_{n-2}(x) = 1 \) for all \( n \geq 2 \). Here is one proof of this: for \( n \geq 1 \), define the \( 2 \times 2 \) matrices  
\[
M_n = \begin{pmatrix} P_{n-1}(x) & P_n(x) \\ P_{n-2}(x) & P_{n-1}(x) \end{pmatrix}, \quad T = \begin{pmatrix} x & -1 \\ 1 & 0 \end{pmatrix}
\]  
with \( P_{-1}(x) = 0 \) (this value being consistent with the recurrence). Then \( \det(T) = 1 \) and \( TM_n = M_{n+1} \), so by induction on \( n \) we have  
\[
(P_{n-1}(x))^2 - P_n(x)P_{n-2}(x) = \det(M_n) = \det(M_1) = 1.
\]  

### Remark
A similar argument shows that any second-order linear recurrent sequence also satisfies a quadratic second-order recurrence relation. A familiar example is the identity \( F_{n-1}F_{n+1} - F_n^2 = (-1)^n \) for \( F_n \) the \( n \)-th Fibonacci number. More examples come from various classes of orthogonal polynomials, including the Chebyshev polynomials mentioned below.