Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of combinations from k to n

  1. Sep 25, 2011 #1
    I have been trying to figure out a formula for the sum of combinations. For example:

    [itex]\sum[/itex]nk=0([itex]\frac{n}{k}[/itex]) = 2n

    But what if you want to sum from any arbitrary k, like 4? I've tried looking at Pascal's triangle for nice values of n and k, but haven't been able to see a pattern. I would really appreciate any help with this. I want to apply this to combinations for large n, which are impractical to compute.

    Thank you in advance.
  2. jcsd
  3. Sep 26, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't know any nice formula for [itex] \sum_{k=0}^m \binom{n}{k} [/itex] Your question made me curious and I searched the web. It apparently doesn't know a nice formula either. Perhaps if you give an example of the kind of computation you are trying to do, someone will see a way to compute the result - at least compute it on a computer.
  4. Sep 26, 2011 #3
    The sum could be expressed in terms of the incomplete beta function, e.g. using the cdf of the binomial distribution with p=1/2.
  5. Sep 27, 2011 #4
    For large n the binomial distribution is approximated by a normal distribution, so if you only want a close approximation you could use that.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook