4
$\begingroup$

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ...

This set of identities can be written as

$${m+1\choose k}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}{m-i\choose k}\tag 1$$

or alternatively as

$$\sum_{i=0}^k(-1)^i{k\choose i}{m-i\choose k}=1$$

Interestingly, the form in $(1)$ suggests that every binomial coefficient can be written as a recurrence in only terms from its own line (ignoring the $k\choose i+1$ terms as "predetermined constants"):

$$a_{n+1}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}a_{n-i}$$

What is the best way to prove these identities hold in general? The proofs for $k=1,2,3$ were very straightforward with simple factorial expansion, but even induction doesn't seem to be working in the general case.

Also, do these identities have a name?

These identities appeared as I was considering the quantity

$$\frac{x^n+y^n}{x+y}\pmod{(x+y)^k}$$

$\endgroup$
  • $\begingroup$ @anorton: Quite clearly from context, $a_n = \binom{n}{k}$ (for some/any fixed $k$). $\endgroup$ – ShreevatsaR Jan 22 '15 at 5:19
  • $\begingroup$ @ShreevatsaR Oh wait... now I see where that came from. :) Thanks. $\endgroup$ – apnorton Jan 22 '15 at 5:21
  • 1
    $\begingroup$ it's a (yet another) form of Vandermonde's identity $\endgroup$ – Grigory M Jan 22 '15 at 12:48
  • $\begingroup$ @GrigoryM: I wondered about that, thanks for the good reference! $\endgroup$ – abiessu Jan 22 '15 at 20:28
  • $\begingroup$ So many good answers, how to choose... $\endgroup$ – abiessu Jan 22 '15 at 20:33
4
$\begingroup$

Here's an approach via generating functions (it is possible to make the proof shorter by avoiding them, but this was the straightforward approach without much cleverness).

If you have $$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$$ and $$B(x) = b_0 + b_1x + b_2 x^2 + b_3x^3 + \dots$$ (the objects $A(x)$ and $B(x)$ are called generating functions of the two sequences) then their product $$A(x)B(x) = C(x) = c_0 + c_1x + c_2x^2 + c_3x^3+\dots$$ satisfies $$c_n = \sum_{r = 0}^{n} a_r b_{n-r}.$$

When, for some fixed $k$, the sequences are $a_n = (-1)^n\binom{k}{n}$ and $b_n = \binom{n}{k}$, we have $$A(x) = \sum_{n=0}^{\infty}(-1)^n\binom{k}{n}x^n = (1 - x)^k $$

and $$B(x) = \sum_{n=0}^{\infty}\binom{n}{k}x^n = \frac{x^k}{(1-x)^{k+1}} $$ (see here; this is a good exercise) so that their product is $$C(x) = A(x)B(x) = (1-x)^k \frac{x^k}{(1-x)^{k+1}} = \frac{x^k}{1-x} = x^k(1 + x + x^2 + \dots)$$

for which we have, for $n \ge k$, $$1 = c_n = \sum_{r=0}^{n}a_{r} b_{n-r} = \sum_{r=0}^n (-1)^r \binom{k}{r}\binom{n-r}{k} = \sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k} $$ (as $\binom{k}{r} = 0$ for $r > k$) which is what you wanted to prove.

$\endgroup$
  • $\begingroup$ Very nice, thank you! $\endgroup$ – abiessu Jan 22 '15 at 20:28
  • $\begingroup$ Just for completeness, on deriving $B(x)$: note that $\sum_{n=0}^{\infty}\binom{n}{k}x^n = \sum_{n=k}^{\infty}\binom{n}{k}x^n = x^k\sum_{n=0}^{\infty}\binom{n+k}{k}x^n =x^k\sum_{n=0}^{\infty}(-1)^n\binom{-k-1}{n}x^n=x^k(1-x)^{-k-1}$ as $$\binom{-k-1}{n} = \frac{(-k-1)(-k-2)\cdots(-k-n)}{n!}=(-1)^n\frac{(n+k)\cdots(k+1)}{n!} =(-1)^n\binom{n+k}{k}.$$ $\endgroup$ – ShreevatsaR Jan 23 '15 at 15:17
2
$\begingroup$

As usual let $[m]=\{1,\ldots,m\}$; we’ll count the $k$-sized subsets of $[m]$ that are contained in $[k]$. On the one hand there is obviously exactly one such set, namely, $[k]$ itself. On the other hand, for each $i\in[k]$ let $A_i$ be the family of $k$-sized subsets of $[m]$ that do not contain $i$. For any $I\subseteq[k]$ we have

$$\left|\bigcap_{i\in I}A_i\right|=\binom{m-|I|}k\;,$$

so a straightforward inclusion-exclusion argument shows that

$$\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{m-i}k$$

and hence that

$$1=\binom{m}k-\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=0}^k(-1)^i\binom{k}i\binom{m-i}k\;.$$

