Curious Identity

Proposition : $\sum_{k=0}^{n} \dbinom{2n}{2k} \dbinom{2k}{k} 4^{n-k} = \dbinom{4n}{2n}$

Proof : Consider a set of $4n$ natural numbers from $1$ to $4n$. We will choose a subset of $2n$ numbers. First way is the trivial $\dbinom{4n}{2n}$. Another way is the following. We define a corresponding pair, that is two natural numbers in the set, whose sum is $4n+1$. For example :- $(1,4n) \ , (2,4n-1) \ ,\ (2n, 2n+1)$ etc.

Now, the subsets of $2n$ natural numbers can have either $0$ corresponding pairs, $1$ corresponding pair, $2$ corresponding pairs and at max $n$ corresponding pairs. We will find the number of ways of choosing exactly $k$ corresponding pairs.

First, we choose $k$ pairs in $\dbinom{2n}{k}$ ways. This can be seen by writing numbers $1$ to $2n$ in one row and $2n+1$ to $4n$ in another. We now have to choose $2n-2k$ single numbers. Note that there are $2n-k$ numbers left in both rows. To do this, we can either choose $0$ numbers from first row and $2n-2k$ from second row, $1$ number from first row and $2n-2k-1$ numbers from the second row and so on. This can be stated as

$\displaystyle \dbinom{2n}{k} \cdot \sum_{r=0}^{2n-2k} \dbinom{2n-k}{r} \cdot \dbinom{2n-k-r}{2n-2k-r}$

Writing in factorials, we have,

$\displaystyle \dbinom{2n}{k} \cdot \sum_{r=0}^{2n-2k} \dfrac{(2n-k)!}{r! k! (2n-2k-r)!}$

