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?
Best Answer
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$.