×

# Curious Identity

Prove That

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

This is a part of the set Formidable Series and Integrals

Note by Ishan Singh
1 year, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

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{blue}{(2n-2k)!}}{r! k! (2n-2k-r)! \times \color{blue}{(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}}$$

- 1 year, 9 months ago

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 } }$

- 1 year, 9 months ago