The following problem appeared in Putnam Competition, 1965:
Prove that
$$ \sum_{r=0}^{\lfloor \frac{n-1}{2}\rfloor} \left(\frac{n-2r}{n} \binom{n}{r}\right)^2 = \frac{1}{n} \binom{2n-2}{n-1} $$
where $\lfloor x \rfloor$ is the integer part of $x$. This is not difficult to prove using Algebra. Since the right hand side is the $(n-1)$th Catalan number, is there a Combinatorial argument that would establish the result?
Best Answer
The well-known result that $$ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}n $$ has an easy bijective combinatorial proof based on counting the $2n$-digit binary words with $n$ 1's and $n$ 0's by splitting it into two $n$-digit words and counting the number of 1's and 0's in each.
Similarly, the Catalan number result $$ \sum_{k=0}^{\lfloor n/2\rfloor} \left(\binom{n}{k}\!-\!\binom{n}{k\!-\!1} \right)^2 \!=\! \sum_{k=0}^{\lfloor n/2\rfloor} T(n,k)T(n,k) = C_n $$ has an easy bijective combinatorial proof. The numbers being squared are the triangular sequence OEIS A008315. Note the A008315 comment
Note that one combinatorial interpretation of $C_n$ is that it is the number of $2n$-digit binary words such that the number of 1's and 0's are both equal to $n$ and such that no initial segment of the word has more 1's than 0's.
Now split each $2n$-digit binary word into two $n$-digit words as before. The first $n$ digits has the required relation between the 1's and 0's. Now reverse the order of the last $n$ digits and change all the 0's to 1's and vice versa. This also has the required relation between the 1's and 0's.
As a comment by Mike Earnest indicates, it is possible to split each $2n$-digit word into unequal parts. Thus, by similar reasoning as above, the generalized identity $$ \sum_{k=0}^{\lfloor r/2\rfloor} T(r,k)T(2n-r,k+n-r) = C_n $$ where $\,0\le r\le n\,$ is proved.