It looks good to me. What you've proven is that it must be less than or equal to this bound. Is there an element that attains this bound?
So, I have been working on a problem for a while. I am trying to see what sort of maximum and minimum values it can attain. I have for a while conjectured that it attains a maximum value of . I want to see if my proof follows. If anyone is willing to take a look, I would be most appreciative.
Define (Note: the 's are all positive integers, but for not all positive integers produce elements of , so it doesn't span all positive integers).
Claim: where the denominator is an element of .
Proof by induction on .
For , this is simply . Since , it must be that , so . Assume the claim is true for all sets up to . Then, if
, then
We can apply the induction hypothesis to the first term, and for the second term, we know that the bottom is an element of with a minimum value of (since every element of is an element of . And the top is then . So, evaluating this, we get:
. Eliminating the logs from both sides (2 to the power of each side) yields the inequality desired, and hence by induction, proves the claim.
Is this proof correct? Am I overlooking something?
Yes, it turns out that the minimum element is always in the set. So, for all , . And it is simple to check that when .
Edit:
I forgot to mention that the minimum element always attains the maximum bound for that ratio since:
Let be the set of odd positive integers. Define by where is the largest power of 2 that divides . The function is sometimes called the Syracuse function, and is one of the methods used to investigate the 3n+1 Conjecture (also known as the Syracuse problem, the Collatz Conjecture, etc.).
Let . Notice that . Now, if we want to check the asymptotic density of in , we need to figure out how many elements of are less than for some . So, we have:
I now know that the second term on the left is bounded below by 0 and bounded above by .