[superprismatic]

Why is it that the binomial coefficient _nC_k is an

odd number if and only if, thinking of the numbers

in their binary representations, k = n AND k ?

[bushindo]

Why is it that the binomial coefficient _nC_k is an

odd number if and only if, thinking of the numbers

in their binary representations, k = n AND k ?

I would like some clarification. What do you mean by 'thinking of the numbers

in their binary representations'? My interpretation is that _nC_k is odd if and only if n = k and k > 0, but that interpretation is clearly false. Clarification would be appreciated. Thanks.

[superprismatic]

I would like some clarification. What do you mean by 'thinking of the numbers

in their binary representations'? My interpretation is that _nC_k is odd if and only if n = k and k > 0, but that interpretation is clearly false. Clarification would be appreciated. Thanks.

I mean that _nC_k is odd if and only if the binary

representation of n contains a 1 in every position

where the binary representation of k contains a 1.

So, for example, if n were 84, 1010100 in binary,

then the only values of k which would make ₈₄C_k

odd is 0,4,16,20,64,68,80 and 84 (binary 0000000,

0000100, 0010000, 0010100, 1000000, 1000100, 1010000,

and 1010100). In terms of the way I said it in the OP,

₈₄C₂₀ is odd because 20 = 84 AND 20

(0010100 = 1010100 AND 0010100). I should have used

parentheses in the OP to make it k = (n AND k).

I hope this makes it clear.

[Molly Mae]

But we should only be concerned with the last bit. If the last bit of k and n are both 0, the number will be even. If the last bit of k and n are both 1, the number will likewise be even. If the last bit are 0 and 1 or 1 and 0, the number will be odd.

[CaptainEd]

Superprismatic, it's amazing to me that (1) this claim is true and (2) someone knows it.

Now that bushindo and molly mae are involved, I expect rapid progress.

All I can contribute right now is this observation.

Call P(m) = power of 2 in m (that is, the number if instances of the factor 2)

Call B(m) = number of 1-bits in m

Then P(m!) = m - B(m)

That is, the power of 2 in m! = m - the number of 1-bits in the number m. For example:

there are 3 1-bits in the number 7, and 7! is divisible by 2^4.

4 = 7 - 3.

Therefore, P( (n-k)! ) = n - k - B(n) + B(k)

And P( n!/k!(n-k)! ) = n - B(n) - ( k - B(k) + (n - k - B(n) + B(k)))

= 2n -2k -2B(n) +2B(k)

=2P(n!) - 2P(k!)

But I can't get from there to seeing how the bits in (k AND n) work to cancel this number to zero.

Hope this helps.

This is interesting, as always. Where do you come up with these things?

Edited September 13, 2011 by CaptainEd

[CaptainEd]

Sorry, bad math.

My calculations for the nCk are bad. They seem to come out to zero, which is false. So please ignore the previous post, except that

P( n! ) = n - B(n)

[CaptainEd]

Sorry to waste your time

error was in P( (n-k)! ). So, to summarize:

P(n!) = n - B(n)

P(_nC_k) = P(n!) - ( P(k!) + P((n-k)!))

= n - B(n) - ( k - B(k) + n-k - B(n-k))

= B(k) - B(n) + B(n-k)

[Guest]

I can prove the ‘if part’ but not the ‘only If part’... Here it goes...

Let's say, N=N1+N2 such that B(N) AND B(N1) = B(N1).

In that case, we can be sure that wherever N1 has 1, N also has 1 in its binary expression. So, when we subtract N1 from N, we will get zeroes at those places but will get 1 wherever N has 1 but N1 has zero. Which means, N2 will also have 1 only at those places, where N already has 1, leading to two conclusions that [b(N) AND B(N2) = B(N2)] and [N2 has 1 only at all those places where N1 doesn’t have but N has].

Now let’s say, N = 2^a¬1 +2^a2 +2^a3 +….+ 2^an, where a1<a2<….<an. So, if we break N1 and N2 also in similar manner, we will obtain exactly same powers of two that we are getting in case of N, with some falling in N1’s expression and some falling in N2’s expression. For example N = 45 = 2^0 +2^2+2^3+2^5. In this case, to satisfy B(N) AND B(N1) = B(N1) we may have N1 = 2^3 and N2 = 2^0+2^2+2^5. We can get similar expressions just by making sure that both conclusions obtained in previous paragraph hold true.

