A question about factorials, nCr

[davon806]

Homework Statement

Hi,I found this problem when I was reading a book,I knew the answer but there is one thing that I don't understand.Here is the question:

Given C(2015,m),find the smaller of m such that C(2015,m) is an even number

Homework Equations

The Attempt at a Solution

Here is the answer:(sorry for being quite messy)

Expand C(2015,m),which gives:

(2015)(2014)... (numerator)
m(m-1)(m-2)...(4)(3)(2)(1)...(2015-m)(2015-m+1)... (denominator)

After some arrangement it becomes:
(2015)(2014)...(2015-(m-1))
m(m-1)...(4)(3)(2)(1)

which is :
(2015)(2014)...(2016-m)
(1)(2)(3)(4)...(m)

In my book,the answer said the first even number occurs when (2016-m)/m is an even number
Therefore 2016/m - 1 must be even,then 2016/m must be odd.
Since 2016 = 2^5 * 63,the smallest number of m is 2^5 = 32

My question:
I know the answer is correct.However,let's just expand a few terms up to 2011 (i.e.m=5)

(2015)(2014)(2013)(2012)(2011)
(5) (4) (3) (2) (1)

which gives:

(403)(1007)(671)(503)(2011) = 2.75*(10^14)

Since m is small,the final product C(2015,m) has a high chance to be an integer as the factors in the denominator is quite small.
However,how can we ensure this is still the case when m is large(Just say m=32 given in my case),could it be a fraction instead of an even number?There might be terms like (1984/19) which makes the final term neither odd nor even.

Thanks very much.

 

[Ray Vickson]

Homework Statement

Hi,I found this problem when I was reading a book,I knew the answer but there is one thing that I don't understand.Here is the question:

Given C(2015,m),find the smaller of m such that C(2015,m) is an even number

Homework Equations

The Attempt at a Solution

Here is the answer:(sorry for being quite messy)

Expand C(2015,m),which gives:

(2015)(2014)... (numerator)
m(m-1)(m-2)...(4)(3)(2)(1)...(2015-m)(2015-m+1)... (denominator)

After some arrangement it becomes:
(2015)(2014)...(2015-(m-1))
m(m-1)...(4)(3)(2)(1)

which is :
(2015)(2014)...(2016-m)
(1)(2)(3)(4)...(m)

In my book,the answer said the first even number occurs when (2016-m)/m is an even number
Therefore 2016/m - 1 must be even,then 2016/m must be odd.
Since 2016 = 2^5 * 63,the smallest number of m is 2^5 = 32

My question:
I know the answer is correct.However,let's just expand a few terms up to 2011 (i.e.m=5)

(2015)(2014)(2013)(2012)(2011)
(5) (4) (3) (2) (1)

which gives:

(403)(1007)(671)(503)(2011) = 2.75*(10^14)

Since m is small,the final product C(2015,m) has a high chance to be an integer as the factors in the denominator is quite small.
However,how can we ensure this is still the case when m is large(Just say m=32 given in my case),could it be a fraction instead of an even number?There might be terms like (1984/19) which makes the final term neither odd nor even.

Thanks very much.

Fact of life: for positive integers N and m (with 0 ≤ m ≤ N), C(N,m) is always an integer.

For instance: C(N,0) = 1 is an integer; C(N,1) = N is an integer; C(N,2) = N(N-1)/2, and one of the factors in the numerator is even; C(N,3) = N(N-1)(N-2)/(3*2), and one of the factors in the numerator is even and one of them is a multiple of 3.

It becomes trickier for m larger than 3, but the result is still true.

Perhaps the easiest way is to do it is to first establish the recursion C(N,m) = C(N-1,m) + C(N-1,m-1), and then use induction on N. That is, given m, let N = m, m+1, m+2, ... .

 

[haruspex]

There are a couple of ways to see it will always be an integer.
If you prove Pascal's relationship C(n,r)=C(n-1,r-1)+C(n-1,r) then inductively they are all integers.
Or consider that if a prime p occurs in some pattern in [1, r] then it occurs in a corresponding pattern in [n-r+1,n]. By that I mean that if p occurs to some power in the lower sequence then there is a corresponding place in the upper sequence where it occurs to at least the same power, and the correspondence is 1-1. That takes a bit of work to make rigorous.