Xrfgtjtk

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?

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

The formula is qualified in Concrete Mathematics by "integers $m,ngeq0$", so the difference between the two quoted right hand sides is $sum_{0leq 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_{mleq kleq 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
$$
sumnolimits_0^nbinom kmdelta k = binom n{m+1}, quadtext{for all integers $n$, and integer $mneq-1$.}
$$