×

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

Sort by:

$$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}$$ · 2 years, 5 months ago

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. · 2 years, 5 months ago

brilliant :D · 2 years, 5 months ago