Now, how many factors of 2 will be there in (N!)? It will be [N/2] + [N/2^2] + [N/2^3] +…. +[N/2^an], where [.] denotes greatest integer function. Let’s check the value of [N/2^p]. There can be two cases: either p belongs to the set {a1, a2, a3,…,an} or it does not belong. In first case we can assume ai = p and in second case we can assume that ai<p<ai+1. So, in both cases, [N/2^p] will be {2^(ai+1-p) + 2^(ai+2-p) + ….. 2^(an-p)}.

A similar analysis with N1 will give us same expression but this time with only those powers of 2 which are involved in N1’s expression and are greater than or equal to p. Same will hold true with N2. So, we can be 100% sure that in this case, [N1/2^p] + [N2/2^p] = [N/2^p] for all p with [.] being greatest integer function.

So, if we count total number of factors of 2 in N!, that will also be equal to total number of factors of 2 in (N1! * N2!). Hence, N©N1 (= N!/(N1! * N2!)) will be an odd number.

Only-if part can also be thought in similar way, but would need more exhaustive calculations.

[superprismatic]

Superprismatic, it's amazing to me that (1) this claim is true and (2) someone knows it.

...

This is interesting, as always. Where do you come up with these things?

How do I come up with my problems? Well, I like to keep a few relatively new

expository mathematics texts nearby so that I can fill some of the time slots

in my life. I routinely keep notes as I flip the pages. These notes are usually

the basis of my posted topics. Something that surprises me, like the odd binomial

coefficient thing, usually makes it in one of my topics. So, most of my topics

are not original, but some are. I find my perusal of expository texts gives me

lots of insights. I usually get these books using inter-library loan from

university libraries. I'm glad you like some of this stuff, Captain! Thanks!

[bushindo]

How do I come up with my problems? Well, I like to keep a few relatively new

expository mathematics texts nearby so that I can fill some of the time slots

in my life. I routinely keep notes as I flip the pages. These notes are usually

the basis of my posted topics. Something that surprises me, like the odd binomial

coefficient thing, usually makes it in one of my topics. So, most of my topics

are not original, but some are. I find my perusal of expository texts gives me

lots of insights. I usually get these books using inter-library loan from

university libraries. I'm glad you like some of this stuff, Captain! Thanks!

Let me just chime in and say that I like your puzzles as well. I'm always happy to see new topics that you post. Can you recommend one or two of these expository texts? There are some time slots in my life that I'd like to put to better use.

[superprismatic]

Let me just chime in and say that I like your puzzles as well. I'm always happy to see new topics that you post. Can you recommend one or two of these expository texts? There are some time slots in my life that I'd like to put to better use.

I usually look at the latest publications from the Mathematical Association of America (MAA) which can be found here

and order interesting-looking books designated Dolciani or Problem Books. I order them through my local

county library. By the time I am just about done leafing through those, a new MAA publications catalog comes out with

more good books. I don't usually record in my notes what book the ideas came from, so I don't have a list of books

immediately at hand.

[CaptainEd]

I followed your neat proof, but I had a problem because it depended on a fact that demonstrates my ignorance (as so many do...).

Why is it that the number of factors of 2 in N! is the sum of [N/2^i] for i=1to n ?

I admit that in my note, I stated without proof that it is equal to N minus the number of bits in the number N. I don't understand why that is true, either.

[CaptainEd]

Here's nomenclature, a lemma, and the proof itself.

First, nomenclature.

Let P(n) be the number of factors of 2 in n

Let B(n) be the number of 1-bits in the binary representation of n

proof by induction on n

P(0) = 0 - B(0) = 0 - 0 = 0

P(1) = 1 - B(1) = 1 - 1 = 0

P(2) = 2 - B(2) = 2 - 1 = 1

assume P( k! ) = k - B(k)

(a) By definition, P( (k+1)! ) = P(k+1) + P( k! )

represent k+1 as a*2^i, where a is odd

there are two cases, i>0 and i=0

case i>0)

P(k)=0

P(k+1)=i

binary representation of k ends in 0 followed by i 1-bits

binary representation of k+1 ends in 1 followed by i 0-bits

B(k+1) = B(k) - i + 1

P( (k+1)! ) = P(k!) + P(k+1)---by (a)

=P(k!) + i

=k-B(k)+i

=k- ( B(k)-i )

