(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.
