Prove combinatorics problem $\sum_{k=0}^n {2k \choose k}{2n-2k \choose n-k}=4^n$ using generating functions

1.6k Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.