- #1

JTHM

- 2

- 0

I have a tricky problem that I hope one of you can help me with. (It's for a personal project, nothing to do with school.) I'm looking for a closed-form expression for the sum of the first through

*m*-th terms of a combinatorial number. For those of you unfamiliar with combinatorial numbers, here's some useful reading: http://en.wikipedia.org/wiki/Combina..._number_system

Basically, the idea is this: for any non-negative integers

*k*, and

*b*, we can express the value of

*b*as a sum of

*k*terms of the form [TEX]\binom{r_1}{k}+\binom{r_2}{k-1}+\binom{r_3}{k-2}... \binom{r_k}{1}[/TEX]. For every

*t*and

*s*where

*t*and

*s*are non-negative integers such that [TEX]t<s \leq k[/TEX], it will be the case that [TEX]r_t>r_s[/TEX] (this is just true by the definition of a combinatorial number).

For example, for [TEX]k=5[/TEX], we can express the number 36 as [TEX]\binom{7}{5}+\binom{6}{4}+\binom{2}{3}+\binom{1}{2}+\binom{0}{1}[/TEX].

Now, the sum of all five of these terms will be 36. But suppose I just want, say, the sum of the first two terms, four terms, or any arbitrary number of terms, and I don't want to exhaustively find every term and add all of them up. The question, then is this: given

*k*,

*b*, and

*m*, where

*k*is the total number of terms in the combinatorial number,

*b*is the value of the combinatorial number, and m is the number of terms (starting with the first term) that we want to sum, what is the closed-form expression for the sum of those terms?

Admittedly, I am not certain that a closed-form expression even exists. If you can think of a reason why there might not be a closed-form expression for the above, please share it. In the eventuality that there is no closed-form expression, if you can think of a fast algorithm to find such a sum--something faster than just adding the terms individually--that would be helpful, too.