Proving $\sum_{k=0}^{n} \binom{n}{k}^2 =\dfrac{(2n)!}{(n!)^2}$

  • Context: MHB 
  • Thread starter Thread starter Albert1
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on proving the identity $\sum_{k=0}^{n} \binom{n}{k}^2 = \dfrac{(2n)!}{(n!)^2}$. This identity is a well-known combinatorial result that can be derived using various methods, including combinatorial arguments and generating functions. The proof confirms the equality by demonstrating that both sides represent the same combinatorial quantity, specifically the number of ways to choose $n$ items from $2n$ items.

PREREQUISITES
  • Understanding of binomial coefficients, specifically $\binom{n}{k}$.
  • Familiarity with factorial notation and properties.
  • Basic knowledge of combinatorial proofs and identities.
  • Experience with generating functions and their applications in combinatorics.
NEXT STEPS
  • Study the combinatorial proof of the identity $\sum_{k=0}^{n} \binom{n}{k}^2 = \dfrac{(2n)!}{(n!)^2}$.
  • Explore generating functions and their role in combinatorial identities.
  • Learn about Vandermonde's identity and its applications in combinatorics.
  • Investigate other identities involving binomial coefficients, such as the Hockey Stick identity.
USEFUL FOR

Mathematicians, students studying combinatorics, and anyone interested in understanding binomial identities and their proofs.

Albert1
Messages
1,221
Reaction score
0
prove:
$\sum_{k=0}^{n} \binom{n}{k}^2
=\dfrac{(2n)!}{(n!)^2}$
 
Last edited:
Mathematics news on Phys.org
Albert said:
prove:
$\sum_{k=0}^{n} \binom{n}{k}^2
=\dfrac{(2n)!}{(n!)^2}$

out of 2n objects n objects can be chosen in

$\dfrac{(2n)!}{(n!)^2}$ ways

now let us make 2n objects into 2 groups of n objects each.

for picking n objects from the set we need k objects from 1st set and n-k from 2nd set and n varies from 0 to n so number of ways

$\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$

the 2 above are same as it shows the number of ways in 2 different ways

so
$\dfrac{(2n)!}{(n!)^2}= \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$

now as $\binom{n}{k} = \binom{n}{n-k}$ so we get the result
 
kaliprasad said:
out of 2n objects n objects can be chosen in

$\dfrac{(2n)!}{(n!)^2}$ ways

now let us make 2n objects into 2 groups of n objects each.

for picking n objects from the set we need k objects from 1st set and n-k from 2nd set and n varies from 0 to n so number of ways

$\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$

the 2 above are same as it shows the number of ways in 2 different ways

so
$\dfrac{(2n)!}{(n!)^2}= \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$

now as $\binom{n}{k} = \binom{n}{n-k}$ so we get the result
nice solution !
 

Similar threads

MHB Calculating $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proving $\dfrac{(n-1)^{2n-2}}{(n-2)^{n-2}}<n^n$ for $n\ge 3$
  • · Replies 1 ·
Replies
1
Views
985
MHB Binomial Sum \displaystyle \sum^{n}_{k=0}\binom{n+k}{k}\cdot \frac{1}{2^k}
  • · Replies 1 ·
Replies
1
Views
2K
MHB Prove Summation Inequality: $\frac{1}{2n-1} > \sum_{k=n}^{2n-2}\frac{1}{k^2}$
  • · Replies 9 ·
Replies
9
Views
2K
MHB Summation Challenge: Evaluate $\sum_{n=0}^\infty \frac{16n^2+20n+7}{(4n+2)!}$
  • · Replies 1 ·
Replies
1
Views
1K
MHB What are the values of n and k in n+8=2^k when n!+8 = 2^k?
  • · Replies 8 ·
Replies
8
Views
2K
MHB Inequality Challenge: Prove $\sum_{1}^{n}$
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Limit of ##i^\frac{1}{n}## as ##n \to \infty##
  • · Replies 14 ·
Replies
14
Views
2K
MHB Compute $\sum_{n=1}^{2020} (f(n)-g(n))$
  • · Replies 1 ·
Replies
1
Views
1K
MHB Trigonometric Sum Challenge Σtan^(-1)(1/(n^2+n+1)=π/2
  • · Replies 3 ·
Replies
3
Views
2K