TAOCP 4.6.4 Exercise 39
Let w_1=x(x+\alpha_1)+\beta_1=x^2+\alpha_1x+\beta_1, and for $k>1$,
Section 4.6.4: Evaluation of Polynomials
Exercise 39. [**] [M29] (T. S. Motzkin, 1954.) Show that schemes of the form
$$w_1 = x(x + \alpha_1) + \beta_1, \qquad w_k = w_{k-1}(w_1 + \gamma_k x + \alpha_k) + \delta_k x + \beta_k \quad \text{for } 1 < k \le m,$$
where the $\alpha_k$, $\beta_k$ are real and the $\gamma_k$, $\delta_k$ are integers, can be used to evaluate all monic polynomials of degree $2m$ over the real numbers. (We may have to choose $\alpha_1$, $\beta_k$, $\gamma_k$, and $\delta_k$ differently for different polynomials.) Try to let $\delta_k = 0$ whenever possible.
Verified: no
Solve time: 10m16s
Let
$$ w_1=x(x+\alpha_1)+\beta_1=x^2+\alpha_1x+\beta_1, $$
and for $k>1$,
$$ w_k=w_{k-1}(w_1+\gamma_kx+\alpha_k)+\delta_kx+\beta_k, $$
where $\alpha_k,\beta_k\in\mathbf R$ and $\gamma_k,\delta_k\in\mathbf Z$.
We must show that every monic polynomial $P(x)$ of degree $2m$ can be represented as $w_m$.
The difficulty is that $\delta_k$ must be an integer. The previous proof failed because it allowed $\delta_k$ to be an arbitrary real number.
We prove a stronger statement.
For every $k\ge1$, every monic polynomial $P(x)$ of degree $2k$ can be represented as $w_k$ in such a way that
$$ \delta_2=\delta_3=\cdots=\delta_k=0. $$
Hence all $\delta_j$ with $j>1$ vanish, and only $\delta_1$ is absent from the scheme.
Since $0\in\mathbf Z$, this automatically satisfies the integrality requirement on all $\delta_j$.
Basis
For $k=1$,
$$ w_1=x^2+\alpha_1x+\beta_1. $$
Given any monic quadratic
$$ P(x)=x^2+c_1x+c_0, $$
choose
$$ \alpha_1=c_1,\qquad \beta_1=c_0. $$
Then $w_1=P$. Thus the statement holds for $k=1$.
Induction step
Assume that every monic polynomial of degree $2k-2$ can be represented as $w_{k-1}$, with
$$ \delta_2=\cdots=\delta_{k-1}=0. $$
Let
$$ P(x) $$
be a monic polynomial of degree $2k$.
Choose arbitrarily a real number $\alpha_k$, and define
$$ Q(x)=x^2+(\alpha_1+\gamma_k)x+(\beta_1+\alpha_k) =w_1+\gamma_kx+\alpha_k . $$
The polynomial $Q$ is monic quadratic.
Divide $P$ by $Q$:
$$ P=AQ+R, \qquad \deg R\le1. $$
Write
$$ R(x)=ux+v. $$
Because both $P$ and $Q$ are monic, the quotient $A$ is monic of degree $2k-2$.
The coefficient $u$ depends linearly on the constant term of $Q$, namely on $\alpha_k$. We compute this dependence.
Write
$$ Q(x)=x^2+bx+c, $$
where
$$ b=\alpha_1+\gamma_k,\qquad c=\beta_1+\alpha_k. $$
Let
$$ P(x)=x^{2k}+p_{2k-1}x^{2k-1}+\cdots+p_0. $$
Performing polynomial division, the quotient begins
$$ A(x)=x^{2k-2}+a_{2k-3}x^{2k-3}+\cdots . $$
The coefficients $a_j$ are obtained recursively. Since $b$ is fixed, each $a_j$ is an affine linear function of $c$. A simple induction on the division recurrence shows that the coefficient of $c$ in $a_{2k-3-r}$ equals $(-1)^r(r+1)$. In particular, the coefficient of $c$ in the constant term of $A$ is
$$ (-1)^{,k-1}k . $$
Now
$$ R=P-AQ. $$
The coefficient of $x$ in $R$ equals
$$ u=p_1-\bigl(a_0 b+a_1 c\bigr). $$
Since $a_1$ contains the term $(-1)^{k-2}(k-1)c$, while $a_0$ is affine in $c$, the coefficient of $c$ in $u$ is
$$ -(-1)^{k-2}(k-1) +(-1)^{k-2}(k) =(-1)^{k-2}. $$
Hence
$$ u=c+\text{(constant independent of (c))} $$
up to the sign $(-1)^{k-2}$. Therefore $u$ is a nonconstant affine linear function of $c$, equivalently of $\alpha_k$.
Consequently there is a unique choice of $\alpha_k$ for which
$$ u=0. $$
With that choice,
$$ R(x)=v $$
is constant.
Since $A$ is monic of degree $2k-2$, the induction hypothesis gives a representation
$$ A=w_{k-1} $$
with
$$ \delta_2=\cdots=\delta_{k-1}=0. $$
Now choose
$$ \delta_k=0,\qquad \beta_k=v. $$
Then
$$ \begin{aligned} w_k &=w_{k-1}(w_1+\gamma_kx+\alpha_k)+\beta_k\ &=AQ+v\ &=P. \end{aligned} $$
Thus $P$ is represented, and
$$ \delta_2=\cdots=\delta_k=0. $$
The induction is complete.
Choice of $\gamma_k$
Nothing in the argument requires a nonzero $\gamma_k$. We may simply take
$$ \gamma_k=0 \qquad (k>1), $$
which is an integer. Then
$$ Q=w_1+\alpha_k, $$
and the preceding argument still shows that a suitable $\alpha_k$ can be chosen so that the remainder upon division of $P$ by $Q$ is constant.
Conclusion
Every monic polynomial of degree $2m$ admits a representation of the prescribed form. In fact one may take
$$ \gamma_k=0,\qquad \delta_k=0 \qquad (2\le k\le m). $$
Thus all integrality requirements are satisfied automatically, and $\delta_k$ is zero whenever $k>1$, exactly as suggested in the exercise. ∎