<s>[INST] 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. :)
 [/INST] 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.$)
</s>