In arguing about the properties of algorithms involving a loop, it is often useful to think in terms of a loop invariant: something that you expect to be true after each iteration of the loop. Then, the principle is: if you have a loop where some proposition $P$ related to the current state is true before starting execution of the loop; and for each iteration of the loop, if before the loop body $P$ is true, then after the loop body $P$ is true; then, after the loop terminates, $P$ is still true.
In this algorithm, let us first expand the "for" statement a bit in order to simplify the analysis:
- function horner(A, x):
- $p := A_n$
- $i := n$
- while $i > 0$:
- $i := i - 1$
- $p := p \cdot x + A_i$
- return $p$
Then the loop invariant we will use is: $$p = \sum_{j=0}^{n-i} A_{n-j} x^{n-i-j} = A_n x^{n-i} + A_{n-1} x^{n-i-1} + \cdots + A_{i+1} x + A_i.$$
Just before the "while" statement starts executing, we indeed have $i = n$ and $p = \sum_{j=0}^0 A_{n-j} x^{n-i-j} = A_n$. Now, when executing the body, let us suppose at the start that $i = i_s$ and $p = A_n x^{n-i_s} + A_{n-1} x^{n-i_s-1} + \cdots + A_{i_s}$. (Here, $i_s$ will be used for the "start" value of $i$ in order to avoid confusion due to the changing value of $i$.) Then after the loop body executes, we will have $i = i_s - 1$ and
$$p = (A_n x^{n-i_s} + A_{n-1} x^{n-i_s-1} + \cdots + A_{i_s}) x + A_{i_s-1} = \\
A_n x^{n-i_s+1} + A_{n-1} x^{n-i_s} + \cdots + A_{i_s} x + A_{i_s-1} = \\
A_n x^{n-i} + A_{n-1} x^{n-i-1} + \cdots + A_{i+1} x + A_i.$$
Therefore, the condition will indeed be preserved by each iteration of the loop. But then, after the loop exits, we will have $i = 0$, so $p = A_n x^n + A_{n-1} x^{n-1} + \cdots + A_1 x + A_0$ and the next "return" statement will return the correct value.
(Incidentally, if you're designing an algorithm, then the concept of loop invariant can also be useful in reverse: to come up with a description of exactly what state you want the variables to be in at the end of each execution of the loop body. Then keeping that in mind will aid in avoiding bugs that are due to "jumping the gun", so to speak, and prematurely performing calculations that really belong to the next iteration.)
The polynomial $a_1 + a_2x + \cdots + a_nx^{n-1}$ that you found has root $x=1$ and so, by the factor theorem, has a factor of $x-1$. Thus
$$p(x) = x(x-1)(b_0 + b_1x + \cdots + b_{n-2}x^{n-2})$$ for some $b_0, \dots , b_{n-2}$. But because
$$a_1 + \cdots + a_nx^{n-1} = (x-1)(b_0 + b_1x + \cdots + b_{n-2}x^{n-2}) = 0$$ for all $x\ne 0$, and $x-1=0$ only for $x=1$, this shows us that $b_0 + \cdots + b_{n-2}x^{n-2}$ is zero for all $x\ne 0, 1$. In particular, it is zero at $x=2$. Hence
$$p(x) = x(x-1)(x-2)(c_0 + \cdots + c_{n-3}x^{n-3})$$
Continuing on in this way you'll find that
$$p(x) = x(x-1)(x-2)\cdots (x-n)(d_0)$$ for some constant $d_0$. Now we know that $p(n+1) = 0$ and we also know that none of the linear factors $x, x-1, \dots, x-n$ is zero at $x=n+1$. Hence $d_0 = 0$.
But what does this have to do with the numbers $a_1, \dots, a_n$? Well we can recover the form $a_0 + a_1x + \cdots a_nx^n$ by multiplying through all of the factors of $p$. But it's clear that the highest power of $p$ will be $d_0x^n$. So $d_0 = a_n = 0$. Hence $p$ is in fact the polynomial $a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$.
Applying the exact same argument to this new representation of $p$ shows that $a_{n-1}=0$, and then $a_{n-2}=0$, etc.
Of course I haven't really given the above as a polished proof, but I'm sure you can handle that.
Best Answer
You assume the $n$th derivative of $a_n x^n$ is $n! a_n$.
You want to prove the $(n+1)$st derivative of $a_{n+1} x^{n+1}$ is $(n+1)! a_{n+1}$. The $(n+1)$st derivative can be obtained by taking one derivative, and then taking the $n$th derivative.
If you take one derivative, you have $(n+1) a_{n+1} x^n$. Then applying the statement in my first sentence with $a_n:= (n+1)a_{n+1}$ shows that the $n$th derivative of this is $n! a_n = n! (n+1) a_{n+1} = (n+1)! a_{n+1}$.