# A simple finite combinatorial sum I found, that seems to work, would have good reasons to work, but I can't find in the literature.

I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors is only consistent if this identity is true:

$$\sum_{k=0}^{N}\left[ \binom{k+j}{j}\binom{N-k+j}{j}\right] = \binom{N+2j+1}{2j+1}$$

Now, this seems to work for small numbers, but I searched for it a lot in the literature and I can't find it.(I have a physics background so probably my knowledge of proper "literature" is the problem here). Neither I can demonstrate it! Has anyone of you seen this before? Can this be rewritten equivalently in some more commonly seen way? Can it be proven right...or wrong? Thanks in advance! :)

• For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/… – David Foley Dec 6 at 16:07
• Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10 – user113102 Dec 6 at 17:32
• @user113102 The index of summation doesn't appear in the right position for 1.10, though. – chepner Dec 6 at 20:32
• Taking $\alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n \choose i} = {n \choose n-i}$ and you're good, no? I admittedly didn't look too hard. – user113102 Dec 6 at 21:27
• I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive? – rrogers Dec 11 at 20:56

Your identity is correct. I don't know a reference offhand, but here is a proof.

The right side, $$\binom{N+2j+1}{2j+1}$$, is the number of bitstrings of length $$N+2j+1$$ consisting of $$N$$ zeroes and $$2j+1$$ ones.

The sum on the left counts the same set of bitstrings. Namely, for $$0\le k\le N$$, the term $$\binom{k+j}j\binom{N-k+j}j$$ is the number of those bitstrings in which the middle one, with $$j$$ ones on either side, is in the $$k+j+1^\text{st}$$ position; i.e., it has $$k$$ zeroes and $$j$$ ones to the left, $$N-k$$ zeroes and $$j$$ ones to the right.

P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form: $$\sum_{k=0}^m\binom{u+k}k\binom{v-k}{m-k}=\binom{u+v+1}m.$$ If we set $$m=N$$, $$u=j$$, $$v=N+j$$, this becomes $$\sum_{k=0}^N\binom{j+k}k\binom{N+j-k}{N-k}=\binom{N+2j+1}N$$ which is plainly equivalent to your identity $$\sum_{k=0}^N\binom{k+j}j\binom{N-k+j}j=\binom{N+2j+1}{2j+1}.$$

We have

$$\sum_{k=0}^N {k+j\choose j} {N-k+j\choose j} = \sum_{k=0}^N {k+j\choose j} {N-k+j\choose N-k} \\ = \sum_{k=0}^N {k+j\choose j} [z^{N-k}] (1+z)^{N-k+j} = [z^N] (1+z)^{N+j} \sum_{k=0}^N {k+j\choose j} z^k (1+z)^{-k}.$$

Now we may extend $$k$$ beyond $$N$$ as there is no contribution to $$[z^N]$$ at the front in this case (we have $$z^k (1+z)^{-k} = z^k +\cdots$$)

$$[z^N] (1+z)^{N+j} \sum_{k\ge 0} {k+j\choose j} z^k (1+z)^{-k} = [z^N] (1+z)^{N+j} \frac{1}{(1-z/(1+z))^{j+1}} \\ = [z^N] (1+z)^{N+j} \frac{(1+z)^{j+1}}{(1+z-z)^{j+1}} = [z^N] (1+z)^{N+2j+1} = {N+2j+1\choose 2j+1}.$$

• I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks! – Rocco Dec 7 at 9:26
• There is this at Wikipedia on formal power series. – Marko Riedel Dec 7 at 13:19