Use an argument about lattice paths to obtain an Ordinary Generating Function I am given that $\sum_{n=0}^{\infty}{2n \choose n}x^n = (1-4x)^{-\frac{1}{2}}$ and need to obtain $\sum_{n=0}^{\infty} {2n +k \choose n}x^n = \frac{C(x)^k}{\sqrt{1-4x}}$ using an argument about lattice paths where $C(x)$ is the ordinary generating function for the Catalan sequence.  I am trying to see how to apply lattice paths to this.  My first thought is maybe there is some convolution I am not seeing but I can't find a good approach otherwise.  
 A: The desired result is that
$$\sum_{n\ge 0}\binom{2n+k}nx^n=\left(\sum_{n\ge 0}\binom{2n}nx^n\right)\left(\sum_{n\ge 0}C_nx^n\right)^k\;,$$
which in turn says that
$$\sum_{j_0+\ldots+j_k=n}\binom{2j_0}{j_0}C_{j_1}C_{j_2}\ldots C_{j_k}=\binom{2n+k}n\tag{1}$$
for $n\ge 0$, where the summation is over all weak compositions of $n$ with $k+1$ parts.
Consider a lattice path $P$ from $\langle 0,0\rangle$ to $\langle n,n+k\rangle$. Let its vertices in order be $\langle p_i,q_i\rangle$ for $i=0,\ldots 2n+k$, so that $p_0=q_0=0$, $p_{2n+k}=n$, and $q_{2n+k}=n+k$. For $\ell=1,\ldots,k$ let $i_\ell$ be minimal such that $q_{i_\ell}=p_{i_\ell}+\ell$. If we remove from $P$ the vertical segment from $\langle p_{i_\ell-1},q_{i_\ell-1}\rangle$ to $\langle p_{i_\ell},q_{i_\ell}\rangle$ for $\ell=1,\ldots,k$, we obtain a lattice path $P'$ from $\langle 0,0\rangle$ to $\langle n,n\rangle$. $P'$ hits the diagonal at the points $\langle p_{i_\ell},p_{i_\ell}\rangle$ for $\ell=1,\ldots,k$, and if it rises above the diagonal at all, it does so only between $\langle p_{i_k},p_{i_k}\rangle$ and $\langle n,n\rangle$.
However, we cannot always reconstruct $P$ from $P'$, because $P'$ may hit the diagonal at points other than the endpoints and the points $\langle p_{i_\ell},p_{i_\ell}\rangle$ for $\ell=1,\ldots,k$. To reconstruct $P$, we need not only $P'$, but also the $k$-tuple $\langle i_1,\ldots,i_k\rangle$. Thus, $\binom{2n+k}n$ is the number of pairs $\big\langle P,\langle i_1,\ldots,i_k\rangle\big\rangle$ such that:


*

*$P$ is a lattice path from $\langle 0,0\rangle$ to $\langle n,n\rangle$;  

*$0<i_1<\ldots<i_k<n$;  

*$\langle i_\ell,i_\ell\rangle$ is on $P$ for $\ell=1,\ldots,k$; and  

*the only points $\langle p,q\rangle$ of $P$ lying above the diagonal (if any) satisfy $i_k<p<n$.


Now show that the lefthand side of $(1)$ counts the same set of pairs.