=k+1 - (B(k)-i+1)

=k+1 - B(k+1)

case i=0

binary representation of k ends in 0

binary representation of k+1 ends in 1

P(k+1)=0

B(k+1)= B(k) + 1

P( (k+1)! ) = P(k!) + P(k+1)--by (a)

=P(k!)

=k - B(k)

=k+1 - (B(k) + 1)

k+1 - B(k+1)

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into (n1-m), (n2-m), and m.

This implies that (n AND (n1-m)) = n1, (n AND (n2-m)) = n2, (n AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1) + P(n2) + B(m)

so

P(n) - (P(n1)+P(n2)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n) - (P(k)+P(n-k)) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

Edited September 14, 2011 by CaptainEd

[CaptainEd]

Finally, the proof

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into n1, n2, and m.

This implies that (n AND (n1-m)) = (n1-m), (n AND (n2-m)) = (n2-m), (n AND m) = m, (n1 AND m) = m, (n2 AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n!) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1!) + P(n2!) + B(m)

so

P(n!) - (P(n1!)+P(n2!)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n!) - ( P(k!)+P((n-k)!) ) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

[Guest]

Finally, the proof

suppose n = n1 + n2, where (n1 AND n2) = m, where m>=0

so the bits of n are partitioned into n1, n2, and m.

This implies that (n AND (n1-m)) = (n1-m), (n AND (n2-m)) = (n2-m), (n AND m) = m, (n1 AND m) = m, (n2 AND m) = m

B(n) = B(n1-m) + B(n2-m) + B(m)

=B(n1) - B(m) + B(n2) - B(m) + B(m)

=B(n1)+B(n2)-B(m)

P(n!) = n-B(n)

=n-( B(n1)+ B(n2) - B(m) )

=n- (B(n1)+B(n2)) + B(m)

= n1 + n2 - (B(n1)+B(n2)) + B(m)

= (n1-B(n1) + (n2-B(n2)) + B(m)

= P(n1!) + P(n2!) + B(m)

so

P(n!) - (P(n1!)+P(n2!)) = B(m)

now, substituting k for n1 and (n-k) for n2, we get

P(n!) - ( P(k!)+P((n-k)!) ) = B(m)

P( nCk ) = B(m)

P( nCk ) = 0 iff B(m) = B(k AND (n-k)) = 0, which occurs exactly when (n AND k) = k

I just took two numbers n1 = 45 (0101101) and n2 = 27 (0011011). So, n = 72 (1001000) and m = 9 (0001001). So, (n1-m) = 45-9 = 36 (0100100) and (n2-m) = 27-9 = 18 (0010010). Now I don't find n AND (n1-m) = (n1-m) and n AND (n2-m) = (n2-m). For me, n AND (n1-m) = n AND (n2-m) = 0.

I think I am confused. Can you please explain these statements with an example?

Also, clarifications of what I said:

Generally, to calculate number of factors of 2 in N!, we used to follow below approach, until you gave your lemma.

Step 1> Find how many even numbers are there between 1 and N. So, divide N by 2. Now N can be odd also. So, we needed to take greatest integer function of that (because unfortunately natural numbers start at odd). So it was [N/2].

Step2> Fine how many numbers are divisible by 4. It will be [N/2^2]. Number of 4 is found because they contribute 1 more factor of two than two itself contributes.

Step 3 onward > Similarly factor of 8 and 16, etc are calculated. We proceed till 2^n where n is maximum but 2^n < N. You can understand this why.

Final step> Add all the numbers obtained in above steps.

I have done the similar thing in my semi-proof.

Finally, it is really great if you got some insight from My proof. :)

[CaptainEd]

Quite right, Swapnil, my assumptions aren't even true, much less conclusions. I'll be back later, I hope...

[bushindo]

I mean that _nC_k is odd if and only if the binary

representation of n contains a 1 in every position

where the binary representation of k contains a 1.

So, for example, if n were 84, 1010100 in binary,

then the only values of k which would make ₈₄C_k

odd is 0,4,16,20,64,68,80 and 84 (binary 0000000,

0000100, 0010000, 0010100, 1000000, 1000100, 1010000,

and 1010100). In terms of the way I said it in the OP,

₈₄C₂₀ is odd because 20 = 84 AND 20

(0010100 = 1010100 AND 0010100). I should have used

