Solveeit Logo
Login

Question

Question: Prove that \(\dfrac{\left( 2n \right)!}{n!}={{2}^{n}}\left( 1\times 3\times 5\times \cdots \left( 2n...

Prove that (2n)!n!=2n(1×3×5×⋯(2n−1))\dfrac{\left( 2n \right)!}{n!}={{2}^{n}}\left( 1\times 3\times 5\times \cdots \left( 2n-1 \right) \right)

Explanation

Solution

Hint: Use the fact that n!=n(n−1)!n!=n\left( n-1 \right)!. Hence write (2n)! as (2n)(2n-1)(2n-2)…(2)(1)
Now from every even term(2n,2n-2,2n-4,…) take 2 as common. Argue that there will be n such terms. Hence prove that (2n)!=2n(1×3×5×⋯(2n−1))(1×2×⋯×n)\left( 2n \right)!={{2}^{n}}\left( 1\times 3\times 5\times \cdots \left( 2n-1 \right) \right)\left( 1\times 2\times \cdots \times n \right)
Divide both sides by n! and hence prove that (2n)!n!=2n(1×3×5×⋯×(2n−1))\dfrac{\left( 2n \right)!}{n!}={{2}^{n}}\left( 1\times 3\times 5\times \cdots \times \left( 2n-1 \right) \right)

Complete step-by-step answer:
We know that n!=n(n−1)!n!=n\left( n-1 \right)!
Hence, we have (2n)!=2n(2n−1)!\left( 2n \right)!=2n\left( 2n-1 \right)!
Continuing this way, we get
(2n)!=2n(2n−1)(2n−2)⋯(2)(1)\left( 2n \right)!=2n\left( 2n-1 \right)\left( 2n-2 \right)\cdots \left( 2 \right)\left( 1 \right)
Writing even terms first and then the odd terms(This can be done since multiplication is both commutative and associative), we get
(2n)!=[(2n)(2n−2)(2n−4)⋯2][(2n−1)(2n−3)⋯(1)]\left( 2n \right)!=\left[ \left( 2n \right)\left( 2n-2 \right)\left( 2n-4 \right)\cdots 2 \right]\left[ \left( 2n-1 \right)\left( 2n-3 \right)\cdots \left( 1 \right) \right]
Taking 2 common from each of the even terms, we get
(2n)!=[2(n)(2)(n−1)(2)(n−2)⋯(2)(1)][(2n−1)(2n−3)⋯(1)]\left( 2n \right)!=\left[ 2\left( n \right)\left( 2 \right)\left( n-1 \right)\left( 2 \right)\left( n-2 \right)\cdots \left( 2 \right)\left( 1 \right) \right]\left[ \left( 2n-1 \right)\left( 2n-3 \right)\cdots \left( 1 \right) \right]
From 1 to n, we have n terms. Hence there are n 2s in the product.
Hence, we have
(2n)!=[2n(1×2×⋯×n)][(2n−1)(2n−3)⋯(1)]\left( 2n \right)!=\left[ {{2}^{n}}\left( 1\times 2\times \cdots \times n \right) \right]\left[ \left( 2n-1 \right)\left( 2n-3 \right)\cdots \left( 1 \right) \right]
We know that 1×2×3⋯(n)=n!1\times 2\times 3\cdots \left( n \right)=n!
Hence, we have
(2n)!=[2nn!][(2n−1)(2n−3)⋯(1)]\left( 2n \right)!=\left[ {{2}^{n}}n! \right]\left[ \left( 2n-1 \right)\left( 2n-3 \right)\cdots \left( 1 \right) \right]
Dividing both sides by n!, we get
(2n)!n!=2n(1×3×5×⋯(2n−1))\dfrac{\left( 2n \right)!}{n!}={{2}^{n}}\left( 1\times 3\times 5\times \cdots \left( 2n-1 \right) \right)
Q.E.D

Note: Alternative Solution:
We know that the power of prime p in n! is given by e=[np]+[np2]+⋯e=\left[ \dfrac{n}{p} \right]+\left[ \dfrac{n}{{{p}^{2}}} \right]+\cdots , where [x] denotes the greatest integer less or equal to x.
Since 2 is prime, we have
Power of 2 in (2n)! is equal to [2n2]+[2n22]+[2n23]+⋯\left[ \dfrac{2n}{2} \right]+\left[ \dfrac{2n}{{{2}^{2}}} \right]+\left[ \dfrac{2n}{{{2}^{3}}} \right]+\cdots
Similarly, we have the power of 2 in n! is equal to [n2]+[n22]+⋯\left[ \dfrac{n}{2} \right]+\left[ \dfrac{n}{{{2}^{2}}} \right]+\cdots
Hence, the power of 2 in (2n)!n!\dfrac{\left( 2n \right)!}{n!} is equal to [2n2]+[2n22]+[2n23]+⋯−[n2]+[n22]+⋯\left[ \dfrac{2n}{2} \right]+\left[ \dfrac{2n}{{{2}^{2}}} \right]+\left[ \dfrac{2n}{{{2}^{3}}} \right]+\cdots -\left[ \dfrac{n}{2} \right]+\left[ \dfrac{n}{{{2}^{2}}} \right]+\cdots
Hence, we have
Power of 2 in (2n)!n!\dfrac{\left( 2n \right)!}{n!} is equal to
n+[n2]+[n22]+⋯−[n2]−[n22]⋯=nn+\left[ \dfrac{n}{2} \right]+\left[ \dfrac{n}{{{2}^{2}}} \right]+\cdots -\left[ \dfrac{n}{2} \right]-\left[ \dfrac{n}{{{2}^{2}}} \right]\cdots =n
The remaining terms in (2n)!n!\dfrac{\left( 2n \right)!}{n!} are all odd numbers from 1 to 2n-1.
Hence, we have
(2n)!n!=2n(1×3×5×⋯(2n−1))\dfrac{\left( 2n \right)!}{n!}={{2}^{n}}\left( 1\times 3\times 5\times \cdots \left( 2n-1 \right) \right)
Hence proved.