# “Upper summation” binomial identity: different version from “Concrete Mathematics”

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?

• 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 – Evan Sep 15 '13 at 18:49
• 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 – Evan Sep 15 '13 at 18:51

## 2 Answers

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

• @Marc: I didn’t offer any generalization. I gave a combinatorial definition and an algebraic one and pointed out that both show that the two versions of the identity are essentially the same. – Brian M. Scott Sep 16 '13 at 16:21

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 (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, 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, 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.}$$