An exercise on binomial coefficient identities

An exercise on binomial coefficient identities

Recently, I received an email asking how I got the closed form of a summation in one of my publications. I checked my archive and did not find the calculation back then. Here I do it again, so I will have it.

The summation in question given integers s and n is denoted as


First, each term in the summation can be rearranged into the product of binomial coefficients following


Then we look for possible binomial coefficient identities to transform Eq. (2). The closest may be Eq. (5.26) in Concrete Mathematics: A Foundation for Computer Science (2nd Edition) by Donald E. Knuth:


Putting into our context by setting


we can get


Ha, this identity would turn the right hand side of Eq. (2) into a closed form if the range of the summation were the same. Nevertheless, an interesting observation is that


Because the binomial coefficient stands for the number of ways to choose s out of s + n - 1 - j distinct items without ordering. If s + n - 1 - j < s, i.e., j > n - 1, which covers the range of j in Eq. (6), there is actually no way to make a choice like that, meaning the binomial coefficient is 0. In other words, all the s extra terms in the summation of Eq. (5) compared to that in Eq. (2) are actually 0, and the ranges of summations can be seen as the same.

Having said that, we are able to apply Eq. (5) to Eq. (2), and solve the summation:


Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.