Waste less time on Facebook — follow Brilliant.

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, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

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 \)


\(\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}} \) Ishan Singh · 1 year, 7 months ago

Log in to reply

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 } } \] Aditya Kumar · 1 year, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...