Putnam 2022, Problem B-1

Suppose that $P(x) = a_1 x + a_2 x^2 + \cdots + a_n x^n$ is a polynomial with integer coefficients, with $a_1$ odd. Suppose that $e^{P(x)} = b_0 + b_1 x + b_2 x^2 + \cdots$ for all $x$. Prove that $b_k$ is nonzero for all $k \geq 0$.

Solution:
We prove that \( b_k k! \) is an odd integer for all \( k \geq 0 \).  

First solution. Since \( e^{P(x)} = \sum_{n=0}^\infty \frac{(P(x))^n}{n!} \), the number \( k! b_k \) is the coefficient of \( x^k \) in  
\[
(P(x))^k + \sum_{n=0}^{k-1} \frac{k!}{n!} (P(x))^n.
\]  

In particular, \( b_0 = 1 \) and \( b_1 = a_1 \) are both odd.  

Now suppose \( k \geq 2 \); we want to show that \( b_k \) is odd. The coefficient of \( x^k \) in \( (P(x))^k \) is \( a_1^k \). It suffices to show that the coefficient of \( x^k \) in \( \frac{k!}{n!} (P(x))^n \) is an even integer for any \( n < k \). For \( k \) even or \( n \leq k - 2 \), this follows immediately from the fact that \( \frac{k!}{n!} \) is an even integer. For \( k \) odd and \( n = k - 1 \), we have  
\[
\frac{k!}{(k-1)!} (P(x))^{k-1} = k(a_1 x + a_2 x^2 + \cdots)^{k-1}
\]  
\[
= k(a_1^{k-1} x^{k-1} + (k - 1) a_1^{k-2} a_2 x^k + \cdots)
\]  
and the coefficient of \( x^k \) is \( k(k - 1) a_1^{k-2} a_2 \), which is again an even integer.