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?
On
You can simplify the expression to $$ \sum_{r=0}^{b}\binom{n}{r}^2 - \sum_{r=1}^{b}\binom{n}{r}\binom{n-1}{r-1} $$ which are unlikely to exist in closed form, because most binomial sums don't. You can get an approximation.
For example, you can divide the first sum by $\binom{n}{b}^2$ to get $$ \frac{S_b}{\binom{n}{b}^2} = 1 + \frac{\binom{n}{b-1}^2}{\binom{n}{b}^2} + \ldots + \frac{1}{\binom{n}{b}^2} $$ Each $k^{th}$ term simplifies to $$ \Big(\frac{b}{n-b+k}\Big)^2 $$ for which you can find bounds since you know $\frac{n-1}{2}\leq b = \lfloor\frac{n-1}{2}\rfloor \leq\frac{n}{2}$, and hence the asymptotic bounds on the sum.
EDIT: for $n geq 2$ I compared every term to its upper-bound (rewrite $L=e^{\log L}) e^{-\frac{4k}n}$ and the corresponding integral is equal to $$ \frac{n}{4}\Big(e^{-\frac{4}{n}} - e^{-2} \Big) $$ Now multiply by $\binom{n}{b}^2$ to get the upper bound on the first sum: $$ \sum_{r=1}^{\lfloor \frac{n-1}{2} \rfloor} \binom{n}{r}^2 \leq \binom{n}{\lfloor \frac{n-1}{2} \rfloor}^2 \frac{n}{4}\Big(e^{-\frac{4}{n}} - e^{-2} \Big) $$
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.