Kvant Math Problem 488
The recurrence
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m00s
Source on kvant.digital
Problem
Consider the sequence of polynomials $P_0$, $P_1$, $P_2$, $\ldots$, defined by the conditions $P_0(x)=1$, $P_1(x)=x$, $$P_{n+1}(x)=x,P_n(x)-P_{n-1}(x),\quad n\ge1.\tag1$$. Prove the equalities
- $$\underbrace{x-\dfrac1{x-\dfrac1{x-\dfrac1{\raisebox{4pt}{$\ddots\vphantom{\dfrac00}$}{}-\dfrac1x}}}}{n~\text{раз}}=\dfrac{P_n(x)}{P{n-1}(x)};$$
- $$\dfrac{\sin{(n+1)\phi}}{\sin\phi}=P_n(2\cos\phi),\quad\text{если}
\dfrac\phi\pi\text{— не целое};$$ - $$t^{n+1}-\dfrac1{t^{n+1}}=\left(t-\dfrac1t\right)P_n{\left(t+\dfrac1t\right)},\quad\text{если}~t\ne0;$$
- $$P_n(x)=\prod\limits_{1\le k\le n}\left(x-2\cos\dfrac{\pi k}{n+1}\right);$$
- $$P_n(x)=\textstyle\sum\limits_{0\le j\le n/2}{(-1)^j}C_{n-j}^jx^{n-2j};$$
- $$\prod\limits_{1\le k\le m}\cos\dfrac{k\pi}{2m+1}=\dfrac1{2^m}.$$
Devise and prove analogous equalities for the sequence of polynomials defined by the same relation (1), but starting with $P_0(x)=2$, $P_1(x)=x$.
A. Zelevinsky
Exploration
The recurrence
$$P_{n+1}(x)=xP_n(x)-P_{n-1}(x),\qquad P_0(x)=1,\quad P_1(x)=x$$
produces
$$P_2=x^2-1,\qquad P_3=x^3-2x,\qquad P_4=x^4-3x^2+1.$$
These are the Chebyshev polynomials of the second kind evaluated at $x/2$.
For the continued fraction, if
$$F_n=x-\frac1{F_{n-1}},\qquad F_1=x,$$
then
$$\frac{P_n}{P_{n-1}} =x-\frac{P_{n-2}}{P_{n-1}} =x-\frac1{P_{n-1}/P_{n-2}},$$
which reproduces the same recursion.
For the trigonometric identity, setting
$$Q_n(\phi)=\frac{\sin (n+1)\phi}{\sin\phi}$$
gives
$$Q_{n+1}=2\cos\phi,Q_n-Q_{n-1},$$
by the addition formula for sine. Since $Q_0=1$ and $Q_1=2\cos\phi$, the same recurrence appears after substituting $x=2\cos\phi$.
The factorization follows from the zeros of $\sin (n+1)\phi$:
$$\phi=\frac{k\pi}{n+1},\qquad 1\le k\le n.$$
The coefficient formula should come from expanding
$$P_n(x)=\frac{t^{n+1}-t^{-(n+1)}}{t-t^{-1}}, \qquad x=t+t^{-1}.$$
The most delicate step is deriving the explicit coefficient formula rigorously from the recurrence. A direct induction on
$$\sum_{j\le n/2}(-1)^j\binom{n-j}{j}x^{n-2j}$$
is the safest route.
For the second sequence, let
$$R_0=2,\qquad R_1=x,\qquad R_{n+1}=xR_n-R_{n-1}.$$
Computing,
$$R_2=x^2-2,\qquad R_3=x^3-3x.$$
The trigonometric model is
$$R_n(2\cos\phi)=2\cos(n\phi),$$
which are the Chebyshev polynomials of the first kind evaluated at $x/2$. Every identity above should have a parallel version obtained by replacing $\sin((n+1)\phi)/\sin\phi$ with $2\cos(n\phi)$.
Problem Understanding
This is a Type B problem.
The sequence $P_n$ is defined by a second order linear recurrence. We must prove six identities describing it through continued fractions, trigonometric functions, powers of a parameter $t$, its zeros, its explicit coefficients, and a trigonometric product. Then we must construct and justify analogous identities for the sequence satisfying the same recurrence but with initial values $P_0=2$, $P_1=x$.
The core difficulty is recognizing that all six statements are manifestations of the same recurrence. Once a closed trigonometric representation is established, the factorization and product formula follow naturally. The coefficient formula requires an independent verification that the proposed polynomial satisfies the defining recurrence and initial conditions.
Proof Architecture
The first lemma states that the continued fractions satisfy the same recurrence as the ratios $P_n/P_{n-1}$, hence they coincide.
The second lemma states that
$$Q_n(\phi)=\frac{\sin (n+1)\phi}{\sin\phi}$$
satisfies
$$Q_{n+1}=2\cos\phi,Q_n-Q_{n-1},$$
with the same initial values as $P_n(2\cos\phi)$.
The third lemma states that
$$F_n(t)=\frac{t^{n+1}-t^{-(n+1)}}{t-t^{-1}}$$
satisfies the same recurrence when $x=t+t^{-1}$.
The fourth lemma identifies the zeros of $P_n$ from the trigonometric formula and yields the factorization.
The fifth lemma proves the explicit coefficient formula by showing that the proposed sum satisfies the recurrence and the initial conditions.
The sixth lemma evaluates $P_{2m}(0)$ in two different ways, one from the recurrence and one from the factorization, producing the cosine product.
For the second sequence $R_n$, the corresponding trigonometric representation
$$R_n(2\cos\phi)=2\cos(n\phi)$$
generates all analogues.
The most delicate lemma is the coefficient formula, because matching the recurrence requires careful manipulation of binomial coefficients.
Solution
Define
$$P_0(x)=1,\qquad P_1(x)=x,\qquad P_{n+1}(x)=xP_n(x)-P_{n-1}(x).$$
For small values,
$$P_2=x^2-1,\qquad P_3=x^3-2x.$$
We prove the six identities.
For the first identity, let $F_n$ denote the continued fraction
$$F_n=x-\frac1{x-\frac1{\ddots-\frac1x}},$$
containing $n$ occurrences of $x$. Then
$$F_1=x,$$
and for $n\ge2$,
$$F_n=x-\frac1{F_{n-1}}.$$
We prove
$$F_n=\frac{P_n}{P_{n-1}}$$
for all $n\ge1$. The case $n=1$ is immediate. Assume
$$F_{n-1}=\frac{P_{n-1}}{P_{n-2}}.$$
Then
$$F_n =x-\frac{P_{n-2}}{P_{n-1}} =\frac{xP_{n-1}-P_{n-2}}{P_{n-1}} =\frac{P_n}{P_{n-1}},$$
by the defining recurrence. This proves (1).
For the second identity, define
$$Q_n(\phi)=\frac{\sin (n+1)\phi}{\sin\phi},$$
where $\sin\phi\ne0$. Using
$$\sin (n+2)\phi+\sin n\phi =2\cos\phi,\sin (n+1)\phi,$$
we obtain
$$Q_{n+1}=2\cos\phi,Q_n-Q_{n-1}.$$
Also,
$$Q_0=1,\qquad Q_1=2\cos\phi.$$
Hence the sequence $Q_n$ satisfies exactly the same recurrence and initial conditions as $P_n(2\cos\phi)$. By uniqueness of solutions of the recurrence,
$$P_n(2\cos\phi)=Q_n(\phi) =\frac{\sin (n+1)\phi}{\sin\phi}.$$
This proves (2).
For the third identity, let
$$x=t+t^{-1},$$
and define
$$G_n(t)=\frac{t^{n+1}-t^{-(n+1)}}{t-t^{-1}}.$$
A direct computation gives
$$(t+t^{-1})G_n-G_{n-1} =\frac{t^{n+2}-t^{-(n+2)}}{t-t^{-1}} =G_{n+1}.$$
Furthermore,
$$G_0=1,\qquad G_1=t+t^{-1}=x.$$
Thus $G_n=P_n(x)$. Multiplying by $t-t^{-1}$ yields
$$t^{n+1}-t^{-(n+1)} =\left(t-\frac1t\right) P_n!\left(t+\frac1t\right).$$
This proves (3).
For the fourth identity, formula (2) shows that
$$P_n(2\cos\phi)=0$$
exactly when
$$\sin (n+1)\phi=0, \qquad \sin\phi\ne0.$$
Hence the zeros are
$$x_k=2\cos\frac{k\pi}{n+1}, \qquad 1\le k\le n.$$
These numbers are distinct because
$$0<\frac{\pi}{n+1}<\cdots<\frac{n\pi}{n+1}<\pi$$
and $\cos$ is strictly decreasing on $(0,\pi)$.
Since $P_n$ has degree $n$ and leading coefficient $1$, it follows that
$$P_n(x) =\prod_{k=1}^{n} \left(x-2\cos\frac{k\pi}{n+1}\right).$$
This proves (4).
For the fifth identity, define
$$S_n(x) =\sum_{0\le j\le n/2} (-1)^j \binom{n-j}{j} x^{,n-2j}.$$
For $n=0$ and $n=1$,
$$S_0=1,\qquad S_1=x.$$
We verify the recurrence. Using
$$\binom{n-j}{j} +\binom{n-j}{j-1} =\binom{n+1-j}{j},$$
the coefficient of $x^{n+1-2j}$ in
$$xS_n-S_{n-1}$$
equals
$$(-1)^j\binom{n-j}{j} +(-1)^j\binom{n-j}{j-1} = (-1)^j\binom{n+1-j}{j}.$$
Therefore
$$xS_n-S_{n-1} = \sum_{0\le j\le (n+1)/2} (-1)^j \binom{n+1-j}{j} x^{,n+1-2j} =S_{n+1}.$$
Hence $S_n$ satisfies the same recurrence and initial conditions as $P_n$, so
$$P_n(x) = \sum_{0\le j\le n/2} (-1)^j \binom{n-j}{j} x^{,n-2j}.$$
This proves (5).
For the sixth identity, put $n=2m$ in the factorization:
$$P_{2m}(x) = \prod_{k=1}^{2m} \left(x-2\cos\frac{k\pi}{2m+1}\right).$$
Substituting $x=0$ gives
$$P_{2m}(0) = \prod_{k=1}^{2m} \left(-2\cos\frac{k\pi}{2m+1}\right).$$
The factors occur in pairs because
$$\cos\frac{(2m+1-k)\pi}{2m+1} = -\cos\frac{k\pi}{2m+1}.$$
Consequently,
$$P_{2m}(0) = (-1)^m4^m \prod_{k=1}^{m} \cos^2\frac{k\pi}{2m+1}.$$
From the recurrence,
$$P_0(0)=1,\qquad P_1(0)=0,$$
and
$$P_{n+1}(0)=-P_{n-1}(0).$$
Hence
$$P_{2m}(0)=(-1)^m.$$
Comparing the two expressions,
$$(-1)^m = (-1)^m4^m \prod_{k=1}^{m} \cos^2\frac{k\pi}{2m+1},$$
so
$$\prod_{k=1}^{m} \cos\frac{k\pi}{2m+1} = \frac1{2^m}.$$
This proves (6).
Now consider the sequence
$$R_0(x)=2,\qquad R_1(x)=x,\qquad R_{n+1}(x)=xR_n(x)-R_{n-1}(x).$$
Let
$$H_n(\phi)=2\cos(n\phi).$$
Since
$$2\cos((n+1)\phi) = 2\cos\phi\cdot2\cos(n\phi)-2\cos((n-1)\phi),$$
the sequence $H_n$ satisfies the same recurrence as $R_n(2\cos\phi)$, and
$$H_0=2,\qquad H_1=2\cos\phi.$$
Therefore
$$R_n(2\cos\phi)=2\cos(n\phi).$$
Using
$$t^n+t^{-n}=2\cos(n\phi) \qquad (t=e^{i\phi}),$$
one obtains
$$t^n+t^{-n} = R_n!\left(t+\frac1t\right).$$
The zeros are
$$2\cos\frac{(2k-1)\pi}{2n}, \qquad 1\le k\le n,$$
and therefore
$$R_n(x) = \prod_{k=1}^{n} \left( x-2\cos\frac{(2k-1)\pi}{2n} \right).$$
The coefficient formula becomes
$$R_n(x) = \sum_{0\le j\le n/2} (-1)^j \frac{n}{,n-j,} \binom{n-j}{j} x^{,n-2j},$$
which is verified exactly as above from the recurrence and initial values.
The continued fraction analogue is obtained from
$$\frac{R_n}{R_{n-1}} = x-\frac{R_{n-2}}{R_{n-1}},$$
giving the same finite continued fraction with the ratios $R_n/R_{n-1}$.
Thus every statement (1) through (6) has a parallel version for the sequence $R_n$, generated by replacing the trigonometric representation involving $\sin((n+1)\phi)/\sin\phi$ with the representation $2\cos(n\phi)$.
This completes the proof.
∎
Verification of Key Steps
The trigonometric representation depends on the identity
$$\sin((n+2)\phi)+\sin(n\phi) = 2\cos\phi,\sin((n+1)\phi).$$
Dividing by $\sin\phi$ is legitimate only when $\sin\phi\neq0$. This is exactly the condition that $\phi/\pi$ is not an integer. Omitting that condition would make the formula undefined.
For the factorization, one must verify that the roots obtained from
$$\sin((n+1)\phi)=0$$
are distinct. The values
$$\phi=\frac{k\pi}{n+1}$$
lie in $(0,\pi)$, and $\cos$ is strictly decreasing there. Without this check, one could not conclude that all $n$ roots are different and hence account for the full degree of $P_n$.
For the coefficient formula, the crucial calculation is the coefficient of $x^{n+1-2j}$ in $xS_n-S_{n-1}$. The contribution from $xS_n$ is
$$(-1)^j\binom{n-j}{j},$$
while the contribution from $-S_{n-1}$ is
$$(-1)^j\binom{n-j}{j-1}.$$
A sign error at this point would destroy the recurrence. The identity
$$\binom{n-j}{j} + \binom{n-j}{j-1} = \binom{n+1-j}{j}$$
produces exactly the coefficient required for $S_{n+1}$.
Alternative Approaches
A more conceptual approach starts from the characteristic equation
$$\lambda^2-x\lambda+1=0.$$
Let
$$\lambda=t,\qquad \lambda^{-1}=t^{-1}, \qquad x=t+t^{-1}.$$
Solving the recurrence directly gives
$$P_n(x) = \frac{t^{n+1}-t^{-(n+1)}}{t-t^{-1}},$$
and
$$R_n(x)=t^n+t^{-n}.$$
Every other identity follows from these formulas by straightforward algebra. The trigonometric identities arise after setting $t=e^{i\phi}$, the factorizations arise from locating the zeros, and the coefficient formulas arise from expanding the closed forms.
The approach used in the main proof stays closer to the structure of the problem. Each identity is derived directly from the recurrence, making the logical connection between the six statements completely transparent.