I have a function f(n) defined over the set of natural numbers, where each input n corresponds to a unique output f(n), ensuring that the function's values are distinct. I am trying to prove that the set of outputs of this function must contain a power of 2 somewhere.
Intuitively, it seems plausible, as the set of natural numbers is infinite, and if each output is unique, there should be a point where the number of distinct outputs reaches a power of 2. However, I am struggling to formalize this proof.
I've considered strategies involving pigeonhole principle or possibly using properties of powers of 2, but haven't made significant progress. Could someone provide insights or a proof sketch to help me tackle this problem? Any assistance or hints would be greatly appreciated!