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