parentheses in the OP to make it k = (n AND k).

I hope this makes it clear.

Thanks for sharing these little gems with us, superprimastic. I enjoy the journey greatly, and feel enriched by the experience. Also, thanks for you recommendation. I picked up the Stanford Mathematics Problem Book for my ereader, and look forward to spending some time on it.

Background:

Some notations and general thoughts before we start the proof.

Let P( n, k ) be a binary test for a property defined as follows

P(n, k) = [ (n AND k) == k ]

In other words, P(n, k) returns TRUE if the binary representation of n contains a 1 in every position where the binary representation of k contains a 1, and FALSE otherwise. Using superprimastic's example, if n were 84, 1010100 in binary, then the only values of k which would make P( n, k) = TRUE is 0,4,16,20,64,68,80 and 84 (binary 0000000, 0000100, 0010000, 0010100, 1000000, 1000100, 1010000, and 1010100).

Let f₀( m ) be the position of the right-most digit of 0 in the binary expansion of m. Let f₁( m ) be the position of the right-most digit of 1 in the binary expansion of m. We consider the right-most digit of a binary number to be at position 1, and the second digit from the right to be at position 2, and so on. For instance, f₀( 11001_b ) is equal to 2, and f₁( 11001_b ) is equal to 1, where 11001_b is the binary representation of the decimal number 25.

Another general thing is the process of addition and subtracting 1 to a binary number. The general observations are as follows

1) If m is a binary number, then (m-1) can be obtained by flipping all digits of m from position 1 to f₁( m ).

2) If m is a binary number, then (m+1) can be obtained by flipping all digits of m from position 1 to f₀( m ).

Last general thing is an identity for the binomial coefficient, which is

_n+1C_k = _nC_k + _nC_k-1

So, let's get to the proof.

Claim: _nC_k is odd if and only if P(n, k) == TRUE

Outline of proof:

We prove this using induction. We assume that the claim is true for _nC_k, where k <= n. We then prove that the claim is true for _n+1C_k.

Using the binomial identity, the proof then reduces to proving the following two statements

A) If P(n + 1, k ) = TRUE, then exactly one of P(n , k ) and P(n, k - 1 ) will be TRUE. [ in other words, P(n , k ) XOR P(n, k + 1 ) = TRUE ]

B) If P(n + 1, k ) = FALSE, then either

B.1) P(n , k ) = FALSE and P(n, k - 1 ) = FALSE or

B.2) P(n , k ) = TRUE and P(n, k - 1 ) = TRUE.

Part A:

Let's examine statement A,

If P(n + 1, k ) = TRUE, that implies f₁( n+1) <= f₁( k ), and it is easy to show* the following two statements using the process of adding and subtracting 1 from a binary number

a) If P(n + 1, k ) = TRUE and f₁( n+1) = f₁( k ), then P(n , k ) = FALSE and P(n, k - 1 ) = TRUE

b) If P(n + 1, k ) = TRUE and f₁( n+1) < f₁( k ), then P(n , k ) = TRUE and P(n, k - 1 ) = FALSE,

So, given that the claim is true for _nC_k under induction, the above implies that P(n + 1, k ) = TRUE leads to _n+1C_k being odd.

Part B:

Let's examine statement B. Without loss of generality, we only need to show that if P(n + 1, k ) = FALSE and P(n , k ) = TRUE, then P(n , k - 1 ) = TRUE as well. We're only showing 1 direction but it can be extended both direction using the symmetry _nC_k = _nC_{n - k}.

So P(n + 1, k ) = FALSE and P(n , k ) = TRUE implies that f₀( n ) > f₁( k ). Using the process of adding and subtracting 1 from a binary number, it is easy to show* that P(n , k - 1 ) = TRUE as well.

The above implies that if P(n + 1, k ) = FALSE and one of P(n , k ) = TRUE or P(n, k - 1 ) is TRUE, then the other one is TRUE as well. This implies that if P(n + 1, k ) = FALSE, then _nC_k and _nC_k-1 are either both even or both odd, which leads to _n+1C_k being even.

QED.

Note: The parts that say 'it's easy to show*' are indeed easy to work out on paper, but quite hard to explain. I'll leave it as an exercise for the reader. There are also some minor details about proving the claim for initial small values of n and k, and also showing that _n+1C_n+1 is odd. Both of those are trivial claims, so I won't show it here.