$\displaystyle = \dbinom{2n}{k} \cdot \sum_{r=0}^{2n-2k} \dfrac{(2n-k)! \times \color{#3D99F6}{(2n-2k)!}}{r! k! (2n-2k-r)! \times \color{#3D99F6}{(2n-2k)!}}$

$\displaystyle = \dbinom{2n}{k} \dbinom{2n-k}{k} \sum_{r=0}^{2n-2k} \dbinom{2n-2k}{r}$

$\displaystyle = \dbinom{2n}{k} \dbinom{2n-k}{k} 2^{2n-2k} \qquad \left(\because \sum_{r=0}^{n} \dbinom{n}{r} = 2^{n} \right)$

$\displaystyle = \dfrac{(2n)!}{(k!)^2 (2n-2k)!} 2^{2n-2k}$

$\displaystyle = \dbinom{2n}{2k} \cdot \dbinom{2k}{k} 2^{2n-2k}$

$\displaystyle = \dbinom{2n}{2k} \cdot \dbinom{2k}{k} 4^{n-k}$

Finally, summing from $k=0$ to $k=n$, we have the identity,

$\displaystyle \sum_{k=0}^{n} \dbinom{2n}{2k} \dbinom{2k}{k} 4^{n-k} = \dbinom{4n}{2n} \ \square$

Now,

$\displaystyle \text{S} = \sum_{k=0}^{n}\frac{4^{k}}{\left(2k\right)!\left[\left(n-k\right)!\right]^{2}}$

$\displaystyle = \sum_{k=0}^{n} \dfrac{4^{n-k}}{(2n-2k)! (k!)^2} \qquad \left(\because \sum_{k=0}^{n} f(k) = \sum_{k=0}^{n} f(n-k) \right)$

Writing in terms of binomial coefficients, we have,

$\displaystyle \text{S} = \dfrac{1}{(2n)!} \sum_{k=0}^{n} \dbinom{2n}{2k} \dbinom{2k}{k} 4^{n-k}$

Using the Proposition, we have,

$\displaystyle \text{S} = \dfrac{1}{(2n)!} \cdot \dbinom{4n}{2n}$

$\displaystyle = \boxed{\dfrac{(4n)!}{[(2n)!]^3}}$

Not a solution:

I proceeded by the hint you gave i.e. by using beta function. But I got stuck. Please help.

$\sum _{ k=0 }^{ n }{ \frac { { 4 }^{ k } }{ \left( 2k \right) !{ \left[ \left( n-k \right) ! \right] }^{ 2 } } } =\frac { 1 }{ n! } \sum _{ k=0 }^{ n }{ \frac { \left( \begin{matrix} n \\ k \end{matrix} \right) { 4 }^{ k } }{ \left( n-k \right) !\left( k-1 \right) ! } \int _{ 0 }^{ 1 }{ { x }^{ k }{ \left( 1-x \right) }^{ k-1 }dx } }$

Let $\xi=\sum_{k=0}^n\frac{4^k}{(2k)![(n-k)!]^2}=\frac{1}{(2n)!}\sum_{k=0}^n\binom{2n}{2k}\binom{2k}{k}4^{n-k}$ Let $\Omega=\sum_{k=0}^n\binom{2n}{2k}\binom{2k}{k}4^{n-k}$

Using Beta function and the relation that $\displaystyle \Gamma\left(p+\frac{1}{2}\right)=\frac{(2p-1)!!}{2^p}=\frac{(2p)!}{4^pp!}$ for $p\in\Bbb{N}$ we get that $\binom{2k}{k}=\frac{4^k}{\pi}\int_0^1y^{k-\frac{1}{2}}(1-y)^{-\frac{1}{2}}dy$ Substituting this in $\Omega$ and then interchanging the summation and integral signs( Justified by Tonelli's Theorem) we get that $\Omega=\frac{4^n}{\pi}\int_0^1\frac{1}{\sqrt{y(1-y)}}\left(\sum_{k=0}^n\binom{2n}{2k}\left(\sqrt{y}\right)^{2k}\right)dy$ Using Binomial Theorem we get that $\sum_{k=0}^n\binom{2n}{2k}x^{2k}=\frac{(1+x)^{2n}+(1-x)^{2n}}{2}$ $\Omega=\frac{4^n}{\pi}\int_0^1\frac{1}{\sqrt{y(1-y)}}\left(\frac{(1+\sqrt{y})^{2n}+(1-\sqrt{y})^{2n}}{2}\right)dy$ Substituting $y=\cos^2x$ we get $\Omega=\frac{4^n}{\pi}\int_0^{\pi/2}\left((1+\cos x)^{2n}+(1-\cos x)^{2n}\right)dx$

But we know that $\displaystyle 2\cos^2\left(\frac{x}{2}\right)=1+\cos x$ and $\displaystyle 2\sin^2\left(\frac{x}{2}\right)=1-\cos x$ we get that $\Omega=\frac{4^{2n}}{\pi}\int_0^{\pi/2}\left(\left(\cos\left(\frac{x}{2}\right)\right)^{4n}+\left(\sin\left(\frac{x}{2}\right)\right)^{4n}\right)dx$

Substituting $2u=x$ we get $\Omega=\frac{2\cdot 4^{2n}}{\pi}\int_0^{\pi/4}((\cos u)^{4n}+(\sin u)^{4n})du$

Now note that $\displaystyle \cos(x)=\sin\left(\frac{\pi}{2}-x\right)$ thus we get $\Omega=\frac{2\cdot 4^{2n}}{\pi}\int_0^{\pi/2}\cos^{4n}(u)du$

Using beta function we have that $\int_0^{\pi/2}\cos^{2x-1}\theta\sin^{2y-1}\theta d\theta=\frac{B(x,y)}{2}$ hence $\Omega=\frac{4^{2n}}{\pi}B\left(2n+\frac{1}{2},\frac{1}{2}\right)=\frac{4^{2n}\Gamma\left(2n+\frac{1}{2}\right)\Gamma\left(\frac{1}{2}\right)}{\Gamma(2n+1)\pi}$ $=\frac{4^{2n}(4n-1)!!\sqrt{\pi}\sqrt{\pi}}{4^n\Gamma(2n+1)\pi}$

But $\displaystyle (4n-1)!!=\frac{(4n)!}{2^{2n}(2n)!}$ Hence $\Omega=\frac{4^{2n}(4n)!}{4^{2n}((2n)!)^2}=\binom{4n}{2n}$

Hence $\xi=\frac{1}{(2n)!}\binom{4n}{2n}=\frac{(4n)!}{((2n)!)^3}$