Results 1 to 2 of 2

Math Help - Sum of first m terms of a combinatorial number

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Atlanta, GA
    Posts
    1

    Sum of first m terms of a combinatorial number

    Dear Math Help Forum,


    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.
    Last edited by QuirinusQuirrell; January 7th 2013 at 07:04 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2009
    From
    London
    Posts
    39
    Thanks
    1

    Re: Sum of first m terms of a combinatorial number

    Hello,

    I came across something like this during my degree and I know of a way to show that any positive integer m can be written uniquely in the form

    {m_r\choose r} +{m_{r-1}\choose r-1}+...+{m_s\choose s},

    where m_r>m_{r-1}>\cdots>m_s>0 and r\geqslant s\geqslant 1.

    The fact that each integer can be written uniquely in such a way implies to me that no such closed form expression could exist, since a closed expression could be re-written in many different ways. I don't know if this helps at all, but I can try to reproduce the proof if you'd like.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Laurent Series and Number of Terms
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 28th 2010, 12:56 PM
  2. number of terms in taylor series
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 14th 2010, 05:52 AM
  3. Number of Terms in an Arithmetic Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 17th 2009, 06:28 AM
  4. Help with Find the Number of Terms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 09:24 AM
  5. number of terms for approximation
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 24th 2009, 10:33 AM

Search Tags


/mathhelpforum @mathhelpforum