Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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.) –  Patrick Da Silva Jul 22 '12 at 3:25
    
It looks like it's just $\dbinom{N+1}{m}$... –  J. M. Jul 22 '12 at 3:28
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?... –  Patrick Da Silva Jul 22 '12 at 3:35
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}$$ –  J. M. Jul 22 '12 at 3:38
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! –  Patrick Da Silva Jul 22 '12 at 4:03
show 3 more comments

4 Answers 4

Using methods described in Concrete Mathematics (Graham, Knuth & Patashnik), the following did the trick for me.

\begin{align*} \sum_{k=0}^n \binom{N-k}{n-k} &= \sum_{k=0}^n (-1)^{n-k} \binom{n-k-(N-k)-1}{n-k} & \text{inversion (5.14)}\\ &= \sum_{k=0}^n (-1)^k \binom{n-N-1}{k} & \text{reverse order} \\ \end{align*} Letting $r = -(N+1)$ and using the results on page 167 yields $$ \sum_{k=0}^n (-1)^k \binom{n+r}{k} = \binom{-r}{m} = \binom{N+1}{m} $$ These calculations may seem like magic, but then one could argue this book makes you a magician.

share|improve this answer
add comment

First note that $\dbinom{n-i}{m-i} = \dbinom{n-i}{n-m}$. Hence, you have $$\dbinom{n-m}{n-m}+\dbinom{n-m+1}{n-m}+\cdots+\dbinom{n-1}{n-m}+\dbinom{n}{n-m}$$ Let $n-m = k$. Hence, we want to find an expression for $$\dbinom{k}k+\dbinom{k+1}{k}+\cdots+\dbinom{n-1}{k}+\dbinom{n}{k}$$ From the Pascal's triangle, we have

$\hskip2.5in$enter image description here \begin{align} \color{red}{\dbinom{n+1}{k+1}} & = \color{blue}{\dbinom{n}{k}} + \color{red}{\dbinom{n}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{red}{\dbinom{n-1}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \color{red}{\dbinom{n-2}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{red}{\dbinom{k+2}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{blue}{\dbinom{k+1}{k}} + \color{red}{\dbinom{k+1}{k+1}}\\ & = \color{blue}{\dbinom{n}{k}} + \color{blue}{\dbinom{n-1}{k}} + \color{blue}{\dbinom{n-2}{k}} + \cdots \color{blue}{\dbinom{k+2}{k}} + \color{blue}{\dbinom{k+1}{k}} + \color{blue}{\dbinom{k}{k}} \end{align}

Hence, your result is $\dbinom{n+1}{n-m+1} = \dbinom{n+1}m$

share|improve this answer
add comment

Here's my version of the proof (and where it arose in the context). You have a cyclic graph of size $n$, which is essentially $n$ vertices and a loop passing through them, so that you can think of them as the roots of unity on a circle (I don't want to draw because it would take a lot of time, but it really helps).

You want to count the number of subsets of size $k$ ($0 \le k \le n$) of this graph which contain 3 consecutive vertices (for some random reason that actually makes sense to me, but the rest is irrelevant).

You can fix 3 consecutive vertices, assume that the two adjacent vertices to those 3 are not in the subset, and then place the $k-3$ remaining anywhere else. Or you can fix $4$ consecutive vertices, assume again that the two adjacent vertices to those $4$ are not in the subset, and then place the $k-4$ remaining anywhere else. Or you can fix $5$, blablabla, etc. If you assume $n$ is prime, every rotation of the positions you've just counted gives you a distinct subset of the graph, so that the number of such subsets would be $$ n\sum_{i=0}^{k-3} \binom{n-5-i}{k-3-i}. $$ On the other hand, if you look at it in another way : suppose there is $\ell$ consecutive vertices in your subset. Look at the $3$ vertices in the $\ell$ consecutive ones that are adjacent to a vertex not in your subset, and place the remaining ones everywhere else. Again, the number of such subsets is $$ n\binom{n-4}{k-3}. $$ If $n$ is not prime, my computations are not accurate (they don't count well what I want to count in my context, but that's another question I'm trying to answer for myself), but I do precisely the same mistakes in both computations! So the two are actually equal. Removing the $n$'s on both lines, replacing $n-5$ and $k-3$ by $N$ and $m$, we get the identity.

share|improve this answer
add comment

The answer indeed seems to be $\binom{N+1}{m}$. You can get it from the more well-known identity \begin{align} \binom{n}{k} = \sum_{r =k}^n \binom{r-1}{k-1} \end{align} by change of variable. There is a nice combinatorial proof of this later identity which you may even adapt to apply directly to your problem. Let $A_r$ be the set of $k$-subsets of $[n] = \{1,\dots,n\}$ whose maximal element is $r$. Let $S$ be the set of all $k$ subsets of $[n]$. Then, $S = \cup_{r = k}^n A_r$ and this union is disjoint. We have $|A_r| = \binom{r-1}{k-1}$ and $|S| = \binom{n}{k}$. You can fill in the details yourself.

EDIT: change of variable: $n \to n+1$, $r \to n+1-i$ and $k \to n+1 -m$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.