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

Which is bigger, 64! or 2⁶⁴? 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: 2⁶⁴ 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 2⁶⁴? As it turns out, almost.

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

64! has a factor of 2⁶³; 16! has a factor of 2¹⁵; 512! has a factor of 2⁵¹¹. 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 2^p-1. (p = 2^k, 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 2^k gives a sequence of nonnegative powers of two from 2^k-1 down to 1. If we sum that sequence of powers of two — 2⁰ + 2¹ + 2² + … + 2^k-1 — we get 2^k – 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! > 2^p For p ≥ 4

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