A Fundamental Relationship of Polynomials and Its Proof

Show more

1. Introduction

The “Fundamental Theorem of Algebra” states that a polynomial of degree n has n roots. Its first assertion in a different form is attributed to Peter Rothe in 1606 and later Albert Girard in 1629. Euler gave a clear statement of the theorem in a letter to Gauss in 1742 and at different times Gauss gave four different proofs (see [1] , p. 292-306).

A nearly as important property of a polynomial is the constancy of the n^{th}‑differences of its subsequent values. To clarify this point let us begin with some demonstrations. While it is customary to use polynomials with real coefficients, here a second-order polynomial with complex coefficients is considered first,

${P}_{2}\left(x\right)=\left(1+i\right){x}^{2}-3ix+2$ (1)

where $i=\sqrt{-1}$ is the imaginary unit. Taking a real starting point ${x}_{0}=-2$ and a real step value $s=1$ the following Table 1 of differences can be established for the subsequent values of the polynomial.

The first differences are computed by taking the differences of the subsequent values of the polynomial as in ${P}_{2}\left(-2\right)-{P}_{2}\left(-1\right)=\left(6+10i\right)-\left(3+4i\right)=3+6i$ .

Table 1. Second-order differences for a sample second-order polynomial.

The second differences are obtained similarly using the first difference values: $\left(3+6i\right)-\left(1+4i\right)=2+2i$ .

Expressing the first differences in terms of polynomial values ${P}_{2}\left(-2\right)-{P}_{2}\left(-1\right)=3+6i$ and ${P}_{2}\left(-1\right)-{P}_{2}\left(0\right)=1+4i$ , the first value of the second differences may be written as

$\begin{array}{l}\left[{P}_{2}\left(-2\right)-{P}_{2}\left(-1\right)\right]-\left[{P}_{2}\left(-1\right)-{P}_{2}\left(0\right)\right]\\ ={P}_{2}\left(-2\right)-2{P}_{2}\left(-1\right)+{P}_{2}\left(0\right)=2+2i\end{array}$ (2)

which is a particular form,
$n=2$ , of the general theorem presented in Section 2. The constant value
$2+2i$ of the second-differences can be calculated from the general expression
${\left(-1\right)}^{n}n\mathrm{!}{a}_{0}{s}^{n}$ where n is the degree of the polynomial and
${a}_{0}$ the coefficient of the n^{th}-order term. For this particular example
$n=2$ and
${a}_{0}=1+i$ hence the constant becomes
${\left(-1\right)}^{2}2!\left(1+i\right){1}^{2}=2+2i$ as found above.

Another example is now given for a third-order polynomial with real coefficients

${P}_{3}\left(x\right)=2{x}^{3}-{x}^{2}-3x+5$ (3)

In this example a complex starting point ${x}_{0}=1-i$ and a complex step value $s=-3+2i$ are used so that Table 2 of differences is constructed, where the constant value of the third-differences can be calculated from the general formula ${\left(-1\right)}^{n}n\mathrm{!}{a}_{0}{s}^{n}$ as ${\left(-1\right)}^{3}3!2{\left(-3+2i\right)}^{3}=-108-552i$ .

A direct connection with the finite-difference approximation of derivatives of a polynomial is of course possible. Finite-difference approximation of the third-derivative of a third-order polynomial is given by

${{P}^{\u2034}}_{3}\text{}\left(x\right)=\frac{{P}_{3}\left({x}_{0}+3s\right)-3{P}_{3}\left({x}_{0}+2s\right)+3{P}_{3}\left({x}_{0}+s\right)-{P}_{3}\left({x}_{0}\right)}{{s}^{3}}$ (4)

where s is the incremental step. If the third-order polynomial is defined as ${P}_{3}\left(x\right)={a}_{0}{x}^{3}+{a}_{1}{x}^{2}+{a}_{2}x+{a}_{3}$ its third-derivative is ${{P}^{\u2034}}_{3}\text{}\left(x\right)=6{a}_{0}$ . Now using this in (4) results in

${P}_{3}\left({x}_{0}\right)-3{P}_{3}\left({x}_{0}+s\right)+3{P}_{3}\left({x}_{0}+2s\right)-{P}_{3}\left({x}_{0}+3s\right)=-6{a}_{0}{s}^{3}$ (5)

