Logical Explanation

Explain logically, not algebraically, why $\dbinom{n}{1}+\dbinom{n}{3}+\dbinom{n}{5}...= 2^{n-1}$ By logically I mean, some argument by which we can calculate the sum orally.

5 years, 7 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:

Flip n coins. Clearly, there are 2^n strings of head and tails possible.

There are n C 1 strings with exactly 1 head, nC3 with 3 heads, and so on.

Observe that the probability of getting an odd number of heads is precisely half (by a variety of arguments like induction, recursion, or plain obviousness). This gives you the desired result.

- 5 years, 7 months ago

Only, induction and recursive should not be considered as 'logical reasoning'(though of course it is logical. ), and should be considered as 'mathematical reasoning'

- 5 years, 7 months ago

That's quite good thinking. I have an argument that'll give us the answer quickly. All we want is the number of odd selections out of a total of $$n$$. Fix any object $$x_n$$ out of the $$n$$ objects. Now the total number of strings possible for the remaining $$n-1$$ elements are $$2^{n-1}$$. Take any possible string of the total strings possible. If the set contains odd number of elements, then keep it as it is, otherwise add $$x_n$$. We see there's a perfect pairing. So we are done!

- 5 years, 7 months ago

We have to find $$\sum_{k\ge0} \binom{n}{2k+1}$$ . Now imagine this like this , Suppose you have to choose number of groups of size $$2k+1$$ from n number of students . Now for each $$k$$ you have some number of groups , symoblically $$0 \le 2k+1 \le n$$ , there are $$\binom{n}{2k+1}$$ groups of size $$2k+1$$ , so there are $$\sum_{k \ge 0} \binom{n}{2k+1}$$ such type of groups .

Now we do this sum , logically . For $$n-1$$ students there is a choice , for taking him in the group or not. so $$2^{n-1}$$ . Once these choices are made, then the fate of the nth student is completely determined so that the final group size is an odd number. Consequently, there are $$2^{n-1}$$ such committees. $$\Box$$

- 5 years, 7 months ago

Actually people wouldn't have been confused if you said "combinatorial proof" instead of "logical explanation".

- 5 years, 7 months ago

Take n balls numbered from 1 to n. Take $$n_{th}$$ ball and put it aside. Split the rest of the $$n-1$$ balls into two sets - set A and set B. There are $$2^{n-1}$$ ways to do that which is our R.H.S. Now take $$n_{th}$$ ball which we have set aside initially and put in to either set A or set B so that number of balls in set A is odd. So, basically we have chosen odd number of balls from n balls in set A, which is the L.H.S. Hence the equation is proved. [EDIT] I should have read the comments first :S, Vikram W. has provided almost the solution as mine.

- 5 years, 7 months ago

This solution is half 'mathematical', half 'logical'. From binomial expansion the sum of nCr = $$2^{n}$$. Now the sum given is equal to the sum that has been removed as nCr = nC(n-r) (i.e. nC1 = nC(n-1)). Hence, the sum is equal to $$\frac{1}{2}$$ * $$2^{n}$$ = $$2^{n-1}$$, as required.

- 3 years, 11 months ago

we know that the total number of subsets of a set containing n elements is 2^n.

Also, the sum of the subsets containing odd elements = sum of the subsets containing even elements.

So we have ,

n C 1 + n C 3 + n C 5 + n C 7 +....= n C 0 + n C 2 + n C 4 + n C 6 +...

again,

n C 1 + n C 2 + n C 3 + n C 4 + n C 5 + ... n C n = 2^n or, 2(n C 1 + n C 3 + n C 5 + n C 7 +....) = 2^n or n C 1 + n C 3 + n C 5 + n C 7 +....= 2^(n-1)

- 5 years, 6 months ago

we know that the total number of subsets of a set containing n elements = 2^n Again we know that the sum of the total number of odd element subset = the sum of the total number of even element subset so n C 1 + n C 2 + n C 3 + ... + n C n = 2^n or , 2 ( n C 1 + n C 3 + n C 5 + ... ) = 2^n or, n C 1 + n C 3 + n C 5 + ... = 2^n / 2 = 2^(n-1)

- 5 years, 6 months ago

((1+x)^n+(1-x)^n)/2=2^(n-1), for x=1 here n is taken positive complete number.Sum of the combinations of n items taking odd number of items(which is less or equal to the number of items) at a time is 2^(n-1). Example: n=4, 4C1+4C3=8=2^(4-1)=8, and so on.

- 5 years, 6 months ago

This can also be used to prove why there exists $$2^n$$ subsets in a set.

- 5 years, 7 months ago

Yeah. We consider $$n$$ objects. Assume you want to make a team out of them consisting of any number of objects. Each object can be given a label 'Yes' or 'No' based on whether it is selected or not. So the total number of possible teams is $$\underbrace{2*2*2...*2}_\text{n times}=2^n$$

- 5 years, 6 months ago

i think the (1-1)^n explanation makes perfect sense, but if you want something "logical" then consider the construction of pascal's triangle. When a row goes to the next row, each term on it is added to two consecutive terms in the next row, and as of course one of these is odd and one is even, the even and odd terms have the same sum. There is also the committee argument which this is pretty much equivalent to, and I'm sure several other clever bijections. What's notable about the generating function is that it generalizes easily, say by changing to (2-1)^n. These are both special cases of roots of unity filters, which are very intuitive.

- 5 years, 7 months ago

$${n \choose {2k-1}}= {{n-1} \choose {2k-1}}+ {{n-1} \choose {2k-2}}$$, and as we apply it to all, it becomes the sum of n-1 choose 0 through n-1 choose N-1, so it is $$2^{n-1}$$

- 5 years, 7 months ago

that is, by binomial theorem, ((1+1)^n-(1-1)^n)/2=2^(n-1)

- 5 years, 7 months ago

Not 'logical reasoning', algebraic reasoning.

- 5 years, 7 months ago

Alternatively, it is known that the sum of N choose 0 through N choose N is $$2^{N}$$. We also know that N choose K is the same thing as $$N \choose N-K$$. So we conclude that N choose 0=N choose N and N choose 1 = N choose N-1 thus the stated problem is half of $$2^{n}$$.

- 5 years, 7 months ago

If n is even e.g. n = 6

nC1 = nC5; but both are in the set. This idea does work for odd n though.

- 5 years, 7 months ago

We know that $$N \choose K$$ is part of the binomial theorem. $$(x+y)^{n}= {N \choose 0}*x^N+{N \choose 1}*x^{N-1}*y+....{N \choose N}*y^{N}$$. Let x and y equal 1 and we see that $$2^{n}={N \choose 0}+{N \choose 1}+...+{N \choose N}$$. By halving both sides we see that $${N \choose 1}+{N \choose 3}+{N \choose 5}+...=2^{n-1}$$.

[Note: In order to type $${ N \choose 1} + {N \choose 3}$$, you need to use { N \choose 1} + { N \choose 3} as the Latex code, otherwise it doesn't know how to write it up. E.g. it could appear as $${ N \choose { 1 + {N\choose 3} } }$$, or any of the other variants - Calvin]

- 5 years, 7 months ago

Another idea: Use the fact that nC0+nC1+...+nCn=2^n and the expansion of 0=(1+(-1))^n by the Binomial Theorem...

- 5 years, 7 months ago