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}$

#Combinatorics #BinomialCoefficients #Powersof2

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

$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}$

U Z - 6 years, 4 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.

Siddhartha Srivastava - 6 years, 4 months ago

brilliant :D

Aritra Jana - 6 years, 4 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 ......

Mohamed Ammar - 6 years, 4 months ago

Math	Appears 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}$