Combinatorial proof of $\sum_{k} \binom{2r}{2k-1}\binom{k-1}{s-1}=2^{2r-2s+1}\binom{2r-s}{s-1}\ \ r,s\in \mathbb{N}_0$

180 Views Asked by At

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?