4
$\begingroup$

The book "Concrete Mathematics: A Foundation for Computer Science", 2nd Edition - authored by Ronald L. Graham, Donald E. Knuth, Oren Patashnik - has, in its page 174, a table called: "Table 174 The top ten binomial coefficient identities". The table is also available in Princeton's PlasmaWiki page about "Binomial Coefficient" - http://qed.princeton.edu/main/PlasmaWiki/Binomial_Coefficient

One of the identities is the "Upper Summation" that is stated both in the book and in PlasmaWiki as follows:

$$\sum_{0 \leq k \leq n}\binom{k}{m} = \binom{n + 1}{m + 1}$$

However, another book - a Portuguese book called "Matemática Finita" (which, literally translated, means "Finite Math") - presents a different formula for the "Upper Summation" - that it calls "Adição do Índice Superior" (literally, "Upper Index Summation").The difference between the two is the lower index of the sum that is $m$ instead of 0 :

$$\sum_{k=m}^{n}\binom{k}{m} = \binom{n + 1}{m + 1}$$

I find it strange that both formulas have the same result, considering that Knuth's apparently has the sum starting from index 0 and the "Matemática Finita" one starts from index $m$. Can anyone help me understand this? Am I missing something?

$\endgroup$
2
  • $\begingroup$ I've seen the second before, is it possible using the generalized binomial coefficient formula involving negative terms that the first formula works out? Or maybe they just set them to Zero hmmm $\endgroup$
    – Evan
    Commented Sep 15, 2013 at 18:49
  • 1
    $\begingroup$ Oh wait, you get zeros even when you plug them into the generic formula hah, ie 3 choose 5 would be 3*2*1*0*-1/5!=0 $\endgroup$
    – Evan
    Commented Sep 15, 2013 at 18:51

2 Answers 2

5
$\begingroup$

They’re exactly the same, because $\binom{n}m=0$ when $n<m$. This is clear if you define the binomial coefficient $\binom{n}m$ for non-negative integers $m$ and $n$ as the number of $m$-element subsets of an $n$-element set. It’s also easily checked if you define $\binom{x}k$ for real $x$ and non-negative integers $k$ as

$$\binom{x}k=\frac{x^{\underline k}}{k!}=\frac{x(x-1)\ldots(x-k+1)}{k!}\;,$$

where $x^{\underline k}$ is a falling factorial: when $x$ is a non-negative integer less than $d$, one of the factors in the numerator is $0$.

$\endgroup$
1
  • $\begingroup$ One more additional note to this fine answer: we can omit summation bounds at all having binomial coefficients defined as non-zero only within the range $0 \leq k \leq n$, see Knuth's "Two notes on notation" arxiv.org/abs/math/9205211 $\endgroup$ Commented May 23 at 8:12
3
$\begingroup$

The formula is qualified in Concrete Mathematics by "integers $m,n\geq0$", so the difference between the two quoted right hand sides is $\sum_{0\leq k<m}\binom km=0$ (all terms in this sum are$~0$).

I think the point of starting the summation at $0$ is that this is more natural in practice: you typically consider all partial sums down a "column" of Pascal's triangle, which starts to the right of the triangle with $m$ entries equal to$~0$ before reaching the right edge. Then for the formula in Concrete Mathematics, there is nothing special for $n<m$, apart from the fact that one hasn't got to the nonzero entries yet; on the other hand the formula $\sum_{m\leq k\leq n}\binom km=\binom{n+1}{m+1}$ might suggest something fishy is going on for $n<m-1$, as the sum is over a "negative length interval"; by analogy with integrals, one might expect that subtracting off terms encountered during backing up would be the right thing to do. In fact the stated sum is empty, and correctly equated to$~0$ by the formula, because the terms that would have been "backed up" over are all$~0$; it is better however not to have such worries in the first place.

I note that in the "finite calculus" form (2.48) of the summation, we can allow negative integer $n$; then it is convenient to replace $n+1$ by $n$, and one gets the nice formula $$ \sum\nolimits_0^n\binom km\delta k = \binom n{m+1}, \quad\text{for all integers $n$, and integer $m\neq-1$.} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .