×

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$$

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

brilliant :D

- 2 years, 10 months ago

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 ......

- 2 years, 10 months ago