which exactly corresponds to the tabulated constant of third-differences. A remarkable point is that while finite-difference approximations are typically formulated for real and relatively small incremental step sizes, for the general expression no such restrictions apply: the incremental step s may be complex and arbitrarily large while the result is always exact.

Table 2. Third-order differences for a sample third-order polynomial.

Finally, a possible application of (5) or its general form for an n^{th}-order polynomial, is its use as a recurrence formula for evaluating a given polynomial at equal intervals once the polynomial is evaluated at n distinct points. For instance for a third-order polynomial it is sufficient to know
${P}_{3}\left({x}_{0}\right)$ ,
${P}_{3}\left({x}_{0}+s\right)$ , and
${P}_{3}\left({x}_{0}+2s\right)$ to obtain
${P}_{3}\left({x}_{0}+3s\right)$ from (5). Then, by setting
${x}_{0}$ to
${x}_{0}+s$ in (5),
${P}_{3}\left({x}_{0}+4s\right)$ can be obtained from the same recurrence relationship and continuing in this manner gives
${P}_{3}\left({x}_{0}+5s\right)$ ,
${P}_{3}\left({x}_{0}+6s\right)$ , etc. with considerably less arithmetic operations compared to straightforward evaluation of polynomial.

2. Main Theorem and Proof

The main theorem which expresses the constancy of n^{th}-order differences for an n^{th}-order polynomial is stated first and then proven by the method of induction.

Theorem 1

For an n^{th}-order polynomial
${P}_{n}\left(x\right)={a}_{0}{x}^{n}+{a}_{1}{x}^{n-1}\cdots +{a}_{n-1}x+{a}_{n}$ with
${a}_{0}\ne 0$ the following relationship holds

$\underset{m=0}{\overset{n}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left(x+ms\right)={\left(-1\right)}^{n}n!{a}_{0}{s}^{n$ (6)

where $n\ge 1$ and ${a}_{j}$ 's, $x$ , $s\in \mathbb{R}$ or $\u2102$ .

Proof of Theorem 1. The base case: Setting $n=1$ in (6) results in

$\left(\begin{array}{c}1\\ 0\end{array}\right){P}_{1}\left(x\right)-\left(\begin{array}{c}1\\ 1\end{array}\right){P}_{1}\left(x+s\right)={(-1)}^{1}1!{a}_{0}{s}^{1}$ (7)

Substituting ${P}_{1}\left(x\right)={a}_{0}x+{a}_{1}$ and ${P}_{1}\left(x+s\right)={a}_{0}\left(x+s\right)+{a}_{1}$ gives

$\left({a}_{0}x+{a}_{1}\right)-\left[{a}_{0}\left(x+s\right)+{a}_{1}\right]=-{a}_{0}s$ (8)

which is correct.

The inductive step: Assuming that the statement (6) holds true for any integer n it is now proven that it also holds true for $\left(n+1\right)$ :

$\underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n+1}\left(x+ms\right)={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1$ (9)

${P}_{n+1}\left(\stackrel{\xaf}{x}\right)$ can be expressed in terms of ${P}_{n}\left(\stackrel{\xaf}{x}\right)$ as

${P}_{n+1}\left(\stackrel{\xaf}{x}\right)=\stackrel{\xaf}{x}{P}_{n}\left(\stackrel{\xaf}{x}\right)+{a}_{n+1}$ (10)

Letting $\stackrel{\xaf}{x}=x+ms$ in (10) and using it in (9) result in

$\begin{array}{l}{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n+1\\ m\end{array}\right)\left[\left(x+ms\right){P}_{n}\left(x+ms\right)+{a}_{n+1}\right]\\ ={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}\end{array}$ (11)

Since ${\sum}_{m=0}^{n+1}}{\left(-1\right)}^{m}\left(\begin{array}{c}n+1\\ m\end{array}\right)=0$ for any n (odd or even) the summation proportional to the constant ${a}_{n+1}$ vanishes, reducing (11) to

$\begin{array}{l}x{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n}\left(x+ms\right)+s{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n}\left(x+ms\right)\\ ={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}\end{array}$ (12)

Making use of ${\sum}_{m=0}^{n+1}}\left(\begin{array}{c}n+1\\ m\end{array}\right)={\displaystyle {\sum}_{m=0}^{n}}\left(\begin{array}{c}n\\ m\end{array}\right)+{\displaystyle {\sum}_{m=1}^{n+1}}\left(\begin{array}{c}n\\ m-1\end{array}\right)$ ( [2] , p. 882) in the first summation above results in

