3
$\begingroup$

Does anyone know a better expression than the current one for this sum?

$$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$

It would help me compute a lot of things and make equations a lot cleaner in the context where it appears (as some asymptotic expression of the coefficients of a polynomial defined over cyclic graphs). Perhaps the context doesn't help much though.

For instance, if $N = m$, the sum is $N+1$, and for $N = m+1$, this sum is $N + (N-1) + \dots + 1 = N(N+1)/2$. But otherwise I don't know how to compute it.

  • 0
    I thought it was a triviality so deleted it at first, but I conjecture it is something like $\binom{N+1}{N-m}$. Although I don't think it's quite obvious. (This conjecture happens to be false for $m=2$ and $N=5$. I am not happy.)2012-07-22
  • 0
    It looks like it's just $\dbinom{N+1}{m}$...2012-07-22
  • 0
    @J.M. : $m$? How come? I don't see it. (Tried a few cases on Mathematica and your suggestion seems to work.)2012-07-22
  • 0
    @J.M. : Oh, you just corrected the mistake in my conjecture. My bad. Thank you.2012-07-22
  • 1
    @J.M. : I actually counted what I wanted to count on my cyclic graph thing in a better way so that I can actually prove that this sum is $\binom{N+1}m$ indirectly. Should I post my graph-theoretic answer or it is irrelevant to do so?...2012-07-22
  • 1
    There's a proof of a more general identity in page 159 of *Concrete Mathematics*, which uses the recurrence formula for binomial coefficients $\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$ repeatedly. You can only apply this after you reindex your sum as $$\sum_{k=0}^m\binom{N-m+k}{k}$$2012-07-22
  • 0
    I think it is best that you answer your own question, as it seems to me a combinatorial proof is usually much more welcomed than a direct finagling of binomial coefficients... :) I might post the "finagling route" much later, unless somebody beats me to it.2012-07-22
  • 1
    Hey! Someone posted a very relevant answer with blue balls and red balls. I was about to accept it! It must be put back!2012-07-22

4 Answers 4