[Guest]

Thanks for sharing these little gems with us, superprimastic. I enjoy the journey greatly, and feel enriched by the experience. Also, thanks for you recommendation. I picked up the Stanford Mathematics Problem Book for my ereader, and look forward to spending some time on it.

Background:

Some notations and general thoughts before we start the proof.

Let P( n, k ) be a binary test for a property defined as follows

P(n, k) = [ (n AND k) == k ]

In other words, P(n, k) returns TRUE if the binary representation of n contains a 1 in every position where the binary representation of k contains a 1, and FALSE otherwise. Using superprimastic's example, if n were 84, 1010100 in binary, then the only values of k which would make P( n, k) = TRUE is 0,4,16,20,64,68,80 and 84 (binary 0000000, 0000100, 0010000, 0010100, 1000000, 1000100, 1010000, and 1010100).

Let f₀( m ) be the position of the right-most digit of 0 in the binary expansion of m. Let f₁( m ) be the position of the right-most digit of 1 in the binary expansion of m. We consider the right-most digit of a binary number to be at position 1, and the second digit from the right to be at position 2, and so on. For instance, f₀( 11001_b ) is equal to 2, and f₁( 11001_b ) is equal to 1, where 11001_b is the binary representation of the decimal number 25.

Another general thing is the process of addition and subtracting 1 to a binary number. The general observations are as follows

1) If m is a binary number, then (m-1) can be obtained by flipping all digits of m from position 1 to f₁( m ).

2) If m is a binary number, then (m+1) can be obtained by flipping all digits of m from position 1 to f₀( m ).

Last general thing is an identity for the binomial coefficient, which is

_n+1C_k = _nC_k + _nC_k-1

So, let's get to the proof.

Claim: _nC_k is odd if and only if P(n, k) == TRUE

Outline of proof:

We prove this using induction. We assume that the claim is true for _nC_k, where k <= n. We then prove that the claim is true for _n+1C_k.

Using the binomial identity, the proof then reduces to proving the following two statements

A) If P(n + 1, k ) = TRUE, then exactly one of P(n , k ) and P(n, k - 1 ) will be TRUE. [ in other words, P(n , k ) XOR P(n, k + 1 ) = TRUE ]

B) If P(n + 1, k ) = FALSE, then either

B.1) P(n , k ) = FALSE and P(n, k - 1 ) = FALSE or

B.2) P(n , k ) = TRUE and P(n, k - 1 ) = TRUE.

Part A:

Let's examine statement A,

If P(n + 1, k ) = TRUE, that implies f₁( n+1) <= f₁( k ), and it is easy to show* the following two statements using the process of adding and subtracting 1 from a binary number

a) If P(n + 1, k ) = TRUE and f₁( n+1) = f₁( k ), then P(n , k ) = FALSE and P(n, k - 1 ) = TRUE

b) If P(n + 1, k ) = TRUE and f₁( n+1) < f₁( k ), then P(n , k ) = TRUE and P(n, k - 1 ) = FALSE,

So, given that the claim is true for _nC_k under induction, the above implies that P(n + 1, k ) = TRUE leads to _n+1C_k being odd.

Part B:

Let's examine statement B. Without loss of generality, we only need to show that if P(n + 1, k ) = FALSE and P(n , k ) = TRUE, then P(n , k - 1 ) = TRUE as well. We're only showing 1 direction but it can be extended both direction using the symmetry _nC_k = _nC_{n - k}.

So P(n + 1, k ) = FALSE and P(n , k ) = TRUE implies that f₀( n ) > f₁( k ). Using the process of adding and subtracting 1 from a binary number, it is easy to show* that P(n , k - 1 ) = TRUE as well.

The above implies that if P(n + 1, k ) = FALSE and one of P(n , k ) = TRUE or P(n, k - 1 ) is TRUE, then the other one is TRUE as well. This implies that if P(n + 1, k ) = FALSE, then _nC_k and _nC_k-1 are either both even or both odd, which leads to _n+1C_k being even.

QED.

Note: The parts that say 'it's easy to show*' are indeed easy to work out on paper, but quite hard to explain. I'll leave it as an exercise for the reader. There are also some minor details about proving the claim for initial small values of n and k, and also showing that _n+1C_n+1 is odd. Both of those are trivial claims, so I won't show it here.

Nice Proof... Thoroughly enjoyed it....