Prove: $\sum_{i=0}^{n-1} C_i\binom{2(n-i)-1}{n-i} = \binom{2n}{n+1}$

Question

I am working on the following problem:

Given that all of the legal paths (ones which do not cross over the line $y = x$) from $(0,0)$ to $(n,n)$ must begin with a move to the right and end with a move upwards. And anytime the number of upward moves exceeds the number of rightward moves, the path becomes illegal. The solution seems to be the total number of paths from $(0,0)$ to $(n,n)$ minus the total number of illegal paths.

Interestingly, I found that the number of illegal paths can be expressed by the formula:

$\sum_{i=0}^{n-1} C_i\binom{2(n-i)-1}{n-i}$

Here, $C_i$ denotes the $i^{th}$ Catalan number. For instance, $C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5 ...$.

Also, the number of illegal paths is the second term in the Catalan numbers: $\binom{2n}{n} - \binom{2n}{n+1}$, resulting in $\binom{2n}{n+1}$.

I am seeking a proof for: $\sum_{i=0}^{n-1} C_i\binom{2(n-i)-1}{n-i} = \binom{2n}{n+1}$

Any insights or methods to prove this would be greatly appreciated.

Answer 1

Here is a generating function approach. In the following we use the coefficient of operator $[z^i]$ to denote the coefficient of $z^i$ in a series. This way we can write for instance \begin{align*} [z^i](1+z)^n=\binom{n}{i}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-1}}&\color{blue}{\frac{1}{i+1}\binom{2i}{i}\binom{2n-2i-1}{n-i}}\\ &=\sum_{i=0}^{n-1}\frac{1}{i+1}\binom{2i}{i}\binom{2n-2i-1}{n-1-i}\tag{2}\\ &=\sum_{i=0}^{\infty}[z^i]\frac{2}{1+\sqrt{1-4z}}[t^{n-1-i}](1+t)^{2n-2i-1}\tag{3}\\ &=[t^{n-1}](1+t)^{2n-1}\sum_{i=0}^{\infty}\left([z^i]\frac{2}{1+\sqrt{1-4z}}\right)\left(\frac{t}{(1+t)^2}\right)^i\tag{4}\\ &=[t^{n-1}](1+t)^{2n-1}\frac{2}{1+\sqrt{1-\frac{4t}{(1+t)^2}}}\tag{5}\\ &=[t^{n-1}](1+t)^{2n-1}\frac{2}{1+\frac{1-t}{1+t}}\\ &=[t^{n-1}](1+t)^{2n}\\ &\,\,\color{blue}{=\binom{2n}{n-1}}\tag{6} \end{align*} and the claim follows.

Comment:

• In (2) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (3) we apply the coefficient of operator according to (1) twice. Here we use the generating function $\frac{2}{1+\sqrt{1-4z}}$ of the Catalan numbers. We also set the limit to $\infty$ without changing anything since we are adding zeros only.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$.

• In (5) we apply the substitution rule of the coefficient of operator with $z:=\frac{t}{(1+t)^2}$
  \begin{align*} A(t)=\sum_{i=0}^\infty a_i t^i=\sum_{i=0}^\infty \left([z^i]A(z)\right)t^i \end{align*}

• In (6) we select the coefficient of $[t^{n-1}]$.