Discrete math evaluate

Question

Question: Evaluate $$\sum_{k=0}^n {2k\choose k}{2n-2k \choose n-k}$$ Hint: use the fact that $$(1-4x)^{-1/2} = \sum_{n\ge0} {2n \choose n}x^n$$ For some reason the hint has me more lost than the problem but I'm sure it is included for a reason. My gut feeling is to approach this with a binomial series but I am not sure where to begin. Any help would be greatly appreciated!

Answer 1

Here are two ways to find a closed expression

Cauchy product

Note, the binomial expression in OPs question is a Cauchy product which we get as the coefficient of the multiplication of two power series. In case both series are equal, say $A(x)=\sum_{n=0}^{\infty}a_kx^k$ we obtain \begin{align*} A^2(x)=\left(\sum_{n\geq0}a_nx^n\right)^2 =\sum_{n\geq0}\left(\sum_{k=0}^na_ka_{n-k}\right)x^n\tag{1} \end{align*}

Applying (1) and using the hint stated in OPs question with $a_n=\binom{2n}{n}$ we get

\begin{align*} \sum_{n\geq0}&\left(\sum_{k=0}^n\binom{2k}{k}\binom{2n-2k}{n-k}\right)x^n\\ &=\left(\sum_{n\geq0}\binom{2n}{n}x^n\right)^2\\ &=\left(\frac{1}{\sqrt{1-4x}}\right)^2\\ &=\frac{1}{1-4x}\\ &=\sum_{n\geq 0}4^nx^n \end{align*}

We conclude by comparing coefficients

\begin{align*} \sum_{k=0}^n\binom{2k}{k}\binom{2n-2k}{n-k}=4^n\qquad\qquad n\geq 0 \end{align*}

Coefficient of - operator

Another way is to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series $A(x)=\sum_{k\geq 0}a_kx^k$ analogously to this answer.

We obtain for $n\geq 0$

\begin{align*} \sum_{k=0}^n&\binom{2k}{k}\binom{2n-2k}{n-k}\\ &=\sum_{k=0}^n[x^k]\frac{1}{\sqrt{1-4x}}[y^{n-k}]\frac{1}{\sqrt{1-4y}}\\ &=[y^n]\frac{1}{\sqrt{1-4y}}\sum_{k=0}^ny^k[x^k]\frac{1}{\sqrt{1-4x}}\tag{2}\\ &=[y^n]\frac{1}{\sqrt{1-4y}}\frac{1}{\sqrt{1-4y}}\tag{3}\\ &=[y^n]\frac{1}{1-4y}\\ &=[y^n]\sum_{n\geq 0}4^ny^n\\ &=4^n \end{align*}

Comment:

• In (2) we use the rule $[y^k]f(y)=[y^0]y^{-k}f(y)$

• In (3) we use the substitution rule $f(y):=\sum_{k=0}^{n}a_ky^k=\sum_{k=0}^n\left([x^k]f(x)\right)y^k$