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! :)
Answer
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}.$$
No comments:
Post a Comment