Pascal's triangle fact

[loveschak]

Interesting thing I just noticed while looking at Pascal's triangle: The number of twos in the prime factorization of comb(2n,n) (that is, the nth number in the central column of the triangle) is equal to the number of ones in the binary representation of n.

Comments

[madcaptenor]

Proof, because I'm bored:

let f(m) be the number of 2s which occur in the prime factorization of m. Then
f(n!) = floor(n/2) + floor(n/4) + floor(n/8) + ...
and clearly f(comb(2n,n)) = f((2n)!) - 2*f(n!). So
f(comb(2n,n)) = floor(n) + floor(n/2) + floor(n/4) + ...
- 2 ( floor(n/2) + floor(n/4) + floor(n/8) + ...)
and matching the kth term in the first sum with the kth term in the second sum,
f(comb(2n,n)) = (floor(n) - 2 floor(n/2)) + (floor(n/2) - 2 floor(n/4)) + ...
= [n is odd] + [floor(n/2) is odd] + [floor(n/4) is odd] + ...
where [logical statement] is 1 if "logical statement" is true and 0 if it's false. But floor(n/2^k) is odd if and only if the kth digit from the left in the binary expansion of n is 1. So f(comb(2n,n)) is just the sum of the binary digits of n.

[loveschak]

Yes, that's a lovely proof.