We need to prove for homework using the generating function method that

$$c_n:=\sum_{k=0}^n {2k \choose k}{2n-2k \choose n-k}=4^n$$

I figured out we can start with function

$$f(x)=\sum_{n=0}^\infty {2n\choose n}x^n=^*\frac{1}{\sqrt{1-4x}}$$

Such that clearly

$$f(x)\cdot f(x)=\sum_{n=0}^\infty c_nx^n=^*\frac{1}{1-4x}=^*\sum_{n=0}^\infty 4^nx^n$$

However the equality signs $=^*$ i found out only with wolfram alpha and i don't think we may use that directly in our proof. I do now that the convergence radiance of both functions is $1/4$ by the ratio test but by my knowledge this does not give the immediate answer. Does anyone know how to properly prove this?


You can show your first star ($\sum_{n \ge 0} \binom{2n}{n}x^n = (1-4x)^{-1/2}$) via the Taylor series of the right-hand side. Just do the first few derivations, then you'll see the pattern, which you can then prove by induction.
The second star means to say that if we set $\mathcal C = \mathcal A \times \mathcal B$ for combinatorial classes $\mathcal A, \mathcal B$ and $\mathcal C$, then $C(z) = A(z) \cdot B(z)$ (where $A,B$ and $C$ are the respective generating functions). Your standard reference here is, as always, Analytic Combinatorics (in particular Chapter $1$) by Flajolet and Sedgewick.
Your third star can be shown by means of the geometric series.

  • $\begingroup$ I do understand how to use your comment on the second star, but I think given the first star it is not really a problem since $c_n$ follows from the series multiplication given the first star, and of course $1/1-4x$ is the square of the previous series. Thanks! $\endgroup$ – user1043065 May 8 '14 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.