Combinatorial Argument for a Binomial idenity 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?
 A: 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

T(n,k) is the number of n-digit binary words (length n sequences on {0,1}) containing k 1's such that no initial segment of the sequence has more 1's than 0's.

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.
A: 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)
$$
