# Proof

(related to Algorithm: Horner Scheme)

We want to show that the Horner scheme algorithm $$\mathtt{horner}(n,x,a)$$ correctly calculates the value $$p(x)$$ of the polynomial over the field $$F$$ (e.g. a polynomial over the field of complex numbers)

$p(z):=a_nz^n + \ldots + a_1z + a_0\quad\quad( * )$ at a specific value $$x\in F$$, where $$a_0,a_1,\ldots,a_n\in F$$ and where the degree of the polynomial is $$n$$ (i.e. $$a_n\neq 0$$). By applying the axiom of distributivity, we can transform $$( * )$$ into $\begin{array}{rcl} p(z)&=&a_nz^n + \ldots + a_1z + a_0\\ &=&(a_nz+a_{n-1})z^{n-1} + \ldots + a_1z + a_0\\ &=&((a_nz+a_{n-1})z+a_{n-2})z^{n-2} + \ldots + a_1z + a_0\\ &\vdots&\\ &=&((\ldots((a_nz+a_{n-1})z+a_{n-2})z^{n-2} + \ldots)z + a_1)z + a_0\quad\quad( ** ) \end{array}$

The formula $$( * * )$$ shows that by setting

$h_n:=a_n,\quad h_k:=h_{k+1}\cdot x + a_k,\quad k=n-1,\ldots,1,0,$

we get $$h_0=p(x)$$, which proves the correctness of the algorithm.

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Stummel, F; Hainer, K: "Praktische Mathematik", Teubner, 1982, 2nd Edition