21
$\begingroup$

I'm doing some exercises on Apostol's calculus, on the floor function. Now, he doesn't give an explicit definition of $[x]$, so I'm going with this one:

DEFINITION Given $x\in \Bbb R$, the integer part of $x$ is the unique $z\in \Bbb Z$ such that $$z\leq x < z+1$$ and we denote it by $[x]$.

Now he asks to prove some basic things about it, such as: if $n\in \Bbb Z$, then $[x+n]=[x]+n$

So I proved it like this: Let $z=[x+n]$ and $z'=[x]$. Then we have that

$$z\leq x+n<z+1$$

$$z'\leq x<z'+1$$

Then $$z'+n\leq x+n<z'+n+1$$

But since $z'$ is an integer, so is $z'+n$. Since $z$ is unique, it must be that $z'+n=z$.

However, this doesn't seem to get me anywhere to prove that $$\left[ {2x} \right] = \left[ x \right] + \left[ {x + \frac{1}{2}} \right]$$

in and in general that

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

Obviously one could do an informal proof thinking about "the carries", but that's not the idea, let alone how tedious it would be. Maybe there is some easier or clearer characterization of $[x]$ in terms of $x$ to work this out.

Another property is $$[-x]=\begin{cases}-[x]\text{ ; if }x\in \Bbb Z \cr-[x]-1 \text{ ; otherwise}\end{cases}$$

I argue: if $x\in\Bbb Z$, it is clear $[x]=x$. Then $-[x]=-x$, and $-[x]\in \Bbb Z$ so $[-[x]]=-[x]=[-x]$. For the other, I guess one could say:

$$n \leqslant x < n + 1 \Rightarrow - n - 1 < x \leqslant -n$$

and since $x$ is not an integer, this should be the same as $$ - n - 1 \leqslant -x < -n$$

$$ - n - 1 \leqslant -x < (-n-1)+1$$

So $[-x]=-[x]-1$

$\endgroup$
15
$\begingroup$

Let $n=\lfloor x\rfloor$, and let $\alpha=x-n$; clearly either $0\le\alpha<\frac12$, or $\frac12\le\alpha<1$. Then

$$\lfloor 2x\rfloor=\lfloor 2n+2\alpha\rfloor=2n+\lfloor 2\alpha\rfloor=\begin{cases} 2n,&\text{if }0\le\alpha<\frac12\\ 2n+1,&\text{if }\frac12\le\alpha<1\;, \end{cases}$$

and

$$\left\lfloor x+\frac12\right\rfloor=\left\lfloor n+\alpha+\frac12\right\rfloor=n+\left\lfloor\alpha+\frac12\right\rfloor=\begin{cases} n,&\text{if }0\le\alpha<\frac12\\ n+1&\text{if }\frac12\le\alpha<1\;; \end{cases}$$

since $\lfloor x\rfloor=n$, the first result is immediate.

The general case is handled similarly, except that there are $n$ cases; for $k=0,\dots,n-1$, case $k$ is $$\frac kn\le\alpha<\frac{k+1}n\;.$$

$\endgroup$
  • $\begingroup$ M.Scott: By this question, Peter, challenged me and my knowledge about this function, however, I supposed I know this function properly. You opened my eyes to the additional facts I didn’t consider well. Thanks Brian. Thanks Peter for this question. (+1)+(+1) $\endgroup$ – mrs Aug 19 '12 at 20:17
17
+50
$\begingroup$

This is one of my favourite exercises, because of the following neat solution:

Fix $n$. Let

$$ f(x) := \sum\limits_{k=0}^{n-1} \Biggl[x + \frac{k}{n}\Biggr] - [nx] \,.$$

Then $f(x) =0 \forall x \in [0,\frac{1}{n})$ since all terms are zero, and it is easy to prove that $f(x+\frac{1}{n})=f(x)$.

It follows imediately that $f$ is identically 0.

$\endgroup$
  • $\begingroup$ You're right, that is a very nice solution. $\endgroup$ – robjohn Oct 20 '12 at 23:19
  • $\begingroup$ Why does it follow that $f\equiv 0$? $\endgroup$ – YoTengoUnLCD Aug 20 '16 at 3:25
  • 1
    $\begingroup$ @YoTengoUnLCD If $x$ is arbitrary, you can write $x=\frac{k}{n}+y$ with $y \in [0,\frac{1}{n})$. Since $f(y)=0$ you get that $f(y+\frac{k}{n})=0$. $\endgroup$ – N. S. Aug 20 '16 at 4:48
9
$\begingroup$

Both sides are equal since they count the same set: the RHS counts naturals $\rm\:\le n\:x\:$. The LHS counts them in a unique mod $\rm\ n\ $ representation, $\:$ viz. $\rm\ \: j \:\le\: x+k/n\: \iff \ j\:n-k \:\le\: n\:x\:,\ \ j>0 \le k < n\:$.

REMARK $\:$ That every natural has a unique representation of form $\rm \: j\:n-k \ \ \:$ where $\rm\ \ \: j>0 \le k < n\ \ \ $ is simply a slight variant of the Division Algorithm where one utilizes negative (vs. positive) remainders.$\ \ $ To derive this negative form, simply perform the following transformation on the positive remainder form $\rm\ q\: n + r\ \to\ (q+1)\:n + r-n\ $ if $\rm\ r\ne 0\:$, i.e. inc the quotient, dec the remainder by the dividend.

Thus the result is equivalent to the Division Algorithm, whose normal proof is indeed by induction. One could give a direct inductive proof of the result if, instead of invoking the Division Algorithm by name, one unwinds or inlines this inductive proof directly into the proof of the result - much as the same way that the classic Lindenmann - Zermelo direct proof of unique factorization of naturals inlines a division / Euclidean algorithm based descent proof of the fundamental Prime Divisor property $\rm\ p|ab\ \Rightarrow\ p|a\ \ or\ \ p|b\:$.

