\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{China TST Quiz 2007/1/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 139}
\maketitle

\section*{Problem}
Fix an integer $n \ge 1$.
Prove there exists exactly one polynomial $P(x)$ of degree $n$ with real coefficients,
such that $P(0) = 1$ and $(x + 1)(P(x))^2 - 1$ is odd.

\section*{Video}
\href{https://www.youtube.com/watch?v=rmhfgp47avs&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/rmhfgp47avs}}

\section*{External Link}
\url{https://aops.com/community/p1365013}

\newpage

\section*{Solution}
Suppose the polynomial $P$ obeys
\[ 2 = (x+1)P(x)^2 + (-x+1)P(-x)^2. \]
Work in $\RR[y, y\inv]$ and substitute
\[ x = \half\left( y + \frac 1y \right). \]
Then the above equation can be rewritten as
\begin{align*}
  4 &= \left( y + \frac 1y + 2 \right) P(x)^2 - \left( y + \frac 1y - 2  \right) P(-x)^2 \\
  \iff 4y &= \left( (y+1) P(x) \right)^2 - \left( (y-1) P(-x) \right)^2 \\
  \iff 4y &= \Big( (y+1) P(x) + (y-1) P(-x) \Big)
  \Big( (y+1) P(x) - (y-1) P(-x) \Big).
\end{align*}
Using factorization in $\RR[y, y\inv]$, we see there must exist an integer $d \ge 0$
and a nonzero real number $\eps$ such that we have identities
\begin{align*}
  2\eps \cdot y^{d+1} &= (y+1) P(x) \pm (y-1) P(-x) \\
  \frac 2\eps \cdot y^{-d} &= (y+1) P(x) \mp (y-1) P(-x)
\end{align*}
for some opposite choice of signs $\pm$.
Replacing $y$ with $1/y$, it follows $\eps = \eps\inv \implies \eps = \pm 1$.
So the system of equations is equivalent to
\begin{align*}
  y^{d+1} + y^{-d} &= \eps (y+1) P(x) \\
  y^{d+1} - y^{-d} &= \pm \eps (y-1) P(-x)
\end{align*}
Now, the first equation implies that
\begin{align*}
  \eps P(x) &= \frac{y^{d+1}+y^{-d}}{y+1} \\
  &= \left( y^d + \frac{1}{y^d} \right)
  - \left( y^{d-1} + \frac{1}{y^{d-1}} \right)
  + \dots
  + (-1)^{d-1} \left( y + \frac 1y \right) + (-1)^d.
\end{align*}
The theory of Chebyshev polynomials guarantees that
$y^k + \frac{1}{y^k}$ is a degree-$k$ polynomial in $x$ for each $k \ge 0$.
Hence we see there is a unique choice of polynomial $P$ of degree $n$
(corresponding to $d=n$) which makes the identity
$P(x) = \eps \frac{y^{d+1}+y^{-d}}{y+1}$ true, for each $\eps \in \{\pm1\}$.
When we add the condition $P(0) = 1$ (set $y=i$ so $x=0$),
we find only one $\eps \in \{\pm1\}$ is valid.

Conversely, we have the implication
\[ \eps (y+1)P(x) = y^{d+1} + y^{-d}
  \implies \eps (y-1)P(-x) = \pm (y^{d+1} - y^{-d}) \]
which follows readily by making the substitution $y \mapsto iy$.
So the choice of polynomial $P$ we just mentioned will satisfy the entire system,
ergo (reversing the logic above) will satisfy the desired condition.
In other words, the unique possibility for $P$ does indeed work.

\begin{remark*}
  The first few actual polynomials $P$ are:
  \begin{align*}
    P(x) &= 1 \\
    P(x) &= 1 - 2x \\
    P(x) &= 1 + 2x - 4x^2 \\
    P(x) &= 1 - 4x - 4x^2 + 8x^3 \\
    P(x) &= 1 + 4x - 12x^2 - 8x^3 + 16x^4.
  \end{align*}
\end{remark*}

\end{document}
