TAOCP 4.6.4 Exercise 24

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 24. ▶ [**] [M24] Find values of $c$ and $\alpha_1$, $\beta_1$ satisfying the conditions of Theorem E, for the polynomial $u(x) = (x+7)(x^2+6x+4)(x^2+4x+5)(x+1)$. Choose these values so that $\beta_2 = 0$. Give two different solutions.

Verified: no
Solve time: 8m35s

Exercise 4.6.4.24 [**]

Find values of $c$ and $\alpha_1, \beta_1$ satisfying the conditions of Theorem E for

$$ u(x) = (x+7)(x^2 + 6x + 4)(x^2 + 4x + 5)(x+1), $$

so that $\beta_2 = 0$. Give two different solutions.

Step 1: Recall Theorem E

Theorem E (Pan, Section 4.6.4) states:

A polynomial of degree $n = 2m+2$ can be written in the form

$$ u(x) = (x+c) (x^2 + \alpha_1 x + \beta_1) (x^2 + \alpha_2 x + \beta_2), $$

where $\alpha_1, \beta_1$ are chosen, $c$ is a linear shift, and $\alpha_2, \beta_2$ are determined so that the decomposition reproduces the original polynomial.

Condition for $\beta_2 = 0$: The second quadratic must degenerate to $x(x + \alpha_2)$.

We must therefore find triples $(c, \alpha_1, \beta_1)$ such that, after factoring out $x+c$ and $x^2 + \alpha_1 x + \beta_1$, the remaining polynomial is of the form $x(x + \alpha_2)$.

Step 2: Express $u(x)$ in standard degree-6 form

The given polynomial is

$$ u(x) = (x+7)(x^2 + 6x + 4)(x^2 + 4x + 5)(x+1). $$

Multiply it out partially to clarify structure:

$$ (x+7)(x+1) = x^2 + 8x + 7, $$

$$ (x^2 + 6x + 4)(x^2 + 4x + 5) = x^4 + 10x^3 + 33x^2 + 50x + 20. $$

Multiply the quadratics with the linear factors:

$$ u(x) = (x^2 + 8x + 7)(x^4 + 10x^3 + 33x^2 + 50x + 20). $$

Perform the multiplication carefully:

  • $x^2 \cdot (x^4 + 10x^3 + 33x^2 + 50x + 20) = x^6 + 10x^5 + 33x^4 + 50x^3 + 20x^2$
  • $8x \cdot (x^4 + 10x^3 + 33x^2 + 50x + 20) = 8x^5 + 80x^4 + 264x^3 + 400x^2 + 160x$
  • $7 \cdot (x^4 + 10x^3 + 33x^2 + 50x + 20) = 7x^4 + 70x^3 + 231x^2 + 350x + 140$

Add the coefficients:

$$ \begin{aligned} x^6 &: 1 \ x^5 &: 10 + 8 = 18 \ x^4 &: 33 + 80 + 7 = 120 \ x^3 &: 50 + 264 + 70 = 384 \ x^2 &: 20 + 400 + 231 = 651 \ x^1 &: 160 + 350 = 510 \ x^0 &: 140 \end{aligned} $$

Thus

$$ \boxed{u(x) = x^6 + 18x^5 + 120x^4 + 384x^3 + 651x^2 + 510x + 140}. $$

This confirms degree 6, so any decomposition must respect this degree.

Step 3: Set up the decomposition

We aim for

$$ u(x) = (x+c)(x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x + \beta_2), $$

with $\beta_2 = 0$, i.e., second quadratic $x(x + \alpha_2)$.

Then the decomposition is

$$ u(x) = (x+c)(x^2 + \alpha_1 x + \beta_1) x (x + \alpha_2) = x(x+c)(x^2 + \alpha_1 x + \beta_1)(x + \alpha_2). $$

Now the degree matches: $1 + 1 + 2 + 1 = 5$. Wait, we need degree 6.

Check: $(x+c)(x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x)$ has degree $1 + 2 + 2 = 5$. We need degree 6.

Hence, the correct decomposition according to Theorem E is:

$$ \boxed{u(x) = (x+c)(x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x + \beta_2)}, \quad \deg(u) = 6. $$

Then $\deg(x^2 + \alpha_2 x + \beta_2) = 2$, so $\beta_2 = 0$ means $x^2 + \alpha_2 x$, degree 2. Correct.

So the correct form is

$$ u(x) = (x+c)(x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x), \quad \beta_2 = 0. $$

Step 4: Compare coefficients

Let

$$ (x+c)(x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x) = u(x) = x^6 + 18x^5 + 120x^4 + 384x^3 + 651x^2 + 510x + 140. $$

Expand step by step:

  1. Multiply the quadratics first:

$$ (x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x) = x^4 + (\alpha_1 + \alpha_2)x^3 + (\alpha_1 \alpha_2 + \beta_1)x^2 + \beta_1 \alpha_2 x. $$

  1. Multiply by $x + c$:

$$ \begin{aligned} (x + c)(x^4 + (\alpha_1 + \alpha_2)x^3 + (\alpha_1 \alpha_2 + \beta_1)x^2 + \beta_1 \alpha_2 x) &= x^5 + (\alpha_1 + \alpha_2)x^4 + (\alpha_1 \alpha_2 + \beta_1)x^3 + \beta_1 \alpha_2 x^2 \ &\quad + c x^4 + c(\alpha_1 + \alpha_2)x^3 + c(\alpha_1 \alpha_2 + \beta_1)x^2 + c \beta_1 \alpha_2 x \ &= x^5 + (\alpha_1 + \alpha_2 + c)x^4 + (\alpha_1 \alpha_2 + \beta_1 + c(\alpha_1 + \alpha_2))x^3 \ &\quad + (\beta_1 \alpha_2 + c(\alpha_1 \alpha_2 + \beta_1)) x^2 + c \beta_1 \alpha_2 x \end{aligned} $$

Check degrees: Highest degree is 5? But $u(x)$ is degree 6.

We forgot $x^2 \cdot x = x^3$? Let's carefully redo:

$$ (x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x + \beta_2) = x^4 + (\alpha_1 + \alpha_2)x^3 + (\alpha_1 \alpha_2 + \beta_1 + \beta_2)x^2 + (\alpha_2 \beta_1 + \alpha_1 \beta_2)x + \beta_1 \beta_2 $$

Now set $\beta_2 = 0$:

$$ (x^2 + \alpha_1 x + \beta_1)(x^2 + \alpha_2 x) = x^4 + (\alpha_1 + \alpha_2)x^3 + (\alpha_1 \alpha_2 + \beta_1)x^2 + (\alpha_2 \beta_1) x $$

Multiply by $x + c$:

\begin{aligned} (x+c)(x^4 + (\alpha_1 + \alpha_2)x^3 +