Give a combinatorial proof of the identity $$ \sum_{k} \binom{2r}{2k-1}\binom{k-1}{s-1}=2^{2r-2s+1}\binom{2r-s}{s-1}\ \quad r,s\in \mathbb{N}_0. $$ Obviously the identity is true when $r<s$ so let’s assume $1\leq s\leq r$. The (RHS) can be interpreted as the number of ways of allocating 0 or 1 to $2r-2s+1$ people and 2 to $s-1$ people. Now count it again by summing up such allocations for fixed $k$ ($k$ denotes how many people receive $0$). This usual argument does not let us get (LHS) and I am at a loss. Could you show me more suitable ways of thinking to tackle this problem?

  • $\begingroup$ I don't see how it would work yet, but I think that, for the RHS, you would want the sum to be $2r$ (to match $2r$ on the left), but in your proposed proof sketch, the sum of $0$'s, $1$'s and $2$'s is at most $2r-2s+1+2(s-1)=2r-1$. So you need to add an extra $1$ somehow. Then, for the LHS, I'm not sure that $k$ should be the number of $0$'s, because how would you interpret $2k-1$ then? It might have to do with $1$'s and $2$'s, that's more likely, but I don't see yet how. $\endgroup$ – Alexander Burstein Dec 26 '17 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.