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

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

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

Comments

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

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

Ishan Singh - 1 year, 9 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, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...