Logical Explanation

Explain logically, not algebraically, why (n1)+(n3)+(n5)...=2n1 \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.

Note by Vikram Waradpande
6 years, 5 months ago

No vote yet
6 votes

  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:

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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.

Gabriel Wong - 6 years, 5 months ago

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'

Zi Song Yeoh - 6 years, 5 months ago

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 nn. Fix any object xnx_n out of the nn objects. Now the total number of strings possible for the remaining n1n-1 elements are 2n12^{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 xnx_n. We see there's a perfect pairing. So we are done!

Vikram Waradpande - 6 years, 5 months ago

Log in to reply

Take n balls numbered from 1 to n. Take nthn_{th} ball and put it aside. Split the rest of the n1n-1 balls into two sets - set A and set B. There are 2n12^{n-1} ways to do that which is our R.H.S. Now take nthn_{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.

Md. Imrul Hassan - 6 years, 5 months ago

Log in to reply

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

Abhishek De - 6 years, 5 months ago

Log in to reply

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

Now we do this sum , logically . For n1 n-1 students there is a choice , for taking him in the group or not. so 2n1 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 2n1 2^{n-1} such committees. \Box

Shivang Jindal - 6 years, 5 months ago

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

André Macedo - 6 years, 5 months ago

Log in to reply

We know that (NK)N \choose K is part of the binomial theorem. (x+y)n=(N0)xN+(N1)xN1y+....(NN)yN (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 2n=(N0)+(N1)+...+(NN)2^{n}={N \choose 0}+{N \choose 1}+...+{N \choose N}. By halving both sides we see that (N1)+(N3)+(N5)+...=2n1{N \choose 1}+{N \choose 3}+{N \choose 5}+...=2^{n-1}.

[Note: In order to type (N1)+(N3) { 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 (N1+(N3)) { N \choose { 1 + {N\choose 3} } } , or any of the other variants - Calvin]

Alexander Sludds - 6 years, 5 months ago

Log in to reply

Alternatively, it is known that the sum of N choose 0 through N choose N is 2N2^{N}. We also know that N choose K is the same thing as (NNK)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 2n2^{n}.

Alexander Sludds - 6 years, 5 months ago

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.

Gabriel Wong - 6 years, 5 months ago

Log in to reply

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

Diego Roque - 6 years, 5 months ago

Log in to reply

Not 'logical reasoning', algebraic reasoning.

Zi Song Yeoh - 6 years, 5 months ago

Log in to reply

(n2k1)=(n12k1)+(n12k2) {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 2n12^{n-1}

Diego Roque - 6 years, 5 months ago

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.

Jacob Gurev - 6 years, 5 months ago

Log in to reply

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

Thaddeus Abiy - 6 years, 4 months ago

Log in to reply

Yeah. We consider nn 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 222...2n times=2n\underbrace{2*2*2...*2}_\text{n times}=2^n

Vikram Waradpande - 6 years, 4 months ago

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.

Md Abul Kalam Azad - 6 years, 4 months ago

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)

Sagnik Saha - 6 years, 4 months ago

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)

Sagnik Saha - 6 years, 4 months ago

Log in to reply

This solution is half 'mathematical', half 'logical'. From binomial expansion the sum of nCr = 2n2^{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 12\frac{1}{2} * 2n2^{n} = 2n12^{n-1}, as required.

Curtis Clement - 4 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...