$\begin{array}{l}x\left[{\displaystyle \underset{m=0}{\overset{n}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left(x+ms\right)+{\displaystyle \underset{m=1}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m-1\end{array}\right){P}_{n}\left(x+ms\right)\right]\\ +s{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n}\left(x+ms\right)={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}\end{array}$ (13)

By re-defining the running index in the second summation (13) becomes

$\begin{array}{l}x\left[{\displaystyle \underset{m=0}{\overset{n}{\sum}}}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left(x+ms\right)+{\displaystyle \underset{m=0}{\overset{n}{\sum}}}{\left(-1\right)}^{m+1}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left[x+\left(m+1\right)s\right]\right]\\ +s{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n}\left(x+ms\right)={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}\end{array}$ (14)

Since x may be assigned to any value, substituting x + s in place of x in the base case (6) reveals that ${\sum}_{m=0}^{n}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left[x+\left(m+1\right)s\right]$ is too equal to the same quantity: ${\left(-\text{1}\right)}^{n}n!{a}_{0}{s}^{n}$ . Noting in the second summation in (14) that ${\left(-\text{1}\right)}^{m+\text{1}}=-{\left(-\text{1}\right)}^{m}$ renders the terms in square brackets zero. Thus, to complete the proof the remaining equality in the second line of (14) must be proven:

$s{\displaystyle \underset{m=0}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\left(\begin{array}{c}n+1\\ m\end{array}\right){P}_{n}\left(x+ms\right)={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}$ (15)

For m = 0 the first term of the summation in (15) is zero hence bringing no contribution. Therefore, we can start the summation from m = 1 without any error. Then, the summation may be expressed as

$\begin{array}{l}{\displaystyle \underset{m=1}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\left(\begin{array}{c}n+1\\ m\end{array}\right)\\ ={\displaystyle \underset{m=1}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}m\frac{\left(n+1\right)!}{\left(n+1-m\right)!m!}\\ ={\displaystyle \underset{m=1}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\frac{\left(n+1\right)!}{\left(n+1-m\right)!\left(m-1\right)!}\end{array}$

$\begin{array}{l}={\displaystyle \underset{m=1}{\overset{n+1}{\sum}}}{\left(-1\right)}^{m}\left(n+1\right)\frac{n!}{\left(n+1-m\right)!\left(m-1\right)!}\\ ={\displaystyle \underset{p=0}{\overset{n}{\sum}}}{\left(-1\right)}^{p+1}\left(n+1\right)\frac{n!}{\left(n-p\right)!p!}\\ =\left(n+1\right){\displaystyle \underset{p=0}{\overset{n}{\sum}}}{\left(-1\right)}^{p+1}(np)\end{array}$

where an obvious change of running index m = p + 1 has been implemented in the final stage. Employing the last expression obtained above after changing p to m for the summation of (15) results in

$s\left(n+1\right){\displaystyle \underset{m=0}{\overset{n}{\sum}}}{\left(-1\right)}^{m+1}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left[x+\left(m+1\right)s\right]={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}$ (16)

As indicated above, the main theorem may also be stated as ${\sum}_{m=0}^{n}{\left(-1\right)}^{m}\left(\begin{array}{c}n\\ m\end{array}\right){P}_{n}\left[x+\left(m+1\right)s\right]}={\left(-1\right)}^{n}n!{a}_{0}{s}^{n$ . Using this in (16) yields

$s\left(n+1\right)\left(-1\right){\left(-1\right)}^{n}n!{a}_{0}{s}^{n}={\left(-1\right)}^{n+1}\left(n+1\right)!{a}_{0}{s}^{n+1}$ (17)

which proves that the proposition holds true for (n + 1) as well. ☐