It seems that 2ⁿ = The summation between 0 and n of nCr.

Why, and can this be extrapolated to anything else?

This is equivalent to saying that the (n+1)th row of Pascal's triangle adds up to 2ⁿ .

Sorry to have to ask, but what does the question mean (summation between 0 and n of nCr)?

Thanks,

Brad

Brad -

summation between 0 and n of nCr
= nC0 + nC1 + nC2 + ... + nC(n-1)+ nCn

Where in each term nCr is the number of ways of choosing r elements from a set of n, and is given by

nCr = (n!)/((n-r)! r!)

Where n! is the factorial function:

n! = n (n-1) (n-2) ... 1.

Hope this helps, (perhaps you can work out why nCr is the number of ways of choosing r elements)

Sean

There is another way of answering the question though, which is to use indicator functions. If U is a subset of N, the indicator function I_U:N®{0,1}(x) (where x is in N) takes the value 1 if x is in U or 0 if x isn't in U. Clearly, each subset has a unique indicator function I_U and each indicator function has a unique subset U, so there are the same number of indicator functions and subsets. Now we just have to count the number of indicator functions there are. The domain of the indicator functions is 1, 2, 3, ..., n and it can be either 1 or 0 each time, so there are 2×2×2×¼×2 = 2ⁿ different indicator functions. Therefore the number of subsets of N is 2ⁿ= sum from r=0 to n of nCr. Tada!

I don't remember any similar results, although I'm pretty sure there are some.

Another way to look at it is to use the expansion of (x+y)ⁿ - the coefficient of x^k y^n-k is ⁿ C_k [because you have to pick the x from k of the factors] then set x=y=1.

Alternatively we can do it by induction. We use the result:

C(n,r) = C(n-1,r) + C(n-1,r-1)

where C(n,r) = n choose r. (This result is why Pascal's triangle works.)

Now suppose the result holds for n = k:

C(k,0) + C(k,1) + ... + C(k,k) = 2^k

Multiply by 2:

2C(k,0) + 2C(k,1) + ... + 2C(k,k) = 2^(k+1)

C(k,0) + (C(k,0)+C(k,1)) + (C(k,1)+C(k,2)) + ... (C(k,k-1)+C(k,k)) + C(k,k) = 2^(k+1)

So:

C(k,0) + C(k+1,1) + C(k+1,2) + C(k+1,3) + ... + C(k+1,k) + C(k,k) = 2^(k+1)

But C(k,0) = C(k+1,0) = C(k,k) = C(k+1,k+1) = 1 so:

C(k+1,0) + C(k+1,1) + C(k+1,2) + ... + C(k+1,k+1) = 2^(k+1)

So if the proposition holds for n = k it also holds for n = k+1. And it obviously holds for n = 1 so that completes the induction.

But I do prefer Dan or Arvan's way of doing it (which are really totally analogous to each other) as it gives you some idea of why it works too.

Yours,

Michael

I think there is some other relation between the sums of nCx where x is an integer:

Don't quote me on this, but I seem to remember that the sum of all the odd 'x's = the sum of all even 'x', or something similar.

Neil,

Well

(1-x)ⁿ = C(n,0) - C(n,1)x + C(n,2)x² + ... + (-1)ⁿ C(n,n)xⁿ

So setting x = 1:

0 = C(n,0) - C(n,1) + C(n,2) - ...

and

C(n,0) + C(n,2) + ... = C(n,1) + C(n,3) + ...

Therefore:

C(n,0) + C(n,2) + ... = 2^n-1

And I guess we can distill the multiples of 3 (i.e. find C(n,0) + C(n,3) + ...) using complex numbers.

Let w=cos(2p/3)+isin(2p/3)
Now:

(1+x)ⁿ = C(n,0) + C(n,1)x + C(n,2)x² + C(n,3)x³ + ... + C(n,n)xⁿ
(1+xw)ⁿ = C(n,0) + wC(n,1)x + w² C(n,2)x² + C(n,3)x³ + ... + wⁿ C(n,n)xⁿ
(1+xw² )ⁿ = C(n,0) + w² C(n,1)x + w C(n,2)x² + C(n,3)x³ + ... + w²ⁿ C(n,n)xⁿ

Add and set x = 1:

2ⁿ + (1+w)ⁿ + (1+w² )ⁿ = 3[C(n,0) + C(n,3) + C(n,6) + ...]

But 1 + w = -w² , 1+w² = -w so:

2ⁿ + (-w² )ⁿ + (-w)ⁿ = 3[C(n,0) + C(n,3) + ...]

We can take the (-1)ⁿ outside the brackets, write w² = w^-1 and hence obtain:

C(n,0)+C(n,3)+¼ = 1/3(2ⁿ+2(-1)ⁿcos(2np/3)]
Now to fish out C(n,0) + C(n,4) + ... we consider the following:

(1+x)ⁿ = C(n,0) + C(n,1)x + C(n,2)x² + ... + C(n,n)xⁿ
(1+xi)ⁿ = C(n,0) + iC(n,1)x -C(n,2)x² + ... + iⁿ C(n,n)xⁿ
(1-x)ⁿ = C(n,0) -C(n,1)x + C(n,2)x² - ... + (-1)ⁿ C(n,n)xⁿ
(1-xi)ⁿ = C(n,0) -iC(n,1)x -C(n,2)x² - ... + (-i)ⁿ C(n,n)xⁿ

Set x = 1 and add:

2ⁿ + (1+i)ⁿ + (1-i)ⁿ = 4[C(n,0) + C(n,4) + ...]

So:

2^n-2+2^n/2-1cos(pn/4)=C(n,0)+C(n,4)+¼
And you could go on and fish out the multiples of 4,5 etc.

Michael

Yes, that's where I found the result (I had glanced over it before, but couldn't remember anything about it.)