Waste less time on Facebook — follow Brilliant.
×

Binomial or Combi?

Prove that:

\(\large{ \binom{2n}{n}- \binom{n}{1}. \binom{2n-2}{n}+ \binom{n}{2}. \binom{2n-4}{n}- \dots }\)

reduces to: \(2^{n}\)

Note by Aritra Jana
2 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

\(Let~\boxed{coefficient~ of~ x^n ~ = a}\)

We can see that -

\(\large{ \binom{2n}{n}- \binom{n}{1}. \binom{2n-2}{n}+ \binom{n}{2}. \binom{2n-4}{n}- \dots }\)

\( = a~ in~(1+x)^{2n} - \binom{n}{1}(a~ in~ (1 + x)^{2n - 2}) + \binom{n}{2}(a~ in~(1+x)^{2n - 4} - \cdots\)

\( =~ coefficient~ of~ x^n ~in~ \left( (1+x)^{2n} - \binom{n}{1}(1 + x)^{2n - 2} + \binom{n}{2}(1+x)^{2n - 4} - \cdots \right)\)

\( = ~ coefficient~ of~ x^n ~in ~ ((1 + x)^2 - 1)^n\)

\( = ~ coefficient~ of~ x^n~ in~x^n(2+x)^n\)

\(= ~constant~term~in(2+x)^n = \boxed{2^n}\) Megh Choksi · 2 years, 3 months ago

Log in to reply

Combinatorical solution:-

I'm using \( [1,2,3] \) to denote a set with elements \( 1,2,3 \). I can't seem to type the curly brackets. :/

Let \( S = [-1,-1,2,-2,...,n,-n] \). Let us find the number of ways to pick \( n \) numbers from \( S \) such that, for all \( x \leq n \), either \( x \) or \( -x\) is chosen, if not both.

Then there are two ways to count the total number of subsets possible.

Case 1:- We count by PIE. Let \( A \) denote the set of ways to pick \( n \) numbers from \( S \). Let \( A_i \) denote the set of ways to pick \( n \) numbers without picking either \( i \) or \( - i \).

Then we need to find \( |A| - | A_1 \cup A_2 \cup ... \cup A_n| \) .

\( |A| \) is simply \( \binom{2n}{n} \)

Since \( |A_i| \) is the number of ways to pick \( n \) numbers from \( S - [i,-i] \), it is obviously \( \binom{2n-2}{n} \). And the number of ways to choose the index \( i \) is \( \binom{n}{1} \). Therefore \( \sum|A_i| = \binom{2n-2}{n} * \binom{n}{1} \).

Likewise, \( |A_i| \cap |A_j| \) is the number of ways to pick n numbers from \( S - [i,-i,j,-j] \), which is \( \binom{2n-4}{n} \). And the number of ways to choose unequal indexes \( i,j \) is \( \binom{n}{2} \). Therefore \( \sum|A_i| \cap |A_j| = \binom{2n-4}{n} * \binom{n}{2} \).

By the same logic, \( |A_{a_1}| \cap |A_{a_2}| \cap ... \cap |A_{a_x}| \), is equal to \( \binom{2n-2x}{n} \). And the number of ways to choose unequal indexes is \( \binom{n}{x} \). Therefore \( \sum|A_{a_1}| \cap |A_{a_2}| \cap ... \cap |A_{a_x}| = \binom{2n-2x}{n} * \binom{n}{x} \).

Therefore, by PIE,

\( | A_1 \cup A_2 \cup ... \cup A_n| = \sum|A_i| - \sum (|A_i| \cap |A_j| )... \)

\( \implies | A_1 \cup A_2 \cup ... \cup A_n| = \binom{2n-4}{n} * \binom{n}{2} - \binom{2n-4}{n} * \binom{n}{2} + ... \)

And \( |A| - | A_1 \cup A_2 \cup ... \cup A_n| = \binom{2n}{n} - \binom{2n-4}{n} * \binom{n}{2} + \binom{2n-4}{n} * \binom{n}{2} - ... \)

Case 2:-. This one is thankfully shorter. We can see that we can choose one and only one element from each of the sets \( [1,-1],[2,-2],...,[n,n] \). The number of ways to do this is \( 2^n \).

Since we're counting the same thing. Both must be equal. Siddhartha Srivastava · 2 years, 3 months ago

Log in to reply

@Siddhartha Srivastava brilliant :D Aritra Jana · 2 years, 3 months ago

Log in to reply

Consider the expansion of (2x+x2)n =[(1+x)2-1]n So coefficient of xn in left hand side is 2power n and it should be equal to coefficient of xn in right hand side [(1+x)2-1]n = Co (1+x)2n - C1 (1+x)2n-2 + C2(1+x)2n-4....... = Co 2nCn - C1 2n-2Cn + C2 2n-4Cn ...... Mohamed Ammar · 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...