I need to show that the sequence $\frac{0}{1}, \frac{0}{2}, \frac{1}{2}, \frac{0}{3}, \frac{1}{3}, \frac{2}{3}, \dots , \frac{0}{k}, \frac{1}{k}, \dots , \frac{k-1}{k}$ is equidistributed in the interval $[0,1]$ (and so equidistributed mod $1$).

Ah, of course I can't use any further theorem developped in the theory of equidistibution of sequences like, for example, Weyl 's criterion. I must deduce it from the definition.

This is taken from Kuipers and Niederreiter, exercize 1.13. I found this old question but as you can see noone answered it. Thank you in advance


Let $(x_n)_{n \geq 0}$ be this sequence. We want to show that, for any function $f \in \mathcal{C} ([0,1], \mathbb{R})$,

$$\lim_{n \to + \infty} \frac{1}{n} \sum_{k=0}^{n-1} f(x_k) = \int_0^1 f(t) \ \text{d}t.$$

The sequence is a concatenation of finite subsequence $(k/n)_{0 \leq k < n}$. We shall proceed in three steps: first by proving convergence for these subsequences, the for the initial sequence $(x_n)_{n \geq 0}$ along a nice subsequence, and then the equidistribution.

Let $f \in \mathcal{C} ([0,1], \mathbb{R})$.

First step

We have

$$\lim_{n \to + \infty} \frac{1}{n} \sum_{k=0}^{n-1} f(k/n) = \int_0^1 f(t) \ \text{d}t,$$

since the left ahnd-side is a Riemann sum for $f$. We write $u_n$ for the $n$th Riemann sum $\frac{1}{n} \sum_{k=0}^{n-1} f(k/n)$.

Second step

Let $N \geq 0$, and set $n(N) := \frac{N(N+1)}{2}$. Then

$$\frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \frac{2}{N(N+1)} \sum_{\ell = 1}^N \sum_{k=0}^{\ell-1} f(k/\ell) = \sum_{\ell = 1}^N \frac{2\ell}{N(N+1)} u_\ell.$$

Set $v_\ell^{(N)} := \frac{2\ell}{N(N+1)}$ for $\ell \leq N$, and $0$ for $\ell \geq N+1$. Then

$$\frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \sum_{\ell = 1}^{+ \infty} v_\ell^{(N)} u_\ell.$$

In addition :

  • $\sum_{\ell=1}^{+\infty} v_\ell^{(N)} = 1$ for all $N$,

  • $\lim_{M \to + \infty} \sum_{\ell=1}^{M} v_\ell^{(N)} = 0$,

  • $\lim_{\ell \to + \infty} u_\ell = \int_0^1 f(t) \ \text{d}t$.

Hence, by a lemma I'll leave aside (but can be proved with some $\epsilon$-$\delta$ arguments),

$$\lim_{N \to + \infty} \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) = \lim_{N \to + \infty} \sum_{\ell = 1}^{+ \infty} v_\ell^{(N)} u_\ell = \int_0^1 f(t) \ \text{d}t.$$

Third step

Let $n \geq 0$. Let $N$ be the largest integer such that $\frac{N(N+1)}{2} \leq n$. Then $n-n(N) \leq n(N+1)-n(N) = N+1 \leq \sqrt{2(n+1)}$, so that

$$\frac{1}{n} \sum_{k=0}^{n-1} f(x_k) = \frac{n(N)}{n} \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) + \frac{1}{n} \sum_{k=n(N)}^{n-1} f(x_k) = (1+o(1)) \frac{1}{n(N)} \sum_{k=0}^{n(N)-1} f(x_k) + O\left(\frac{\|f\|_{\infty}}{\sqrt{n}} \right),$$

and thus the full sequence also converges to the integral of $f$.


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.