## How is Horner’s method linked to synthetic division?

Horner’s method is a computationally efficient algorithm for evaluating a polynomial at a certain point or value.

But how does Horner’s method link to synthetic division? The process of Horner’s method gives coefficients that are identical in the synthetic division. But why? does Horner’s algorithm give the coefficients of the quotient of the polynomial divided by the linear division that it is evaluated at.

http://en.wikipedia.org/wiki/Horner_scheme

## Description of the algorithm

Given the polynomial

where are real numbers, we wish to evaluate the polynomial at a specific value of , say .

To accomplish this, we define a new sequence of constants as follows:

$b_n := a_n$

$b_{n-1} :=a_{n-1}+b_n x_0$

$b_0 :=a_0+b_1 x_0$

Then is the value of .

To see why this works, note that the polynomial can be written in the form

Thus, by iteratively substituting the into the expression,

$p(x_0)=a_0+x_0(a_1+x_0(a_2+...+x_0(a_{n-1}+b_n x_0)...))$

$=a_0+x_0(a_1+x_0(a_2+...+x_0(b_{n-1})...)) = ... =a_0+x_0(b_1) =b_0.$