Let $A$ be a non-empty subset of $\mathbb{N}$, such that for all $k \in \mathbb{N}$, we have $2^k\in A$. Also, if $x \in A$ then we have $\lfloor \sqrt{x} \rfloor \in A$. Is it true that $A=\mathbb{N}$?

I have tried but am not able to do anything. Taking $n \notin A$ and trying to achieve a contradiction didn't work for me. So how do we solve this, preferably by a pre-calculus approach? Additionally, is it also true for powers of $n$ other than $2$?


Let's take one number $n$ which is not a power of $2$ and assume it is not in $A$.

If $n$ is not in $A$ then any number between $n^2$ and $(n+1)^2-1$ must be missing, because if one of these numbers is in $A$ then $n$ is in $A$, because the floor of the square root of all of them is equal to $n$.

Now, we can consider two steps. It is easy to see that all the numbers from $n^4$ to $(n+1)^4-1$ should be missing, otherwise in two steps we reach $n$.

Proceeding in this way we can see that all the numbers from $n^\alpha$ to $(n+1)^\alpha-1$ must be missing, where $\alpha$ is a power of 2.

Now, the ratio $\frac{n+1}{n}$ is larger than $1$, so there will be a value $\alpha$ such that $(n+1)^\alpha > 2\cdot n^\alpha$, i.e., that the range of forbidden numbers contains at least one number $m=n^\alpha$ and twice that number $2m=2n^\alpha$.

But it is easy to see that between a number $m$ which is not a power of two and its double $2m$ there is always a power of 2.

But this would imply that that power of 2 is forbidden, but this is a contradiction because all the powers of 2 are in $A$.

EDIT. The argument should work also if we know that $3^k\in A$ (or other powers with a fixed base). Indeed the ratio between $n^\alpha$ and $(n+1)^\alpha$ can always become large enough to be sure that a power of the base is inside the interval.

| cite | improve this answer | |

It's sufficient to show $$\forall n\in \mathbb N\quad \exists k,m\in \mathbb N \quad \text{s.t} \quad n^{2^k}<2^m<(n+1)^{2^k}$$
and it's equal to say $$\forall n\in \mathbb N\quad \exists k,m\in \mathbb N \quad \text{s.t} \quad 2^k \log_2{n}<m<2^k \log_2{(n+1)}$$

And it's true, because if $\log_2{(n+1)}-\log_2{n}=\varepsilon $ then put $k$ so large such that $2^k\varepsilon>1$.

Remark : This method also works for any number $1<x$ other than $2$.
If $\log_x{(n+1)}-\log_x{n}=\varepsilon $ then there is a $k$ s.t $x^k\varepsilon>1$

| cite | improve this answer | |
  • $\begingroup$ Indeed. It would be interesting to see how much effort is needed to turn this into a pre-calculus proof. First thing, one can compute effectively a "large enough" $k$ in terms of $m$ $\endgroup$ – Ewan Delanoy Apr 1 '16 at 11:35
  • $\begingroup$ @EwanDelanoy "large enough" $k$ in terms of $n$, not $m$. $\endgroup$ – user217174 Apr 1 '16 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.