Home » Blog » Deduce and prove a formula for [nx]

Deduce and prove a formula for [nx]

by RoRi

Use the previous exercise (1.11, #4 parts (d) and (e)) to deduce a formula for [nx] and prove this formula is correct.

Claim:

    \[ [nx] = \sum_{k=0}^{n-1} \left[ x + \frac{k}{n} \right]. \]

Proof. Let [x] = m, then we have

    \[ m \leq x < m+1 \quad \implies \quad nm \leq nx < nm+n. \]

Thus, there exists some j \in \mathbb{Z} with 0 \leq j < n such that

    \[ nm +j \leq nx < nm+j+1. \]

Hence, [nx] = nm+j. Thus,

    \[ m+\frac{j}{n} \leq x < m + \frac{j+1}{n}. \]

Then, for each k \in \mathbb{Z} with 0 \leq k < n-j we have

    \begin{alignat*}{2} &m+\frac{j+k}{n} \leq x + \frac{k}{n} < m+\frac{j+k+1}{n} & \qquad \qquad & (\text{adding } \frac{k}{n}) \\ \implies \quad & m \leq x + \frac{k}{n} < m+1 & & (\frac{j+k}{n} < 1 \text{ since } k < n-j) \\ \implies \quad &\left[ x + \frac{k}{n} \right] = m = [x] && \text{for } 0 \leq k < n-j. \end{alignat*} \end{align*}

Then, for n-j \leq k < n, we have

    \begin{alignat*}{3} &m+\frac{j+k}{n} \leq x + \frac{k}{n} < m + \frac{j+k+1}{n} \\ \implies \quad & m+1 \leq x + \frac{k}{n} < m+2 & \qquad \qquad & (\frac{j+k}{n} \geq 1 \text{ since } n-j \leq k) \\ \implies \quad & \left[ x + \frac{k}{n} \right] = m+1 = [x] + 1 && \text{for } n-j \leq k < n. \end{alignat*}\end{align*}

So,

    \begin{align*} \sum_{k=0}^{n-1} \left[ x+ \frac{k}{n} \right] &= \sum_{k=0}^{n-j-1} \left[ x + \frac{k}{n} \right] + \sum_{k=n-j}^{n-1} \left[ x + \frac{k}{n} \right] \\ &= (n-j)[x] + j([x] + 1) \\ &= n[x] + j \\ &= nm+j \\ &= [nx]. \qquad \blacksquare \end{align*}

5 comments

  2. Jon Hurst says:

    Claim:

        \[ [nx] = \sum_{k=0}^{n-1}\left[ x+\frac{k}{n}\right] \]

    Proof:

    (1)   \begin{equation*} \left[x + \frac{k}{n}\right]= \begin{cases} [x] &\quad \mathrm{if}\> x x\geq [x] + \frac{n-k}{n}\\ \end{cases} \quad ;k\in\mathbb{Z},0\leq k\leq\> x \> [x]+\frac{j+1}{n}\quad ;j\in\mathbb{Z}, 0\leq j<n \end{equation*}

    This allows us to derive a closed form of the summation:

    (2)   \begin{equation*} \sum_{k=0}^{n-1}\left[ x+\frac{k}{n}\right] = \sum_{k=0}^{n-j-1}\left[ x+\frac{k}{n}\right] + \sum_{k=n-j}^{n-1}\left[ x+\frac{k}{n}\right] \end{equation*}

    For the first term on the RHS of \eqref{e:3}

        \[ k\leq n-j-1 \Rightarrow [x] + \frac{j+1}{n}\leq [x]+\frac{n-k}{n} \]

    Applying \eqref{e:2} we get

    (3)   \begin{equation*} x\leq\> nx \> n[x]+j+1\quad \Rightarrow\quad [nx]=n[x] + j \end{equation*}

    Thus, for condition \eqref{e:2}

        \[ \sum_{k=0}^{n-1}\left[ x+\frac{k}{n}\right] = [nx] \]

    and since j is not involved in the formula, it is true \forall x.

  3. droptop says:

    Thanks for the work your doing here. But I’ve not been able to figure out the introduction of j into into the proof, even after reading the explanation you gave in the comment section.Please can you like explain again how your going about your proof, like how you know where your headed….

    • RoRi says:

      Hi, no problem, comment away! (Though if I get busy, responses could start to lag.)
      We have

          \[ nm \leq nx \leq nm+n. \]

      But we know for any number nx that it is between k and k+1 for exactly one integer k. But since nm \leq nx we know that integer k is somewhere between nm and nx, which means it is nm+j for some integer j. So, then we have that nx is between nm+j and nm+j+1. Does that make sense? Basically, we are just saying that we know k \leq nx \leq k+1 for some integer k, but then it is more convenient to write it as nm+j \leq nx \leq nm+j+1 since that will help us out later.

      Not sure if this actually clears up your question. Let me know if not.

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):