Hey I started working on the following problem:

For any real number $x$ let $\lfloor x \rfloor$,denote the greatest integer, which is less than or equal to $x$. Define $q(n) = \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \rfloor $ for $n = 1,2,3,...$. Determine all positive integers $n$ for which $q(n)>q(n+1)$.

My attempt:

So I realised that $q(n)$ 'jumps' whenever $n$ moves from a number just below a perfect square to the next perfect square.

This gave me the idea to focus on values of $n$, between $m^2$ and $(m+1)^2$, in order to find out more about the function.

From $m^2 \le n < (m+1)^2$, we can deduce that $\lfloor \sqrt{n} \rfloor = m$. However now I am stuck on how to continue with $q(n) = \lfloor \frac{n}{m} \rfloor$.

It seems to me that the function is increasing, but if yes then wouldn't there be no values for $n$ at all?

Can anyone help me on how to continue please?


You are correct that the function is increasing in the interval $[m^2,(m+1)^2-1]$, so there are no values of $n$ in any interval $[m^2,(m+1)^2-1)$ which satisfies $q(n)>q(n+1)$, for any $m$. This means you only need to check $n=(m+1)^2-1$, for any $m$, because this is where $\lfloor\sqrt{n}\rfloor$ "jumps" when you move from $n$ to $n+1$.

For $n=(m+1)^2-1$, you have $q(n)=\lfloor\frac{m^2+2m}{m}\rfloor$ and $q(n+1)=\lfloor\frac{m^2+2m+1}{m+1}\rfloor$. Can you compare the two?

  • $\begingroup$ Where does the $(m+1)^2 - 1$ come from? $\endgroup$ – ar0bx Aug 24 '16 at 8:44
  • $\begingroup$ For $n=m^2,m^2+1,\dots,(m+1)^2-2$, we already have $q(n)\leq q(n+1)$, by the argument that you wrote. $\endgroup$ – pi66 Aug 24 '16 at 8:45
  • $\begingroup$ Maybe an example would help. Consider $m=2$, so the interval $[4,8]$. For $n=4,5,6,7$, we already know that $q(n)\leq q(n+1)$. So we only need to check $n=8$, i.e., whether $q(8)>q(9)$ or not. $\endgroup$ – pi66 Aug 24 '16 at 8:48
  • $\begingroup$ Well $q(n) = \lfloor \frac{m^2 + 2m}{m} \rfloor = m+2$ and $q(n+1) = \lfloor \frac{(m+1)(m+1)}{(m+1)} \rfloor = m+1$ $\endgroup$ – ar0bx Aug 24 '16 at 8:53
  • $\begingroup$ Right, exactly! $\endgroup$ – pi66 Aug 24 '16 at 8:54

The function $q(n)$ is piecewise increasing (but not strictly) in every interval $[m^2, {(m + 1)}^2 - 1]$, since if $a, b$ are in that interval (with $a < b$), then $$\left\lfloor\frac a m \right\rfloor = q(a) \leq q(b) = \left\lfloor \frac b m \right\rfloor.$$

Therefore we only need to check where all those intervals "join", and that happens between a perfect square and the preceding number. Indeed we have $q(n) > q(n + 1)$ in this case: $$q(m^2) = \left\lfloor\frac{m^2}m\right\rfloor = m$$ while $$q(m^2 - 1) = \left\lfloor\frac{m^2 - 1}{m - 1}\right\rfloor = m + 1$$

We conclude that the only values of $n$ for which $q(n) > q(n + 1)$ are $$\{m^2 - 1 \mid m \in \mathbb N\} = \{3, 8, 24, \ldots\}$$

I find that plotting the sequence really helps in visualizing the proof: enter image description here

  • $\begingroup$ Can you tell me please what have you plot ? $\endgroup$ – chaviaras michalis Aug 24 '16 at 9:34
  • $\begingroup$ @chaviarasmichalis I plotted $q(n)$ with $n$ from $1$ to $40$. The red points are the values of the sequence. $\endgroup$ – rubik Aug 24 '16 at 10:40
  • $\begingroup$ I see ... and how you calculate \begin{equation} q(m^2 +1 )=\floor{\frac{m^2 -1 }{\floor{\sqrt(m^2 -1) } } } \end{equation} at the formula which you wrote ? $\endgroup$ – chaviaras michalis Aug 24 '16 at 18:56
  • $\begingroup$ @chaviarasmichalis Assuming you mean $q(m^2 - 1)$, we have: $$q(m^2 - 1) = \left\lfloor\frac{m^2 - 1}{\lfloor\sqrt{m^2 - 1}\rfloor}\right\rfloor = \left\lfloor\frac{m^2 - 1}{m - 1}\right\rfloor = \left\lfloor\frac{(m + 1)(m - 1)}{m - 1}\right\rfloor = m + 1$$ $\endgroup$ – rubik Aug 24 '16 at 20:16
  • $\begingroup$ Yeah that's what i meant . So can you explain how you figure out that $\lfloor \sqrt{m^2 -1} \rfloor = m-1$ $\endgroup$ – chaviaras michalis Aug 25 '16 at 19:00

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.