Exercise 4.1.22* (Amazing sequences)

Proof.

(a)

Even if it means replacing $\alpha$ with ${\alpha }^{-1}$ and exchanging the two sequences, we can assume that $\alpha >1$ ( $\alpha =1$ is impossible because $\alpha$ is irrational).

For all $m,n$ in $\mathbb{N}=\{0,1,2,\dots \}$, put

$$u_n=\lfloor n+\mathit{n\alpha }\rfloor ,v_m=\lfloor m+m{\alpha }^{-1}\rfloor .$$

In particular $u_0=v_0=0$.

We prove first that the two sequences ${(u_n)}_{n\in \mathbb{N}},{(v_m)}_{m\in \mathbb{N}}$ are strictly increasing.

$$\begin{array}{llll}\hfill u_{n+1}-u_n& =n+1+\lfloor (n+1)\alpha \rfloor -n-\lfloor \mathit{n\alpha }\rfloor & \hfill & \\ \hfill & =\lfloor (n+1)\alpha \rfloor -\lfloor \mathit{n\alpha }\rfloor +1,& \hfill & \end{array}$$

where $\lfloor \mathit{n\alpha }\rfloor \le \lfloor (n+1)\alpha \rfloor$, thus

$$u_{n+1}-u_n\ge 1.$$

This proves that ${(u_n)}_{n\in {\mathbb{N}}^{\text{∗}}}$ is strictly increasing, and so is ${(v_m)}_{m\in {\mathbb{N}}^{\text{∗}}}$.

(b)

About this last sequence, we can say a little more. As previously, $$\begin{array}{lll}\hfill v_{m+1}-v_m=\lfloor (m+1){\alpha }^{-1}\rfloor -\lfloor m{\alpha }^{-1}\rfloor +1,0<{\alpha }^{-1}<1.& & \hfill \text{(1)}\end{array}$$

Since

$$\begin{array}{lll}\hfill k-1\le m{\alpha }^{-1}<k,\text{ where }k=\lfloor m{\alpha }^{-1}\rfloor +1\in {\mathbb{N}}^{\text{∗}},& & \hfill \text{(2)}\end{array}$$

we obtain

$$k-1<(m+1){\alpha }^{-1}<k+{\alpha }^{-1}<k+1,$$

thus $\lfloor (m+1){\alpha }^{-1}\rfloor =k-1$ or $k$, so

$$v_{m+1}-v_m\in \{1,2\}.$$

When $v_{m+1}-v_m=2$? We prove the following equivalence:

$$\begin{array}{lll}\hfill v_{m+1}-v_m=2⟺\exists <!--\; FUNCTION\; APPLICATION\; -->k\in {\mathbb{N}}^{\text{∗}},m=\lfloor \mathit{k\alpha }\rfloor .& & \hfill \text{(3)}\end{array}$$

By equation (1), if $v_{m+1}-v_m=2$, then $\lfloor (m+1){\alpha }^{-1}\rfloor =\lfloor m{\alpha }^{-1}\rfloor +1=k$, therefore $m{\alpha }^{-1}<k$, so

$$k\le (m+1){\alpha }^{-1}<k+{\alpha }^{-1}.$$

Thus, multiplying by $\alpha$,

$$\mathit{k\alpha }\le m+1<\mathit{k\alpha }+1,$$

or equivalently

$$m<\mathit{k\alpha }\le m+1$$

Since $\alpha$ is irrational, $\mathit{k\alpha }\le m+1$ otherwise $\alpha =(m+1)∕k\in \mathbb{Q}$. Therefore

$$m<\mathit{k\alpha }<m+1.$$

This shows that $m=\lfloor \mathit{k\alpha }\rfloor .$

Conversely, if $m=\lfloor \mathit{k\alpha }\rfloor$ for some $k\in {\mathbb{N}}^{\text{∗}}$, then, using $\alpha \in ℝ\setminus \mathbb{Q}$, we obtain $m<\mathit{k\alpha }<m+1$ , thus $\mathit{k\alpha }<m+1<\mathit{k\alpha }+1$, so $k<(m+1){\alpha }^{-1}<k+{\alpha }^{-1}$. Therefore $\lfloor (m+1){\alpha }^{-1}\rfloor =k$. Moreover $m<\mathit{k\alpha }<m+1$ implies $m{\alpha }^{-1}<k<(m+1){\alpha }^{-1}$, thus $k-1<k-{\alpha }^{-1}<m{\alpha }^{-1}<k$, so $k=1+\lfloor m{\alpha }^{-1}\rfloor$. This proves $\lfloor (m+1){\alpha }^{-1}\rfloor =1+\lfloor m{\alpha }^{-1}\rfloor$. By equation (1),

$$v_{m+1}-v_m=\lfloor (m+1){\alpha }^{-1}\rfloor -\lfloor m{\alpha }^{-1}\rfloor +1=2.$$

The equivalence (3) is proven.

(c)

By (3), we know that $$\begin{array}{lll}\hfill v_{\lfloor \mathit{n\alpha }\rfloor +1}=v_{\lfloor \mathit{n\alpha }\rfloor }+2.& & \hfill \text{(4)}\end{array}$$

Now we show that

$$\begin{array}{lll}\hfill v_{\lfloor \mathit{n\alpha }\rfloor }<u_n<v_{\lfloor \mathit{n\alpha }\rfloor +1}& & \hfill \text{(5)}\end{array}$$

The definitions