$\endgroup$
4
$\begingroup$

It is enough to prove it for $0 < x < 1$.

Now, let $M$ be an integer such that, $\frac{M}{n} \le x < \frac{M+1}{n}$ where $0 \le M < n$

Thus $[nx] = M$.

For $0 \le k \le n-M-1$, we have that $[x+\frac{k}{n}] = 0$.

For $n-1 \ge k > n-M-1$ we have that $[x + \frac{k}{n}] = 1$.

The result follows.

I don't think induction can be used here.

$\endgroup$
4
$\begingroup$

Hint: Set $\{ x \} = x - [x]$. To prove $[nx] = \displaystyle\sum_{k = 0}^{n - 1} [x + \frac{k}{n}]$, consider the cases $\frac{k - 1}{n} \leq \{ x\} < \frac{k}{n}$ for $k = 1,2,\ldots,n$ separately.

The idea is that we want to see when exactly $[x + \frac{k}{n}] = [x] + 1$ starts to hold as $k$ grows.

$\endgroup$
  • 1
    $\begingroup$ Although one need not phrase this in terms of «cases»: given $x$, there exists exactly one $k\in\{1,\dots,n\}$ such that $(k-1)/n\leq\{x\}<k/n$. Now work with this $k$. $\endgroup$ – Mariano Suárez-Álvarez Aug 19 '12 at 18:57
2
$\begingroup$

The trick for the inductive proof is that you want to do induction on $x$, not $n$, and you want to take steps of size $\frac{1}{n}$, not steps of size $1$.

For the base case, observe that it's true for $x \in [0, \frac{1}{n})$, since all of the terms are zero.

Then for the inductive step, you can see that substituting $x \to x + \frac{1}{n}$ will increase exactly one term on the left hand side by $1$, and has the same effect on the right hand side. Alternatively, you can calculate

$$\begin{align} \sum_{k=0}^{n-1} \left\lfloor \left(x + \frac{1}{n}\right) + \frac{k}{n} \right\rfloor &= \sum_{k=0}^{n-1} \left\lfloor x + \frac{k+1}{n} \right\rfloor \\&= \left( \sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor \right) + \left\lfloor x + \frac{n}{n} \right\rfloor - \left\lfloor x + \frac{0}{n} \right\rfloor \\&= \lfloor nx \rfloor + 1 \\&= \left\lfloor n \left( x + \frac{1}{n} \right) \right\rfloor \end{align}$$

Consequently, if the theorem holds for $x = t$, then it also holds for $x = t + \frac{1}{n}$. Similarly, it holds for $x = t - \frac{1}{n}$. We thus conclude it holds for all real $x$.

To phrase this as an "ordinary" induction problem, the statement to be proved is:

For every integer $k$, the equation holds for $x \in [\frac{k}{n}, \frac{k+1}{n})$.

The base case is $k=0$. One inductive argument then proves the theorem for positive $k$, and another proves it for negative $k$.

$\endgroup$
  • $\begingroup$ This is exactly the same approach as in Matsuoka, Yoshio (1964), "Classroom Notes: On a Proof of Hermite's Identity", The American Mathematical Monthly 71 (10): 1115 (doi: 10.2307/2311413), which I found through Wikipedia and used in this answer of mine. $\endgroup$ – Marnix Klooster Aug 27 '16 at 22:23
0
$\begingroup$

Here is a complete answer to the second question:

If $n$ is a positive integer then $\lfloor nx \rfloor = \sum_{k=0}^{n-1} \lfloor x+\frac{k}{n} \rfloor$.

Let $m = \lfloor x \rfloor$ and $d = x - m$, so $0 \le d < 1$.

Let $j =\lfloor nd \rfloor $, so $0 \le j \le n-1 $ and $\frac{j}{n} \le d < \frac{j+1}{n} $. If $0 \le k \le n-j-1$,

$\begin{array}\\ m &\le m+d+\frac{k}{n}\\ &< m+\frac{n-j}{n}+\frac{j}{n}\\ &= m+\frac{n}{n}\\ &= m+1\\ \end{array} $

so $\lfloor m+d+\frac{k}{n} \rfloor =m $.

If $n-j \le k \le n-1$,

$\begin{array}\\ m+d+\frac{k}{n} &\ge m+\frac{n-j}{n}+\frac{j}{n}\\ &= m+\frac{n}{n}\\ &= m+1\\ \end{array} $

and

$\begin{array}\\ m+d+\frac{k}{n} &\lt m+\frac{n-j+1}{n}+\frac{n-1}{n}\\ &= m+\frac{2n-j}{n}\\ &= m+2-\frac{j}{n}\\ \end{array} $

so $\lfloor m+d+\frac{k}{n} \rfloor =m+1 $.

Therefore

$\begin{array}\\ \sum_{k=0}^{n-1} \lfloor x+\frac{k}{n} \rfloor &=\sum_{k=0}^{n-1} \lfloor m+d+\frac{k}{n} \rfloor\\ &= \sum_{k=0}^{n-j-1} \lfloor m+d+\frac{k}{n} \rfloor +\sum_{k=n-j}^{n-1} \lfloor m+d+\frac{k}{n} \rfloor\\ &= (n-j)m+j(m+1)\\ &= nm+j\\ \end{array} $

and $\lfloor nx \rfloor =\lfloor n(m+d) \rfloor =nm+\lfloor nd \rfloor =nm+j $.

We are done.

$\endgroup$

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.