Showing n! > 2n When n Is A Power of Two

Which is bigger, 64! or 264? 64! is, because it follows from a proof by induction for any integer n greater than or equal to 4. It’s also easy to just reason that 64! is bigger: 264 is 64 factors of 2, whereas 64! has 64 factors, except all but one of them (1) are 2 or greater.

When I saw this problem though I wondered if I could solve it in another way: Could the factors of two alone in 64! be greater than 264? As it turns out, almost.

(2k)! Has a Factor of 22k-1

64! has a factor of 263; 16! has a factor of 215; 512! has a factor of 2511. That’s what Wolfram Alpha told me, after I worked out similar but smaller examples on paper. The pattern was clear: the factorial of any positive power of two p, p!, had a factor of 2p-1. (p = 2k, for any integer k ≥ 1.)

It’s not hard to see why. The factors of 2 come from the even numbers, and from the 64 factors in 64! (1, 2, 3, …, 64) there are 32 even numbers: 2, 4, 6, …, 64. If you pull out a factor of two from each number in that list you get a new list: 1, 2, 3, …, 32. In that list there are 16 even numbers (2, 4, 6, …, 32) from which you can pull out another 16 factors of 2. Repeating this process until the list reduces to no even numbers (a list of just 1), you have a total number of factors of two of 32 + 16 + 8 + 4 + 2 + 1 = 63.

To generalize, we are repeatedly halving a power of two with each new list of even numbers, and repeatedly halving a power of two 2k gives a sequence of nonnegative powers of two from 2k-1 down to 1. If we sum that sequence of powers of two — 20 + 21 + 22 + … + 2k-1 — we get 2k – 1.

(I haven’t thought much about how to do this with an inductive proof, or whether it would be necessary — it certainly isn’t for my purposes. But you’d do it in “reverse”, starting with smaller powers of two and proving the property holds for bigger ones.)

p! > 2p For p ≥ 4

Although there aren’t more than p factors of two in p! like I had wondered, the proof that p! > 2p is still trivial just using the powers of two that are present. For our example, the factors 263 and 3 of 64! make it greater than 264. Because 3 will always be a factor of p! for any p ≥ 4, this result applies generally to show p! > 2p.


Copyright © 2008-2024 Exploring Binary

Privacy policy

Powered by WordPress