Summing nCr

By William Johnson (P2617) on Tuesday, August 15, 2000 - 04:20 am :

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

Why, and can this be extrapolated to anything else?

By The Editor :

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

By Brad Rodgers (P1930) on Tuesday, August 15, 2000 - 11:15 pm :

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

Thanks,

Brad

By Sean Hartnoll (Sah40) on Tuesday, August 15, 2000 - 11:38 pm :

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

By Dan Goodman (Dfmg2) on Tuesday, August 15, 2000 - 01:51 pm :

I think the best way to think of this is in terms of power sets and subsets. If

N = {1, 2, 3, \dots, n}

, how many subsets of

N

are there? One way of answering this is to say, how many subsets of size

k

are there, and it's the number of ways of picking

k

elements from

n

, i.e.

nCk

. So the total number of subsets is the sum from

k = 0

n

nCk

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 \to {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 \times 2 \times 2 \times \dots \times 2 = 2^{n}$ different indicator functions. Therefore the number of subsets of $N$ is $2^{n} =$ sum from $r = 0$ to $n$ of $nCr$ . Tada!

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

By Arvan Pritchard (T708) on Tuesday, August 15, 2000 - 02:05 pm :

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.

By Michael Doré (P904) on Tuesday, August 15, 2000 - 03:27 pm :

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

By Neil Morrison (P1462) on Tuesday, August 15, 2000 - 06:37 pm :

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.

By Michael Doré (P904) on Wednesday, August 16, 2000 - 12:17 am :

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 (2 π / 3) + i \sin (2 π / 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) + \dots = 1 / 3 (2^{n} + 2 (- 1)^{n} \cos (2 n π / 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 - 1} \cos (π n / 4) = C (n, 0) + C (n, 4) + \dots$
And you could go on and fish out the multiples of 4,5 etc.

Michael

By Neil Morrison (P1462) on Wednesday, August 16, 2000 - 07:46 pm :

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