3

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].$

Isomorphism
  • 437
  • 2
  • 10

1 Answers1

2

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.

Marko Riedel
  • 61,317