Combinatoric identity from a random walking problem I tried to prove the following equation and got stuck:
$$\sum_{k=1}^{n-r+1}\left[\binom{2k-1}{k}-\binom{2k-1}{k+1}\right]\binom{2n-2k+1}{n-k+r}=\binom{2n+1}{n-r}.$$
For whom are interested in its background:
Let $S_n$ be a symmetric random walking on the line. We call it a sign reverse at time $n$ if $S_{n-1}S_{n+1}<0.$ Let $X_n$ be the total number of reverses by the time $2n+1$. Prove that $$\mathbb{P}[X_n=r]=2\mathbb{P}[S_{2n+1}=2r+1]$$
holds for each $r\geq 0.$
The case that $r=0$ is trivial, and I use induction to prove the statement. The rest process was a bit tedious (confident about its correctness) and I finally arrived at the beginning equation.
THX :)
As @Jean Marie commented, the induction starts by conditioning the first time reaching -1, which is exactly the same as meeting the diagonal in a Catalan path, noted that $\mathbb{P}[X_n=r\big\vert S_1=1]=\mathbb{P}[X_n=r].$
 A: We seek to verify that
$$\sum_{k=1}^{n-r+1}
\left[{2k-1\choose k} - {2k-1\choose k+1}\right]
{2n-2k+1\choose n-k+r} = {2n+1\choose n-r}.$$
Note that for the square bracket term with $k\ge 1$ we get a Catalan
number, so the LHS becomes
$$\sum_{k=1}^{n-r+1} \frac{1}{k+1} {2k\choose k}
{2n-2k+1\choose n-r+1-k}.$$
This becomes
$$[z^{n-r+1}] (1+z)^{2n+1}
\sum_{k\ge 1} \frac{1}{k+1} {2k\choose k} \frac{z^k}{(1+z)^{2k}}.$$
Here we have extended to infinity due to the coefficient extractor.
Continuing with the OGF of the Catalan numbers,
$$- {2n+1\choose n-r+1} +
[z^{n-r+1}] (1+z)^{2n+1}
\frac{1-\sqrt{1-4z/(1+z)^2}}{2z/(1+z)^2}.$$
The square root term becomes
$$[z^{n-r+1}] (1+z)^{2n+1}
\frac{1+z-\sqrt{(1-z)^2}}{2z/(1+z)}
\\ = [z^{n-r+1}] (1+z)^{2n+1}
\frac{1}{1/(1+z)}
= [z^{n-r+1}] (1+z)^{2n+2}
= {2n+2\choose n-r+1}.$$
Collecting everything we have
$${2n+2\choose n-r+1} - {2n+1\choose n-r+1}
= {2n+1\choose n-r}
\left[\frac{2n+2}{n-r+1} - \frac{n+r+1}{n-r+1}\right]
\\ = {2n+1\choose n-r}$$
as claimed. This last one was Pascal's rule.
