Waste less time on Facebook — follow Brilliant.
×

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.

Note by Vikram Waradpande
4 years ago

No vote yet
6 votes

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 · 4 years ago

Log in to reply

@Gabriel Wong 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 · 4 years 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 \(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! Vikram Waradpande · 4 years ago

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 \) Shivang Jindal · 4 years ago

Log in to reply

Actually people wouldn't have been confused if you said "combinatorial proof" instead of "logical explanation". Abhishek De · 4 years ago

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. Md. Imrul Hassan · 4 years ago

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. Curtis Clement · 2 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 · 4 years 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 · 4 years 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 · 4 years ago

Log in to reply

This can also be used to prove why there exists \(2^n\) subsets in a set. Thaddeus Abiy · 4 years ago

Log in to reply

@Thaddeus Abiy 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\) Vikram Waradpande · 4 years 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 · 4 years ago

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}\) Diego Roque · 4 years ago

Log in to reply

that is, by binomial theorem, ((1+1)^n-(1-1)^n)/2=2^(n-1) Diego Roque · 4 years ago

Log in to reply

@Diego Roque Not 'logical reasoning', algebraic reasoning. Zi Song Yeoh · 4 years ago

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}\). Alexander Sludds · 4 years ago

Log in to reply

@Alexander Sludds 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 · 4 years ago

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] Alexander Sludds · 4 years 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 · 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...