Prove that $1 + \sum_{k=1}^{n-1} \frac{k}{n-k} { 2n-k-1 \choose n} = C_n$ where $C_n$ is the $n$'th Catalan number?

Question

Prove that $$1 + \sum_{k=1}^{n-1} \frac{k}{n-k} { 2n-k-1 \choose n} = C_n$$ where $C_n$ is the $n$'th Catalan number?

Wrote a program to validate it, appears to be correct.

This looks awfully like the formula $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$

Both computational proof and combinatoric proof are welcome, but obviously combinatoric proof might be more beautiful. :)

Answer 1

Here is a proof which is slightly more combinatorial. We start with some algebraic manipulation, similar to Donald Splutterwit's answer: \begin{align} 1+\sum_k {k\over n-k}\binom{2n-k-1}n &=1+\sum_k \left[{2n \over n-k}\binom{2n-k-1}n-\frac{2n-k}{n-k}\binom{2n-k-1}n\right] \\&=1+\sum_k \left[2\binom{2n-k-1}{n-1}-\binom{2n-k}{n}\right] \\&=1+\sum_k \left[\binom{2n-k-1}{n-1}+\color{blue}{\binom{2n-k-1}{n-1}-\binom{2n-k}{n}}\right] \\&=1+\sum_k \left[\binom{2n-k-1}{n-1}-\color{blue}{\binom{2n-k-1}{n}}\right] \end{align} Now, each summand of the last expression has a combinatorial interpretation. Whereas $C_n$ is the number of paths from $(0,0)$ to $(n,n)$ which stay at or above the line $y=x$, the summand $\binom{2n-k-1}{n-1}-\binom{2n-k-1}{n}$ is the number of such paths whose first right step is at height $k$. This can be proven using the reflection principle.

Answer 2

Algebraic proof : \begin{eqnarray*} 1 + \sum_{k=1}^{n-1} \frac{k}{n-k} { 2n-k-1 \choose n} &=& 1 + \sum_{k=1}^{n-1} \frac{(2n-(2n-k))}{n-k} \frac{(2n-k-1)!}{(n-k-1)!n!} \\ &=& 1 + \sum_{k=1}^{n-1} \left( 2 \frac{(2n-k-1)!}{(n-k)!(n-1)!}-\frac{(2n-k)!}{(n-k)!n!} \right) \\ &=& 1+ 2\sum_{k=1}^{n-1} \binom{2n-k-1}{n-k}-\sum_{k=1}^{n-1} \binom{2n-k}{n-k} \\ &=& 2\sum_{j=0}^{n} \binom{n+j-1}{j}-\sum_{j=0}^{n} \binom{n+j}{j} \\ &=& 2 \binom{2n}{n}- \binom{2n+1}{n+1} =C_n. \\ \end{eqnarray*}

Answer 3

We seek to show that with $C_n$ the Catalan number we have

$$C_n = 1 + \sum_{k=1}^{n-1} \frac{k}{n-k} {2n-k-1\choose n}.$$

This holds by inspection when $n=0$ and $n=1$ when the sum is zero so we may assume that $n\ge 2.$ Observe that

$$\frac{k}{n-k} {2n-k-1\choose n} = k \times \frac{(2n-k-1)!}{n! \times (n-k)!} = \frac{k}{n} {2n-k-1\choose n-k}.$$

We thus obtain

$$1+ \frac{1}{n} \sum_{k=1}^{n-1} k {2n-k-1\choose n-k} = \frac{1}{n} \sum_{k=1}^n k {2n-k-1\choose n-k} \\ = \frac{1}{n} [z^n] (1+z)^{2n-1} \sum_{k=1}^n k \frac{z^k}{(1+z)^k}.$$

Here the coefficient extractor enforces the upper range and we find

$$\frac{1}{n} [z^n] (1+z)^{2n-1} \sum_{k\ge 1} k \frac{z^k}{(1+z)^k} \\ = \frac{1}{n} [z^n] (1+z)^{2n-1} \frac{z/(1+z)}{(1-z/(1+z))^2} \\ = \frac{1}{n} [z^n] (1+z)^{2n-1} \frac{z(1+z)}{(1+z-z)^2} = \frac{1}{n} [z^{n-1}] (1+z)^{2n} = \frac{1}{n} {2n\choose n-1}.$$

To see that this is indeed the Catalan number sequence we write

$$\frac{1}{n} {2n\choose n-1} = \frac{(2n)!}{n! \times (n+1)!} = \frac{1}{n+1} {2n\choose n}.$$

This is the claim (and it holds for $n\ge 0.$)