Q:

Let

\[ Q_0(x) = 1 \]

\[ Q_1(x) = x \]

\[ Q_n(x) = \frac{(Q_{n-1}(x))^2 - 1}{Q_{n-2}(x)} \]

for all $n \geq 2$. Prove that $Q_n(x)$ is a polynomial with integer coefficients for all $n$.

A:

Our approach to this problem comes in two parts: first we will prove that each $Q_n(x)$ is indeed a polynomial, and second we will then show that each of these polynomials has integer coefficients. For the first part of the proof, we use the Fundamental Theorem of Algebra, from which it can be proven that

\[ Q_{n-1}(x) \Big\vert Q_n(x) \]

if and only if every root of $Q_{n-1}(x)$ is also a root of $Q_n(x)$.

Part 1

Assume for induction that for all $2 \leq k \leq n$,

\[ Q_k(x) = \frac{(Q_{k-1}(x))^2 - 1}{Q_{k-2}(x)} \]

is a polynomial with integer coefficients.

Consider

\[ Q_{n+1}(x) = \frac{(Q_{n}(x))^2 - 1}{Q_{n-1}(x)} \]

and let $r$ be any root of $Q_{n-1}(x)$, i.e. $Q_{n-1}(r) = 0$. Then we have

\[ 0 = Q_{n-1}(r) = \frac{(Q_{n-2}(r))^2 - 1}{Q_{n-3}(r)} \]

\[ \implies Q_{n-2}(r) = \pm 1 \]

But we also have

\[ Q_n(r) = \frac{(Q_{n-1}(r))^2 - 1}{Q_{n-2}(r)} = - \frac{1}{Q_{n-2}(r)} = \mp 1 \]

\[ \implies (Q_n(r))^2 - 1 = 0 \]

thus $r$ is a root of $(Q_n(x))^2 - 1$. This is true for all roots $r$ of $Q_{n-1}(x)$, therefore by the Fundamental Theorem of Algebra,

\[ Q_{n-1}(x) \Big\vert (Q_n(x))^2 - 1 \]

which implies $Q_{n+1}(x) = \frac{(Q_{n}(x))^2 - 1}{Q_{n-1}(x)}$ is a polynomial.

By induction, $Q_n(x)$ is a polynomial for all $n$.

Part 2

To prove that all of the $Q_n(x)$ have integer coefficients, we first make an additional note that all $Q_n(x)$ are monic, i.e. their leading coefficients are $1$. (This can be proved with induction.)

We have

\[ Q_{n+1}(x)Q_{n-1}(x) = (Q_n(x))^2 - 1 \]

and thus we see that we can write $(Q_n(x))^2 - 1$, a monic polynomial, as the product of $Q_{n+1}(x)$ and $Q_{n-1}(x)$, two other monic polynomials. By our inductive hypothesis, we know that both $Q_{n-1}(x)$ and $(Q_n(x))^2 - 1$ have integer coefficients. By these facts, we can conclude that $Q_{n+1}(x)$ must have integer coefficients as well, but if you don’t believe me, I will prove this explicitly.

Write

\[ Q_{n+1}(x) = x^p + a_{p-1}x^{p-1} + \cdots + a_0 \]

\[ Q_{n-1}(x) = x^q + b_{q-1}x^{q-1} + \cdots + b_0 \]

We know that all of the $b_i$s are integers, and we want to prove that all of the $a_i$s are integers as well.

Expanding the product of the two polynomials, we have

\[ (Q_n(x))^2 - 1 = Q_{n+1}(x)Q_{n-1}(x) = x^{p+q} + (a_{p-1} + b_{q-1})x^{p+q-1} + \cdots \]

Immediately we see that $a_{p-1}$ must be an integer, since $b_{q-1}$ and $a_{p-1} + b_{q-1}$ are both integers.

Next we examine the $x^{p+q-2}$ coefficient, which is

\[ a_{p-2} + a_{p-1}b_{q-1} \]

which, since we just proved $a_{p-1}$ is an integer and by similar logic to before, implies that $a_{p-2}$ must also be an integer.

Thus we inductively continue, noting that the $x^{p+q-i}$ coefficient is

\[ a_{p-i} + a_{p-i+1}b_{q-1} + (\cdots) \]

where by induction the terms inside $a_{p-i+1}b_{q-1} + (\cdots)$ are all integers, so therefore $a_{p-i}$ must also be an integer.

Thus all $a_i$ are integers, and we have proven that $Q_{n+1}(x)$ is a polynomial with integer coefficients.

By induction, all $Q_n(x)$ are polynomials with integer coefficients.