# Generating Functions and Catalan Numbers

The task is to evaluate $$\sum_{k=0}^{n}\dfrac{1}{k+1}{2k\choose k}{2(n-k)\choose n-k}$$

This is what I've gotten so far.

\begin{align*} A(x)&=\sum_{n\geq 0}\left(\sum_{k\geq 0}^{n}\dfrac{1}{k+1}{2k\choose k}{2(n-k)\choose n-k}\right)x^{n}\\ &=\sum_{n\geq 0}C_{n}x^{n}\sum_{n\geq 0}\binom{2n}{n}x^{n}\\ &=\dfrac{1-\sqrt{1-4x}}{2x}\cdot\dfrac{1}{\sqrt{1-4x}}\\ &=\dfrac{1}{2x\sqrt{1-4x}}-\dfrac{1}{2x} \end{align*}

So we have $$A(x)=\dfrac{1}{2}\sum_{n\geq 1}\binom{2n}{n}x^{n-1}$$

So the answer would be $\dfrac{1}{2}\binom{2(n+1)}{n+1}$ but I know that is wrong because I got $\binom{2n-1}{n}$ when using a combinatorial arguement, which was verified.

$\dfrac{1}{2}\binom{2n+2}{n+1}=\binom{2n+1}{n}$ I just counted the lattice paths to $(n+1,n+1)$. Don't know why I didn't think of that earlier.