$$\begin{array}{llll}\hfill u_n& =\lfloor n+\mathit{n\alpha }\rfloor =n+\lfloor \mathit{n\alpha }\rfloor ,& \hfill & \\ \hfill v_m& =\lfloor m+m{\alpha }^{-1}\rfloor =m+\lfloor m{\alpha }^{-1}\rfloor & \hfill & \end{array}$$

give

$$\begin{array}{llll}\hfill v_{\lfloor \mathit{n\alpha }\rfloor }& =\lfloor \mathit{n\alpha }\rfloor +\lfloor \lfloor \mathit{n\alpha }\rfloor {\alpha }^{-1}\rfloor ,& \hfill & \\ \hfill v_{\lfloor \mathit{n\alpha }\rfloor +1}& =\lfloor \mathit{n\alpha }\rfloor +1+\lfloor (\lfloor \mathit{n\alpha }\rfloor +1){\alpha }^{-1}\rfloor ,& \hfill & \end{array}$$

thus the inequalities (5) are equivalent to

$$\begin{array}{lll}\hfill & \lfloor \mathit{n\alpha }\rfloor +\lfloor \lfloor \mathit{n\alpha }\rfloor {\alpha }^{-1}\rfloor <n+\lfloor \mathit{n\alpha }\rfloor ,& \hfill \text{(6)}\\ \hfill & n+\lfloor \mathit{n\alpha }\rfloor <\lfloor \mathit{n\alpha }\rfloor +1+\lfloor (\lfloor \mathit{n\alpha }\rfloor +1){\alpha }^{-1}\rfloor .& \hfill \text{(7)}\end{array}$$

By definition of the greatest integer function, $\lfloor \mathit{n\alpha }\rfloor \le \mathit{n\alpha }<\lfloor \mathit{n\alpha }\rfloor +1$, and since $\alpha$ is irrational,

Therefore, multiplying by ${\alpha }^{-1}$, we obtain

Since $\lfloor \mathit{n\alpha }\rfloor {\alpha }^{-1}<n$, a fortiori $\lfloor \lfloor \mathit{n\alpha }\rfloor {\alpha }^{-1}\rfloor <n$, so

which is inequality (6).

Since $n<(\lfloor \mathit{n\alpha }\rfloor +1){\alpha }^{-1}$, we have

thus

which is inequality (7). We have proven (5).

From (4) and (5), we deduce

Assume for the sake of contradiction, that $u_n=v_m$ for some indices $m>0,n>0$. By (8), we obtain $v_{\lfloor \mathit{n\alpha }\rfloor }<v_m<v_{\lfloor \mathit{n\alpha }\rfloor +1}$. But the sequence $(v_m)$ is strictly increasing, thus $\lfloor \mathit{n\alpha }\rfloor <m<\lfloor \mathit{n\alpha }\rfloor +1$: this is impossible. This contradiction shows that

(d) Now we prove by finite induction that for any integer $i$,

By (8), this is true for $i=1$.

Suppose now that $u_n+i=v_{\lfloor \mathit{n\alpha }\rfloor +i}$ for some $i<\lfloor (n+1)\alpha \rfloor -\lfloor \mathit{n\alpha }\rfloor$, then

Since the sequence ${(\lfloor \mathit{n\alpha }\rfloor )}_{n\in \mathbb{N}})$ is increasing, this shows that $\lfloor \mathit{n\alpha }\rfloor +i\ne \lfloor \mathit{k\alpha }\rfloor$ for all $k$. Then the equivalence (3) shows that $v_{\lfloor \mathit{n\alpha }\rfloor +i+1}-v_{\lfloor \mathit{n\alpha }\rfloor +i}\ne 2$, so

The induction is done, so $u_n+i=v_{\lfloor \mathit{n\alpha }\rfloor +i}$ is true for any $i\ge 1$ up to $\lfloor (n+1)\alpha \rfloor -\lfloor \mathit{n\alpha }\rfloor$: (9) is proven.

Similarly, $v_{i+1}=v_i+1$ for any $i<\lfloor \alpha \rfloor$, and $v_1=1$, thus $v_i=i$ for all $i\le \lfloor \alpha \rfloor$. (e) Consider now any integer $k\in ]]u_n,u_{n+1}[[$, for some $n\ge 0$. Then $k=u_n+i$ where by part (a), $1\le i<u_{n+1}-u_n=\lfloor (n+1)\alpha \rfloor -\lfloor \mathit{n\alpha }\rfloor +1$, so

Then by (9), $k=u_n+i=v_{\lfloor \mathit{n\alpha }\rfloor +i}$ is a term of the sequence ${(v_m)}_{m\in {\mathbb{N}}^{\text{∗}}}$. Moreover $u_{n+1}$ is a term of the sequence ${(u_n)}_{n\in {\mathbb{N}}^{\text{∗}}}$, so every $k\in ]]u_n,u_{n+1}]]$ is a term of one of these two sequences.

Since ${\mathbb{N}}^{\text{∗}}=\underset{n\in \mathbb{N}}{\bigcup <!--\; FUNCTION\; APPLICATION\; -->}]]u_n,u_{n+1}]]$, every $k$ in ${\mathbb{N}}^{\text{∗}}$ is a term of one of the two sequences. Moreover, by part (a), all the terms $u_n$ are distinct, all the terms $v_m$ are distinct, and by part (c), all $u_n$ are distinct of every $v_m$ ( $n>0,m>0$). Therefore $k$ is a term of one of the two sequences in only one way.

The two sequences

together contain every positive integer exactly once. (f) Suppose now that $\alpha =p∕q$ is a rational number, where $p,q$ are in ${\mathbb{N}}^{\text{∗}}$. Then

Then

thus the previous result becomes false. □