Proof that nonconstant polynomial cannot have the same value at all integer points

Question

I am reading the solution to the Project Euler problem 28 here, specifically the one under 'Deriving a non-iterative formula'. That solution first deduces the degree of the polynomial, and then constructs a polynomial for that degree. What I do not understand is why the differences method (used by the author) successfully finds the degree of the polynomial. Yes, I understand the intuition behind it. Taking the differences between two points is just short for rate of change AKA derivative, and of course if you take a derivative of a polynomial enough times you will get a constant. However how do I know that this works consistently? That is, how do I know there is not some nonconstant polynomial out there that gives the same points at f(0), f(1), f(2), f(3), f(4), and then goes to something else at f(5) and beyond? If it is impossible for a nonconstant polynomial (of degree 1 or greater) to have the same value at consecutive integer points (e.g., f(0), f(-1), etc), please prove.

Answer 1

Just subtract that constant from the polynomial to get a new one which is zero at an infinite number of integer points, then use the fundamental theorem of algebra. Alternatively, use the fact that differentiating a polynomial reduces its degree, so there is some $n$ such that its $n^{\text{th}}$ derivative is identically $0$. In the problem being discussed, the difference method works because the answer happens to be a polynomial, and to know this in advance requires a certain intuition. If instead the $k^{\text{th}}$ cell of the spiral had value $2^k$ then this method would not work.

Answer 2

The binomial polynomial $$ \binom xn=\frac{x(x-1)(x-2)\cdots(x-n+1)}{n!} $$ has the property that it takes the same value, $0$, at the $n$ consecutive integers $0,\cdots,n-1$, and beyond that, has the pleasant property that at $x=n$, it takes the value $1$. Defining $\binom x0$ to be the constant polynomial $1$ allows you to get a polynomial of degree $n$ taking any specified values whatever at $0,\cdots,n$ as a linear combination of the binomial polynomials. I think a simple inductive argument will demonstrate this.

EDIT: Let me be more complete. Let’s consider the set of polynomials of degree less than $n$, and for typographic convenience, let me write $C_k(x)=\binom xk$. Now the dimension of the space of polynomials of degree less than $n$ is $n$, spanned by $1,x,\cdots,x^{n-1}$, but another spanning set consists of all the $C_k$ for $0\le k<n$. You see this most clearly by noting that the degree of the polynomial $C_k$ is exactly $k$. Thus we can say, if $\deg(f)<n$, that there are coefficients $a_0,a_1,\cdots,a_{n-1}$, uniquely determined by $f$, such that $\,f=\sum_{k=0}^{n-1}a_kC_k$. Now use the difference operator $\Delta$: you’re using $(\Delta(f))(x)=f(x+1)-f(x)$. And use also the fact that $\Delta(C_k)=C_{k-1}$ and $\Delta(C_0)=0$. Now we can move ahead: $$ \begin{align} f&=a_0C_0+a_1C_1+\cdots a_{n-1}C_{n-1}\\ f(0)&=a_0\\ \Delta f&=a_1C_0+a_2C_1+\cdots a_{n-1}C_{n-2}\\ (\Delta f)(0)&=a_1\\ \Delta^2f&=a_2C_0+a_3C_1+\cdots a_{n-1}C_{n-3}\\ (\Delta^2 f)(0)&=a_2\\ \vdots\\ \Delta^{n-1}f&=a_{n-1}C_0=a_{n-1}\,. \end{align} $$ And that’s why the method of differences always works.