The power set of an -set has elements. This isn’t that complicated. However, mimicking some proofs purporting to show P=NP, I can (incorrectly!) show that the power set grows polynomially in . Heck, I could even show that the power set has a constant number of elements.
Proof. It is not hard to see that the number of elements of the power set of an -set satisfies the recurrence . I’d like to claim that grows polynomially in . In the base case . Good so far. Now for the inductive step, suppose that the number of elements of the power set is polynomial for . Then . QED.
Of course there’s a huge problem in that proof, but that hasn’t stopped others from publishing essentially the same thing. For example, see A polynomial-time algorithm for the maximum clique problem. For those looking to find mistakes in purported P versus NP proofs, here’s a treasure trove.