Find the number of ways an odd number of objects can be chosen

[zorro]

Homework Statement

Find the number of ways in which an odd number of objects can be chosen from n objects.

The Attempt at a Solution

We have 2 cases-

1) n is even

nC1 + nC3 + nC5 + ... nCn-1

2) n is odd

nC1 + nC3 + nC5 + ... nCn

I think adding them will give the answer.
How do I find out the sum?

 

[tiny-tim]

Hi Abdul!

Hint: for n odd, it's easy!

(if you can't see it immediately, try a few examples … in fact, trying a few examples is often a good idea anyway)

 

[zorro]

I used binomial expansions and surprisingly, got both of them as 2^n-1.

 

[tiny-tim]

Since that's half of 2ⁿ, that's not at all surprising for odd n …

can you see why? ​

 

[zorro]

Its obvious for odd n, what about even n?

 

[tiny-tim]

sorry, are you saying you can see it's obvious for odd n, or not?

 

[zorro]

Yeah I can see it's obvious for odd n.
In the expansion of (1+x)ⁿ, the number of terms are n+1 = even number of terms , n being odd.

Of these even number of terms, half correspond to choosing odd number of objects and half correspond to choosing an even number of objects. Sum of any half = 2^n-1

If n is even ( as in the case 1 ), how do you justify 2^n-1 (the answer I got)?

 

[tiny-tim]

Hi Abdul!

Of these even number of terms, half correspond to choosing odd number of objects and half correspond to choosing an even number of objects. Sum of any half = 2^n-1

Yes, that's right.

But I can't see an obvious way of proving it for even n

(maybe someone else can? )

though I can see a neater maths way … consider (1 + 1)ⁿ + (1 - 1)ⁿ

 

[verty]

Hint: Use Pascal's rule.