Putnam 2017, Problem A-1

Let \( S \) be the smallest set of positive integers such that  
(a) \( 2 \) is in \( S \),  
(b) \( n \) is in \( S \) whenever \( n^2 \) is in \( S \), and  
(c) \( (n+5)^2 \) is in \( S \) whenever \( n \) is in \( S \).  
Which positive integers are not in \( S \)?  
(The set \( S \) is "smallest" in the sense that \( S \) is contained in any other such set.)

Solution:
We claim that the positive integers not in \( S \) are \( 1 \) and all multiples of \( 5 \). If \( S \) consists of all other natural numbers, then \( S \) satisfies the given conditions: note that the only perfect squares not in \( S \) are \( 1 \) and numbers of the form \( (5k)^2 \) for some positive integer \( k \), and it readily follows that both (b) and (c) hold.  

Now suppose that \( T \) is another set of positive integers satisfying (a), (b), and (c). Note from (b) and (c) that if \( n \in T \) then \( n + 5 \in T \), and so \( T \) satisfies the following property:  
(d) if \( n \in T \), then \( n + 5k \in T \) for all \( k \geq 0 \).  

The following must then be in \( T \), with implications labeled by conditions (b) through (d):  
\[
2 \stackrel{c}{\Rightarrow} 49 \stackrel{a}{\Rightarrow} 54^2 \stackrel{a}{\Rightarrow} 56^2 \stackrel{b}{\Rightarrow} 56 \stackrel{d}{\Rightarrow} 121 \stackrel{b}{\Rightarrow} 11
\]  
\[
11 \stackrel{d}{\Rightarrow} 16 \stackrel{b}{\Rightarrow} 4 \stackrel{d}{\Rightarrow} 9 \stackrel{b}{\Rightarrow} 3
\]  
\[
16 \stackrel{d}{\Rightarrow} 36 \stackrel{b}{\Rightarrow} 6
\]  

Since \( 2, 3, 4, 6 \in T \), by (d) \( S \subseteq T \), and so \( S \) is smallest.  

### Second solution
We establish directly that \( Q_n(x) = xQ_{n-1}(x) - Q_{n-2}(x) \), which again suffices. From the equation  
\[
1 = Q_{n-1}(x)^2 - Q_n(x)Q_{n-2}(x) = Q_n(x)^2 - Q_{n+1}(x)Q_{n-1}(x)
\]  
we deduce that  
\[
Q_{n-1}(x)(Q_{n-1}(x) + Q_{n+1}(x)) = Q_n(x)(Q_n(x) + Q_{n-2}(x)).
\]  

Since \( \deg(Q_n(x)) = n \) by an obvious induction, the polynomials \( Q_n(x) \) are all nonzero. We may thus rewrite the previous equation as  
\[
\frac{Q_{n+1}(x) + Q_{n-1}(x)}{Q_n(x)} = \frac{Q_n(x) + Q_{n-2}(x)}{Q_{n-1}(x)},
\]  
meaning that the rational functions \( \frac{Q_n(x) + Q_{n-2}(x)}{Q_{n-1}(x)} \) are all equal to a constant value. By taking \( n = 2 \) and computing from the definition that \( Q_2(x) = x^2 - 1 \), we find the constant value to be \( x \); this yields the desired recurrence.  

### Remark
By induction, one may also obtain the explicit formula  
\[
Q_n(x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n - k}{k} x^{n - 2k}.
\]