Logical Explanation

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.

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.

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

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$

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

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

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

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

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

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