32
$\begingroup$

I recently came up with this theorem:

For any complex polynomial $P$ degree $n$:

$$ \sum\limits_{k=0}^{n+1}(-1)^k\binom{n+1}{k}P(a+kb) = 0\quad \forall a,b \in\mathbb{C}$$

Basically, if $P$ is quadratic, $P(a) - 3P(a+b) + 3P(a+2b) - P(a+3b) = 0$ (inputs of $P$ are consecutive terms of any arithmetic sequence). This can be generalized to any other degrees.

  • Has this been discovered? If yes, what's the formal name for this phenomenon?
  • Is it significant/Are there important consequences of this being true?
  • Can this be generalized to non-polynomials?
$\endgroup$
  • 2
    $\begingroup$ I do not know if this have a name, but your theorem comes as a linear combination of the special case $P(x) = x^m$ where $0 \leq m \leq n$, and for the monomial case, I believe it is well known. I am still searching for a more suitable reference, but this page explains a bit: mathworld.wolfram.com/FiniteDifference.html $\endgroup$ – Hw Chu Sep 26 '18 at 0:49
  • $\begingroup$ For $b=1$, this follows from Theorem 1 and Theorem 2 in my post math.stackexchange.com/questions/1379172/… . (My argument is more or less the same as Steven Stadnicki's.) To get the case of general $b$, you can either generalize my argument, or you can apply my argument to the polynomial $Q$ (also of degree $n$) defined by $Q\left(x\right) = P \left(a+xb\right)$. $\endgroup$ – darij grinberg Sep 26 '18 at 2:02
  • 1
    $\begingroup$ My answer here has a reference to an article by Gould that has a very extensive list of references on this result, which goes back to Euler. $\endgroup$ – Chappers Sep 26 '18 at 15:03
  • $\begingroup$ What specific field of math is this? I want to learn it. $\endgroup$ – clathratus Oct 2 '18 at 3:22
  • $\begingroup$ @clathratus I'm not sure, tbh. I guess it's algebra, since it involves polynomials (something you learn in Algebra class at high school), and also because most techniques I used to prove this are algebraic manipulations (i.e., divide both sides by something, etc.). I hope someone else can give you a definite answer. $\endgroup$ – Felix Fourcolor Oct 2 '18 at 5:02
33
$\begingroup$

In brief: this is well-known, but definitely important.

It's easiest to write this in terms of the finite difference operator $\Delta$: $\Delta P(x)=P(x+1)-P(x)$. You use $P(x+b)$ instead of $P(x+1)$, but it's easy to see that these two things are equivalent; to keep things consistent with your notation, I'll write $\Delta_b$ for your operator.

The most important feature of the $\Delta_b$ operator is how it affects the degree of a polynomial:

Theorem: for any nonconstant polynomial $P(x)$, the degree of $\Delta_b P(x)$ is one less than the degree of $P(x)$.

Proof outline: Note that the degree of $\Delta_b P(x)$ is no greater than the degree of $P(x)$. Now, write $P(x) = a_dx^d+Q(x)$, where $Q(x)$ is a polynomial of degree $d-1$ or less. Then $P(x+b) =a_d(x+b)^d+Q(x+b)$, so $\Delta_b P(x) = a_d\left((x+b)^d-x^d\right)+\Delta_b Q(x)$; by the binomial theorem $(x+b)^d=x^d+{d\choose 1}bx^{d-1}+\ldots$, so $(x+b)^d-x^d={d\choose 1}bx^{d-1}+\ldots$ is a polynomial of degree at most $d-1$, and thus $\Delta_bP(x)$ is the sum of two polynomials of degree at most $d-1$ (namely, $a_d\left((x+b)^d-x^d\right)$ and $\Delta_b Q(x)$), so it's of degree at most $d-1$ itself.

(It's slightly more challenging to prove that the degree of $\Delta_bP(x)$ is exactly $d-1$ when $b \neq 0$, but this can also be shown.)

Why does this matter? Because it can be shown by induction that your sum is exactly the result of applying the $\Delta_b$ operator $d+1$ times, where $d$ is the degree of the polynomial; since each application of $\Delta_b$ reduces the degree by one, then $(\Delta_b)^dP(x)$ is a polynomial of degree zero — a constant — and thus $(\Delta_b)^{d+1}P(x)$ will be identically zero. This is exactly your identity.

Now, you may know that the derivative of a polynomial of degree $d$ is also a polynomial of degree $d-1$. It turns out that this isn't a coincidence; $\Delta$ is very similar to a derivative in many ways, with the Newton polynomials ${x\choose d}=\frac1{d!}x(x-1)(x-2)\cdots(x-d)$ playing the role of the monomial $x^d$ with respect to the derivative. For more details, I suggest starting with Wikipedia's page on finite difference calculus.

In fact, we can also prove the converse (and this answers the question about generalizing to non-polynomials in the negative). I'll work in terms of $\Delta$, rather than $\Delta_b$, but again all the results generalize readily.

Note that $\Delta^n P(x)$ only depends on the values of $P(x+i)$ for $i$ an integer between $0$ and $n$; thus, a function can take arbitrary values for $0\lt x\lt1$ and still satisfy the identity; we can't say much about general points. However, it does constrain the values at integers:

Theorem: suppose that $\Delta^{d+1}f(x)\equiv 0$ identically. Then there exists a polynomial $P(x)$ of degree $d$ such that $f(n)=P(n)$ for all integers $n$.

The proof works by induction. For simplicity's sake, I'll consider all functions as being on $\mathbb{Z}$ now, and not consider non-integer values at all. Note first of all that if $\Delta f(x)=g(x)$, then $f(n)=f(0)+\sum_{i=0}^{n-1}g(i)$. (Proof by induction: the case $n=1$ is true by definition, since $g(0)=\Delta f(0)=f(1)-f(0)$ implies that $f(1)=f(0)+g(0)$. Now, assuming it's true for $n=k$, at $n=k+1$ we have $f(k+1)=f(k)+g(k)$ $=f(0)+\sum_{i=0}^{k-1}g(i)+g(k)$ $=f(0)+\sum_{i=0}^kg(i)$.) In particular, if $\Delta f(x)\equiv 0$ identically, then $f(n)=f(0)$ for all integers $n$; $f()$ is constant on $\mathbb{Z}$.

This gives us the base case for our induction; to induct we just need to show that if $\Delta f(x)$ is a polynomial of degree $d$, then $f(x)$ is polynomial of degree $d+1$. But suppose for concreteness that $\Delta f(x)=P(x)=\sum_{i=0}^da_ix^i$. Then $f(n)=f(0)+\sum_{k=0}^{n-1}P(k)$ $=f(0)+\sum_{k=0}^{n-1}\left(\sum_{i=0}^da_ik^i\right)$ $=f(0)+\sum_{i=0}^da_i\left(\sum_{k=0}^{n-1}k^i\right)$. Now, for each $i$ the sum $\sum_{k=0}^{n-1}k^i$ in parentheses in this last expression is known to be a polynomial of degree $i+1$ (see e.g. https://en.wikipedia.org/wiki/Faulhaber%27s_formula ), so the whole expression is a polynomial of degree $d+1$, as was to be proved.

$\endgroup$
  • $\begingroup$ "this is well-known, but definitely important." Did you mean this particular theorem, or the idea of finite difference in general? $\endgroup$ – Felix Fourcolor Sep 26 '18 at 4:47
  • 2
    $\begingroup$ @FelixFourcolor Sort of both - the idea of finite differences in the broad, but also particularly this consequence that the difference operator behaves like a derivative especially with respect to polynomials (and that therefore the n+1st difference is zero, which is your theorem). It's used, for instance, in building up interpolating polynomials. $\endgroup$ – Steven Stadnicki Sep 26 '18 at 5:20
  • $\begingroup$ Would you happen to know why I got those down-votes on my answer below with no explanation added? It seems to me that I have a perfectly valid formal power series proof. Maybe you can advise here. $\endgroup$ – Marko Riedel Sep 26 '18 at 15:04
  • $\begingroup$ @MarkoRiedel I'm afraid I don't; I wasn't one of the downvoters and it looks broadly sensible to me. It might just be a matter of a gap in levels between the question and the proof, but I wouldn't expect that to garner quite so many downvotes in and of itself. $\endgroup$ – Steven Stadnicki Sep 26 '18 at 15:39
  • 1
    $\begingroup$ @FelixFourcolor I'll try to amend my answer to address that; the short version is that your conditions impose no restrictions on the function's values from e.g. $0$ to $b$, but force the function to be 'polynomial at multiples of $b$'. I'll add the proof of that (along with a clearer definition) in my answer. $\endgroup$ – Steven Stadnicki Oct 2 '18 at 21:25
2
$\begingroup$

What you wrote is the finite difference operator of order $n+1$, acting on $P$, $$ \sum\limits_{k=0}^{n+1}(-1)^k\binom{n+1}{k}P(a+kb) =\Delta^{n+1} P(a+kb).$$

Notice that by linearity it suffices for the property to hold for all monomials $k^m, m\le n$ and it is easily explained by the fact that the first order difference of a polynomial is a polynomial of degree one less.

$$(k+1)^m-k^m=k^m+mk^{m-1}+\cdots-k^m.$$


Illustration ($n=3$):

$$\Delta^4 k^m=((4^m-3^m)-(3^m-2^m))-((3^m-2^m)-(2^m-1^m)) \\-((3^m-2^m)-(2^m-1^m))-((2^4-1^m)-(1^4-0^m)) \\=4^m-4\cdot3^m+6\cdot2^m-4\cdot1^m+0^m.$$ and $$\begin{matrix} 1&&1&&1&&1&&1 \\&0&&0&&0&&0 \\&&0&&0&&0 \\&&&0&&0 \\&&&&0 \end{matrix}$$

$$\begin{matrix} 0&&1&&2&&3&&4 \\&1&&1&&1&&1 \\&&0&&0&&0 \\&&&0&&0 \\&&&&0 \end{matrix}$$

$$\begin{matrix} 0&&1&&4&&9&&16 \\&1&&3&&5&&7 \\&&2&&2&&2 \\&&&0&&0 \\&&&&0 \end{matrix}$$

$$\begin{matrix} 0&&1&&8&&27&&64 \\&1&&7&&19&&37 \\&&6&&12&&18 \\&&&6&&6 \\&&&&0 \end{matrix}$$


Final remark:

On can show that $\Delta_{n+1}k^{n+1}=(-1)^nn!$, so that for a polynomial of degree $n+1$ the sum is

$$(-1)^nn!p_{n+1}b^{n+1},$$ independently of $a$.

$\endgroup$
  • $\begingroup$ You don't need to include "illustrations", as I was the one who discovered this phenomenon myself, I must have known it. Instead, you could talk more about your final remark and maybe a sketch of proof for it. For now, your answer brings very limited new information to the table. That's the reason for my downvote. $\endgroup$ – Felix Fourcolor Oct 4 '18 at 6:20
  • 2
    $\begingroup$ @FelixFourcolor: posting such a naive question made me think you needed simple explanations. Sorry to have disturbed you. $\endgroup$ – Yves Daoust Oct 4 '18 at 7:11
1
$\begingroup$

This result is known and was demonstrated by a student named Ruiz.

Here's the reference :

Sebastián Martín Ruiz, An Algebraic Identity Leading to Wilson's Theorem, The Mathematical Gazette, 80 (489) 579-582 (Nov. 1996).

You accesss to it at JSTOR : http://www.jstor.org/stable/3618534

$\endgroup$
0
$\begingroup$

This is not a new result. What you wrote is the formula for the $n$-th order forward difference and can be found even on Wikipedia.

I will show a representation formula which is valid for $C^n(\mathbb R)$ functions, not just polynomials. The same can be found also here.

The key point is that finite differences and derivatives commute: $D\Delta_h=\Delta_hD$.

For $f\in C^1(\mathbb R)$ you can compute $$ \frac1h\Delta_h[f](x) = \frac{f(x+h)-f(x)}h = \frac1h \int_0^h D[f](x+x_1) \,dx_1 $$

For $f\in C^n(\mathbb R)$, iterating the above formula, you get $$ \begin{split} \frac1{h^n}\Delta_h^n[f](x) &= \frac{\frac1{h^{n-1}}\Delta_h^{n-1}[f](x+h) - \frac1{h^{n-1}}\Delta_h^{n-1}[f](x)} {h} \\ &= \frac1h \int_0^h \frac1{h^{n-1}}D\Delta_h^{n-1}[f](x+x_1) \,dx_1 \\ &= \frac1{h^2} \int_0^h \int_0^h \frac1{h^{n-1}} D^2\Delta_h^{n-2}[f](x+x_1+x_2) \,dx_1dx_2 \\ &= \,\cdots \\ &= \frac1{h^n} \int_0^h\dotsi\int_0^h D^n[f](x+x_1+\dotsb+x_n) \,dx_1\dotsm dx_n . \end{split} $$

The last integral is a weighted average of $D^n[f]$ over the segment $[x,x+nh]$. More precisely, let $X_1,\dotsc,X_n\sim\mathrm{Uniform}(0,h)$ be i.i.d. and $S=X_1+\dotsb+X_n$. Then the previous expression can be viewed as $$ \frac1{h^n}\Delta_h^n[f](x) = \mathbb{E}\left[D^n[f](S)\right] $$

The mean value theorem for integrals applies and tells us that there exists $x^*\in(x,x+nh)$ such that $$ \frac1{h^n}\Delta_h^n[f](x) = D^n[f](x^*). $$

Regarding your proposition, it follows trivially from the fact that if $P$ is a polynomial of degree $n$, then $D^{n+1}[P]=0$ identically, hence also $\Delta_h^{n+1}[P]=0$.

I can recommend reading at least Finite difference, Indefinite sum and Newton polynomial to learn about related material.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.