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