"Ballot numbers" sum up to Catalan numbers Summing certain numbers and comparing the results with OEIS, I found that
$ 
\sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n},
$
where $C_n$ denotes the $n^{\textrm{th}}$ Catalan Number. How can I prove this equation? And is there any combinatorial interpretation?
Some background information: The number $\frac{k}{n} \binom{2n-k-1}{n-1}$ denotes the number of unranked trees of size $n$ with a root degree $k$ (these numbers are known as ballot numbers, see e.g. the book Analytic Combinatorics from Flajolet and Sedgewick, page 68). So one must have $\sum_{k=1}^n \frac{k}{n} \binom{2n-k-1}{n-1} =  C_{n}$, since there are $C_n$ many trees of size $n$.
 A: Notice that:
$$
   \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} \stackrel{k \to n+1-k}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{n-1} \stackrel{\binom{a}{b} = \binom{a}{a-b}}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{k-1} = \sum_{k=0}^{n} \frac{(n-k)^2}{n} \binom{n+k-1}{k}
$$
This this nothing but a convolution of two sequences $a_{k} = \frac{k^2}{n}$ and $b_{k} = \binom{n+k-1}{k}$. Therefore the generating function for the sum $c_n = \sum_{k=0}^{n} a_{n-k} b_k$ is the product of generating functions of $a_k$ and $b_k$:
$$
   \sum_{k=0}^\infty x^k a_k = \frac{1}{n} \sum_{k=0}^\infty x^k k^2 = \frac{1}{n} \left( x\frac{\mathrm{d}}{\mathrm{d} x}\right)^2 \sum_{k=0}^\infty x^k = \frac{1}{n} \frac{x(1+x)}{(1-x)^3}
$$
$$
   \sum_{k=0}^\infty \binom{n+k-1}{k} x^k = \frac{1}{(1-x)^n}
$$
Thus:
$$
    c_n = [x]^n \left( \frac{1}{n} \frac{x(1+x)}{(1-x)^3}  \frac{1}{(1-x)^n} \right) = [x]^n \left( \frac{1}{n} \frac{x}{(1-x)^{n+3}} + \frac{1}{n} \frac{x^2}{(1-x)^{n+3}} \right) = \frac{1}{n} \left(\binom{2n+1}{n-1} + \binom{2n}{n-2}  \right)
$$
Now, using 
$$
   \binom{2n}{n-2} = \binom{2n+1}{n-1} - \frac{2n}{n-1} \binom{2n-1}{n-2}
$$
which is easily proven using recurrence relation for factorials comprising binomial coefficients,  we get
$$
   c_n = \frac{2}{n} \binom{2n+1}{n-1} - \frac{2}{n-1} \binom{2n-1}{n-2} = C_{n+1} - C_{n}
$$
A: Consider the space of lattice points $(p,q)$ where $0 \leq p \leq q, q = 0, 1, \dots$;
the number of (shortest) paths in this space from $(p,q)$ to $(0,0)$ is the ballot number
$$N(p,q) = \frac{q-p+1}{q+1} \cdot \binom{p+q}{p}; \quad N(0,0) =_D 1.$$
Using this notation we have $ N(n-k,n-1) = \frac{k}{n} \binom{2n-k-1}{n-1} $.
The problem asks to show
$$\sum_{k=1}^n k N(n-k, n-1) =  C_{n+1} - C_{n}.$$
Note that $ C_{n} $ is the nth Catalan number and that $ C_{n} = N(n,n) $, so 
$ C_{n+1} - C_{n} $ is the number of paths from point $(n-1, n+1)$ to $(0,0)$ (all paths from 
$(n+1, n+1)$ to $(0,0)$ which don't use point $(n,n)$ must use point $(n-1, n+1)$).
Any path from point $(n-1, n+1)$ to point $(0,0)$ must use one and only one of the arcs $a(k)$
which start from point $(k, n)$ and stop in point $(k, n-1)$, where $0 \leq k \leq n-1$.
But the number of such paths is $(n-k)N(k,n-1)$ because the number of paths from $(n-1, n+1)$
to point $(k, n)$ is $(n-k)$, and the number of paths from point $(k,n)$ which use arc $a(k)$ is
$N(k,n-1)$, so the total number of paths from point $(n-1, n+1)$ to $(0,0)$ is
$\sum_{k=0}^{n-1} (n-k) N(k,n-1)$.

Voineasa.
