# Computing a sum of binomial coefficients

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.

-
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}$... –  Ｊ. Ｍ. Jul 22 '12 at 3:28
@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
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}$$ –  Ｊ. Ｍ. Jul 22 '12 at 3:38
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

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$.

-

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$ \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$

-

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.

-

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.

-