MHB Sum of first m terms of a combinatorial number

[JTHM]

Dear Math Help Boards,

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 \binom{r_1}{k}+\binom{r_2}{k-1}+\binom{r_3}{k-2}... \binom{r_k}{1}. For every t and s where t and s are non-negative integers such that t<s \leq k, it will be the case that r_t>r_s (this is just true by the definition of a combinatorial number).

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

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.

 

[CaptainBlack]

Dear Math Help Boards,

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 \binom{r_1}{k}+\binom{r_2}{k-1}+\binom{r_3}{k-2}... \binom{r_k}{1}. For every t and s where t and s are non-negative integers such that t<s \leq k, it will be the case that r_t>r_s (this is just true by the definition of a combinatorial number).

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

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.

Your link is broken: Wikipedia Combinatorial Number System

CB

 

[caffeinemachine]

Dear Math Help Boards,

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 \binom{r_1}{k}+\binom{r_2}{k-1}+\binom{r_3}{k-2}... \binom{r_k}{1}. For every t and s where t and s are non-negative integers such that t<s \leq k, it will be the case that r_t>r_s (this is just true by the definition of a combinatorial number).

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

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.

I don't know if the following provides any help but it may give you some insight I hope.
Lets settle the existence of such a representation. We use induction on $k$.
If $k$ is $1$ then the assertion is trivially true. So base case is verified.
Now let $k>1$. Let $r_1$ be the greatest integer such that $b_1=b-\binom{r_1}{k}\geq 0$. If $b_1=0$ then we can easily find a desired representation. So assume $b_1>0$. Let $r_2$ be the largest integer such that $b_2=b_1-\binom{r_2}{k-1}\geq 0$. We show that $r_2<r_1$. Assume on the contrary that $r_2\geq r_1$. By the above said things we clearly have $b-\binom{r_1}{k}-\binom{r_2}{k-1}\geq 0$. But
\begin{align*}
r_2& \geq r_1 \\
\Rightarrow \binom{r_2}{k-1}&\geq \binom{r_1}{k-1}\\
\Rightarrow b-\binom{r_1}{k}-\binom{r_2}{k-1}&\leq b-\binom{r_1}{k}-\binom{r_1}{k-1}\\
\Rightarrow b_2=b-\binom{r_1}{k}-\binom{r_2}{k-1}&\leq b-\binom{r_1+1}{k}\\
\end{align*}
Where we have used the identity $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$.
Note that $b-\binom{r_1+1}{k}<0$ by definition of $r_1$. This gives $b_2<0$, a contradiction.
Thus we have $r_2<r_1$.
Now use the induction on $k$ to get a representation of $b_1$ as a sum of $k-1$ binomial terms. Add $\binom{r_1}{k}$ to this representation to get a representation of $b$. This completes the proof for existence.