|
Question:
Counting 1's if n = 3 then its binary expansion is 11. Also
6!/(3!3!) = 20 = (2^2)*5.
if n = 7 then its binary expansion is 111. Also 14!/(7!7!) = (2^3)*429.
if n = 8 then its binary expansion is 100. Also 16!/(8!8!) = (2^1)*6435.
Is it a mere coincidence that the number of 1's in binary expansion of a
positive integer n is equal to the largest integer x such that 2^x divides into
the binomial coefficient (2n)Cn = (2n)!/(n!n!)? Prove your result.
Answer:
No, it is not a coincidence. Since 2 is prime, the number of
factors of
2 in n! for some positive integer n is:
floor(n/2) + floor(n/4) + floor(n/8) + ...
Thus, the number of factors of 2 in C(2n, n) = (2n)! / [n!*n!] is:
[ floor(2n/2) + floor(n/2) + floor(n/4) + ...] - 2*[ floor(n/2) +
floor(n/4) + floor(n/8) + ... ]
= n - [ floor(n/2) + floor(n/4) + floor(n/8) + ... ]
(since floor(2n/2) = floor(n) = n)
Let f(n) = n - [ floor(n/2) + floor(n/4) + floor(n/8) + ... ]. So, we
want to show that:
f(n) = the number of 1's in the binary expansion of n (*)
for all positive integers n.
We will now prove the following two propositions:
i) If (*) holds for n, then it holds for 2n.
ii) If (*) holds 2n, then it holds for 2n + 1.
Proof of i): Since doubling n simply corresponds to adding a 0 after
n's binary expression, the number of 1's in the binary expression will
be the same for both n and 2n. So we want to show that f(2n) = f(n). We
have:
f(2n) = 2n - [ floor(n) + floor(n/2) + floor(n/4) + ... ]
= 2n - [ n + floor(n/2) + floor(n/4) + ... ]
= n - [ floor(n/2) + floor(n/4) + floor(n/8) + ... ] = f(n). //
Proof of ii): Note that 2n has 0 as the last digit in its binary
expansion, so that 2n+1 would simply change that last digit to a 1, so
the number 1's in 2n + 1 is just 1 more than the number of 1's of 2n. So
we want to show that f(2n+1) = 1 + f(2n). We have:
f(2n+1) = 2n + 1 + [ floor( (2n+1)/2 ) + floor( (2n+1)/4 ) + floor(
(2n+1)/8 ) + ... ]
= 1 + 2n + [ floor( n + 1/2 ) + floor( n/2 + 1/4 ) + floor( n/4 + 1/8 )
+ ... ]
= 1 + 2n + [ floor(n) + floor(n/2) + floor(n/4) + ... ]
= 1 + f(2n). //
Note that (*) holds for n = 1. So by the above propositions, it also
holds for n = 2 and n = 3. And since it holds for n = 2, it also holds
for n = 4 and n = 5. And since it holds for n = 3, it also holds for n
= 6 and n = 7. Continuing in this manner, we see that (*) holds for all
positive integers n, as desired. QED -- Michael Viscardi
|
