Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} \frac{f(t)}{n + 1}. \end{align} The proof follows by transforming it into the identity \begin{align} \sum_{j = 0}^{n} \sum_{k = j}^{n} (-1)^{k-j} \binom{k}{j} \binom{t}{k} f(j) = \sum_{k = 0}^{n} \binom{t}{k} (\Delta^{k} f)(0) = f(t), \end{align} where $\Delta^{k}$ is the $k^{\text{th}}$ forward difference operator. However, I'd like to prove the aforementioned identity directly, without recourse to the calculus of finite differences. Any hints are appreciated!


share|cite|improve this question
up vote 7 down vote accepted

This is just Lagrange interpolation for the values $0, 1, \dots, n$.

This means that after cancelling the denominators on the left you can easily check that the equality holds for $t=0, \dots, n$.

share|cite|improve this answer
Lagrange interpolation is derived using the Calculus of Finite Differences. Is there another way to see the identity directly? – user02138 May 4 '11 at 18:59
In my answer I said how you can prove Lagrange interpolation directly if you know that it is enough to check a polynomial identity of degree $m$ on $m+1$ places. Do you consider the last result to be equivalent to a proof using the Calculus of Finite Differences? – Phira May 4 '11 at 19:03
@02138: finite differences is only one way to derive a formula for the interpolating polynomial. At least, the form I am accustomed to sets up products of monomials $x-i$ and multiplies them by appropriate weights. So, objecting to 9325's answer as using finite differences isn't very justified. – J. M. May 4 '11 at 20:00
I think that it is possible to regard Lagrange interpolation as being tied to finite differences, but with that point of view a proof without finite differences becomes impossible by definition. (In particular, one has to view the mere act of dividing out zeros of polynomials as instances of finite differences.) – Phira May 4 '11 at 22:14
Agreed. All good comments. Thank you! – user02138 May 5 '11 at 14:04

I just ran across this question after working on this answer, and realized that the same method could be used here.

Notice that your equation is equivalent to $$ \sum_{j=0}^n(-1)^{n-j}\binom{n}{j}\frac{f(j)}{t-j}=\frac{n!f(t)}{t(t-1)(t-2)\dots(t-n)} $$ As long as $f$ is a polynomial of degree $n$ or less, apply the Heaviside Method for Partial Fractions to the right hand side to get the left hand side.

That is, to compute the coefficient of $\frac1{t-j}$ on the left hand side, multiply both sides by $t-j$ and set $t=j$. The right hand side becomes $$ \frac{n!f(j)}{j(j-1)(j-2)\dots1(-1)(-2)\dots(j-n)}=(-1)^{n-j}\binom{n}{j}f(j) $$

share|cite|improve this answer
(+1). This answer also has the feature that it explains some of the details of my answer below. – Marko Riedel Jun 17 '15 at 21:40
(+1) Nice answer. – Ishan Singh Jul 5 at 12:51

This can also be done with complex variables. Observe that we have by inspection that $$\sum_{j=0}^n (-1)^j {n\choose j} \frac{f(j)}{t-j} = (-1)^n \times n! \times \sum_{k=0}^n \mathrm{Res}_{z=k} \frac{f(z)}{t-z}\prod_{q=0}^n \frac{1}{z-q}.$$

This holds even if $f(t)$ vanishes at some positive integer in the range.

Recall that the residues sum to zero, so the right is equal to $$-(-1)^n \times n! \times \sum_{k\in\{\infty,t\}} \mathrm{Res}_{z=k} \frac{f(z)}{t-z}\prod_{q=0}^n \frac{1}{z-q}.$$

The residue at infinity of a function $h(z)$ is given by the formula $$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

which in the present case yields $$-\mathrm{Res}_{z=0} \frac{1}{z^2} \frac{f(1/z)}{t-1/z}\prod_{q=0}^n \frac{1}{1/z-q} \\ = -\mathrm{Res}_{z=0} \frac{z^{n+1}}{z^2} \frac{f(1/z)}{t-1/z}\prod_{q=0}^n \frac{1}{1-qz} \\ = -\mathrm{Res}_{z=0} z^n \frac{f(1/z)}{zt-1}\prod_{q=0}^n \frac{1}{1-qz}.$$

Note however that $f(z)$ has degree $m$ and we require that $n\ge m$ which means $f(1/z) z^n$ has no pole at zero and hence the residue at infinity is zero as well.

That leaves the residue at $z=t$ for a total contribution of $$-(-1)^n \times n! \times (-1)\times f(t)\times \prod_{q=0}^n \frac{1}{t-q} = (-1)^n f(t) \times n! \prod_{q=0}^n \frac{1}{t-q} \\ = (-1)^n f(t) \times n! \times \frac{1}{(n+1)!} {t\choose n+1}^{-1} \\ = (-1)^n \frac{f(t)}{n+1} {t\choose n+1}^{-1}$$ which was to be shown, QED.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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