$\endgroup$
  • $\begingroup$ Another example where I wish I could have multiple "accept" options $\endgroup$ – abiessu Jan 23 '15 at 2:41
  • $\begingroup$ @abiessu: :-) You got a bit of everything this time. It's good, though: it makes it more useful to future readers who run across it. $\endgroup$ – Brian M. Scott Jan 23 '15 at 2:56
1
$\begingroup$

Here is the usual complex variables proof. Suppose we seek to show that $$\sum_{k=0}^n {n\choose k} (-1)^k {m-k\choose n} = 1$$ Introduce the integral representation $${m-k\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-k}}{z^{n+1}} \; dz.$$ This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \sum_{k=0}^n {n\choose k} (-1)^k \frac{1}{(1+z)^k}\; dz$$ or $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \left(1-\frac{1}{1+z}\right)^n \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \left(\frac{z}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-n}}{z} \; dz.$$

Now this evaluates to one by inspection, since we have an ordinary binomial when $m\ge n$ and a Newton binomial which starts at one when $m<n.$ (Observe that we need the constant coefficient.)

$\endgroup$
  • $\begingroup$ Very nice twist! $\endgroup$ – abiessu Jan 23 '15 at 2:41
1
$\begingroup$

For completeness, I did manage to create an inductive argument for this identity, though it is nowhere near the simplicity and elegance of the others here. I have also found a much simpler argument using finite differences; I'll leave the induction argument intact below the argument by polynomial theory:

Let $p(x)$ be a given integer-valued polynomial of degree $d$. The $n$th forward finite difference is given by

$$\Delta_p^n(x)=\sum_{i=0}^n(-1)^i{n\choose i}p(x+i)$$

If $n=d$ we get a constant, namely, the leading coefficient of $p(x)$ as taken in binomial form, i.e., $p(x)=\sum_ia_i{x\choose i}$. The formula stated in the question is an immediate consequence of these facts, taking $p(x)=\binom xn$.

Here is the proof by induction for anyone who might be interested:

For proof of $(1)$, use strong induction and start with $\binom {n+1}1 = 1 + \sum_{i=0}^{1-1}(-1)^i{k\choose i+1}{n-i\choose k} = 1+\binom n1 = n+1$. Assuming for $k = q$, we get

$${n+1\choose q} = 1+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{n-i\choose q}$$

Establishing a base-case for $k=q+1$ is a matter of considering

$${q+2\choose q+1}=q+2 = 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{q+1-i\choose q+1}=1+q+1 = q+2$$

after which we again make an assumption that our formula holds, this time for $n=r, r\ge q+1$: ${r+1\choose q+1}=1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}$. All that remains is to test the formula for $n=r+1$:

$$\begin{align}{r+2\choose q+1} &= 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\\ &= {r+1\choose q+1}+{r+1\choose q}\end{align}$$

By strong induction, we can use the formulas for $r+1\choose q+1$ and $r+1\choose q$ and write

$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{r-i\choose q}\\ &=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}\right)\end{align}$$

This is a bit messy, but it works out well:

$$\begin{align}{q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}&={q+1\choose i+1}{r-i\choose q+1}+\left[{q+1\choose i+1}-{q\choose i}\right]{r-i\choose q}\\ &={q+1\choose i+1}\left[{r-i\choose q+1}+{r-i\choose q}\right]-{q\choose i}{r-i\choose q}\\ &={q+1\choose i+1}{r-i+1\choose q+1}-{q\choose i}{r-i\choose q}\end{align}$$

Going in reverse, we now have

$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r+1-i\choose q+1}-{q\choose i}{r-i\choose q}\right)\\ &=2+(-1)^q{r-q+1\choose q+1}-(-1)^q{r-q\choose q}+\sum_{i=0}^{q-1}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q-1}(-1)^i{q\choose i}{r-i\choose q}\\ &=2+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q}(-1)^i{q\choose i}{r-i\choose q}\\ &=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1-\sum_{i=1}^{q}(-1)^i{q\choose i}{r-i\choose q}\\ &=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1+\sum_{j=0}^{q-1}(-1)^j{q\choose j+1}{r-j-1\choose q}\\ {r+2\choose q+1}&=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\end{align}$$

Note that the last step follows from strong induction due to the original formula (with $r\ge q+1$)

$$\binom rq = 1+\sum_{i=0}^{q-1}{q\choose i+1}{r-1-i\choose q}$$

$\endgroup$
1
$\begingroup$

$$\begin{align} \sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose k} &=\sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose m-k-i}\\ &=\sum_{i=0}^k (-1)^i{k\choose i }{-k-1\choose m-k-i}(-1)^{m-k-i}&&(1)\\ &=(-1)^{m-k}\sum_{i=0}^k {k\choose i }{-k-1\choose m-k-i}\\ &=(-1)^{m-k}{-1\choose m-k}&&(2)\\ &=(-1)^{m-k}{m-k\choose m-k}(-1)^{m-k}&&(3)\\ &=1\qquad\blacksquare\end{align}$$

(1): Upper Negation
(2): Vandermonde
(3): Upper Negation

$\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.