"Ballot numbers" sum up to Catalan numbers

Solution 1:

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} $$

Solution 2:

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.