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.

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

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.

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

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!

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.

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$

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]

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

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

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.

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$

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

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)

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)

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.

Easy Math Editor

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:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

Log in to reply

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

Log in to reply

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!

Log in to reply

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.

Log in to reply

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

Log in to reply

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$

Log in to reply

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

Log in to reply

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]

Log in to reply

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

Log in to reply

If n is even e.g. n = 6

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

Log in to reply

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

Log in to reply

Not 'logical reasoning', algebraic reasoning.

Log in to reply

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

Log in to reply

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.

Log in to reply

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

Log in to reply

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$Log in to reply

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

Log in to reply

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)

Log in to reply

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)

Log in to reply

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.

Log in to reply