Compute $\lim\limits_{n \to \infty} n\sum\limits_{k=1}^n(f(k/n) - f((k-1)/n))\int_{(k-1)/n}^{k/n}f(t)dt$

Question

Let $f : [0,1] \to \mathbb{R}$ be a continuous function and let $(a_n)_{n>0}$ and $(b_n)_{n>0}$ be two sequences such that $$\displaystyle{ a_n = \sum_{k=1}^n{f \left(\frac{k-1}{n}\right) \cdot \int_\frac{k-1}{n}^\frac{k}{n}}{f(t)dt}},$$

$$\displaystyle b_n = \sum_{k=1}^n{f \left(\frac{k}{n}\right) \cdot \int_\frac{k-1}{n}^\frac{k}{n}}{f(t)dt}, $$ $\forall n \in \mathbb{N}^*$.

a) Prove that $\displaystyle{\lim_{n \to \infty}{(b_n - a_n)} = 0}$.

b) Compute $\displaystyle{\lim_{n \to \infty}{n(b_n - a_n)}}$.

I have managed to solve a).

Proof for a) :

From the mean value theorem, we know that $\displaystyle{\exists c_k \in \left(\frac{k-1}{n}, \frac{k}{n}\right)}$ such that $\displaystyle{\int_{\frac{k-1}{n}}^{\frac{k}{n}}{f(t)dt} = \frac{1}{n}f(c_k)}$

So, $b_n = \displaystyle{\frac{1}{n}\sum_{k=1}^n {f(c_k) \cdot f\left(\frac{k}{n}\right)} = \frac{1}{2} \cdot \frac{1}{n}\sum_{k=1}^n{\left(\frac{f(c_k) + f\left(\frac{k}{n}\right)}{2}\right)^2 \cdot 4 - (f(c_k))^2 - \left(f\left(\frac{k}{n}\right)\right)^2}}$.

Since $f$ has the intermediate value property, then $\exists x_k \in \displaystyle{\left(c_k, \frac{k}{n}\right) \subset \left(\frac{k-1}{n}, \frac{k}{n} \right)}$ such that $\displaystyle{\frac{f(c_k) + f\left(\frac{k}{n}\right)}{2} = f(x_k)}$.

Therefore, $\displaystyle{\lim_{n \to \infty}b_n = \int_0^1{(f(t))^2dt}}$.

Using the same method, $\displaystyle{\lim_{n \to \infty}a_n = \int_0^1{(f(t))^2dt}}$, so $\displaystyle{\lim_{n \to \infty}{(b_n - a_n)} = 0}$.

I have trouble solving b). I tried using the same method but it doesn't work, not unless $f$ is differentiable (so I can use Lagrange's theorem).

$\displaystyle{n(b_n - a_n) = \sum_{k=1}^n{f(c_k) \left( f\left(\frac{k}{n}\right) - f\left(\frac{k-1}{n} \right) \right)}}$ and if $f$ is differentiable, then $\displaystyle{f\left(\frac{k}{n}\right) - f\left(\frac{k-1}{n} \right) = \frac{1}{n}f'(c_k)}$.

Answer 1

Here we construct a continuous function $f : [0, 1] \to [0, 1]$ such that the associated sequences $(a_n)$ and $(b_n)$ satisfy

$$ \lim_{n\to\infty} 3^n(b_{3^n} - a_{3^n}) = \infty \tag{*}$$

1. Construction

Pick $0 < y_2 < y_1 < 1$ and define $\psi : \mathbb{R} \to [0, 1]$ by

$$ \forall x \in [0, 3) \ : \quad \psi(x) = \begin{cases} 3y_1, & x \in [0, 1) \\ 3(y_2 - y_1), & x \in [1, 2) \\ 3(1 - y_2), & x \in [2, 3) \end{cases} $$

and extend by $3$-periodicity, i.e. $\psi(x) = \psi(x \text{ mod } 3)$. Then define $f_n : [0, 1] \to \mathbb{R}$ by

$$ f_n(x) = \int_{0}^{x} \prod_{i=1}^{n} \psi(3^i t) \, dt. $$

We will prove the following claim.

Theorem. $f_n$ converges uniformly to a continuous function $f : [0, 1] \to \mathbb{R}$. Moreover, for all $n \geq 1$ and $k \in \{1,\cdots,3^n\}$, we have $f(\frac{k}{3^n}) = f_n(\frac{k}{3^n})$ and

$$ \int_{\frac{k-1}{3^n}}^{\frac{k}{3^n}} f(x) \, dx = \frac{1}{2\cdot 3^n}\left( f_n(\tfrac{k}{3^n}) + f_n(\tfrac{k-1}{3^n}) \right) + \frac{\alpha}{3^n}\left( f_n(\tfrac{k}{3^n}) - f_n(\tfrac{k-1}{3^n}) \right) $$

where $\alpha = 2\int_{0}^{1} (\psi(3t) - t) \, dt$.

Remark. $f$ is a variant of the Cantor-Lebesgue function, with the construction step modified so that the variation diverges fast.

Assuming this theorem, we find that

\begin{align*} 3^n(b_{3^n} - a_{3^n}) &= 3^n \sum_{k=1}^{3^n} \left( f(\tfrac{k}{3^n}) - f(\tfrac{k-1}{3^n}) \right) \int_{\frac{k-1}{3^n}}^{\frac{k}{3^n}} f(x) \, dx \\ &= \frac{1}{2} \sum_{k=1}^{3^n} \left( f_n(\tfrac{k}{3^n})^2 - f_n(\tfrac{k-1}{3^n})^2 \right) + \alpha \sum_{k=1}^{3^n} \left( f_n(\tfrac{k}{3^n}) - f_n(\tfrac{k-1}{3^n}) \right)^2 \\ &= \frac{1}{2} + \frac{\alpha}{9^n} \sum_{k=1}^{3^n} \prod_{i=1}^{n} \psi(3^i \cdot \tfrac{k-1}{3^n} )^2. \end{align*}

But it is not hard to check that

$$ \sum_{k=1}^{3^n} \prod_{i=1}^{n} \psi(3^i \cdot \tfrac{k-1}{3^n} )^2 = \left( \psi(0)^2 + \psi(1)^2 + \psi(2)^2 \right)^n. $$

So we have

$$ 3^n(b_{3^n} - a_{3^n}) = \frac{1}{2} + \alpha \left( \frac{\psi(0)^2 + \psi(1)^2 + \psi(2)^2}{9} \right)^n. $$

Finally, we can choose $y_1$ and $y_2$ so that $\frac{\psi(0)^2 + \psi(1)^2 + \psi(2)^2}{9} > 1$ and $\alpha > 0$. Therefore the desired claim $\text{(*)}$ follows. ////

2. Proof of Theorem

The following lemma will be useful throughout our proof.

Lemma. For each $m \in \{1, \cdots, 3^n\}$ and $x \in [\frac{m-1}{3^n}, \frac{m}{3^n}]$ we have

\begin{align*} f_{n+1}(x) &= f_n(\tfrac{m-1}{3^n}) + \left( f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) \right) \cdot f_1(3^n x - (m-1)) \\ &= f_n(x) + \left( f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) \right) \cdot \left( f_1(3^n x - (m-1)) - (3^n x - (m-1)) \right) \end{align*}

Indeed, we have

\begin{align*} f_{n+1}(x) - f_{n+1}(\tfrac{m-1}{3^n}) &= \int_{\frac{m-1}{3^n}}^{x} \prod_{i=1}^{n+1} \psi(3^i t) \, dt \\ &= \left( \prod_{i=1}^{n} \psi \left( 3^i \cdot \tfrac{m-1}{3^n} \right) \right) \cdot \left( \int_{\frac{m-1}{3^n}}^{x} \psi(3^{n+1} t) \, dt \right) \\ &= \left( 3^n \left( f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) \right) \right) \cdot \left( \frac{f_1(3^n x - (m-1))}{3^n} \right) \\ &= \left( f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) \right) \cdot f_1(3^n x - (m-1)). \end{align*}

Plugging $x = \frac{m}{3^n}$ and $f_1(1) = 1$ shows that $f_{n+1}(\tfrac{m}{3^n}) - f_{n+1}(\tfrac{m-1}{3^n}) = f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) $. From this we easily deduce that $f_{n+1}(\tfrac{m}{3^n}) = f_{n}(\tfrac{m}{3^n})$ and the first half of Lemma follows. Now by using the fact that the graph of $f_n$ is linear on the interval $[\frac{m}{3^n}, \frac{m+1}{3^n}]$, we have

\begin{align*} f_{n}(x) - f_{n}(\tfrac{m-1}{3^n}) &= \left( f_{n}(\tfrac{m}{3^n}) - f_{n}(\tfrac{m-1}{3^n}) \right) \cdot (3^n x - (m-1)) \end{align*}

and hence the second half of Lemma follows. ////

Proof of Theorem. We fist establish the uniform convergence. Let $r = \frac{1}{3}\sup |\psi|$. By our choice of $y_1$ and $y_2$ we know that $r \in [0, 1)$. Also,

$$ \forall m \in \{1,\cdots,3^n\} \ : \quad \left| f_n(\tfrac{m}{3^n}) - f_n(\tfrac{m-1}{3^n}) \right| = \frac{1}{3^n} \prod_{i=1}^{n} \left| \psi(3^i \cdot \tfrac{m}{3^n}) \right| \leq r^n. $$

Now let $C = \sup_{x \in [0, 1]} |f_1(x) - x|$. Then by Lemma, uniformly in $x \in [0, 1]$ we have

$$ \left| f_{n+1}(x) - f_{n}(x) \right| \leq C r^n. $$

So $(f_n)$ converges uniformly over $[0, 1]$. Let $f : [0, 1] \to \mathbb{R}$ denote the limiting function. Then $f$ is continuous. Also, by the intermediate step of the proof of Lemma, we know that

\begin{align*} f_n(\tfrac{k}{3^n}) &= f_{n+1}(\tfrac{k}{3^n}) = f_{n+1}(\tfrac{3k}{3^{n+1}}) = f_{n+2}(\tfrac{3k}{3^{n+1}}) \\ &= f_{n+2}(\tfrac{k}{3^n}) = f_{n+2}(\tfrac{3^2 k}{3^{n+2}}) = f_{n+3}(\tfrac{3^2 k}{3^{n+2}}) \\ &= f_{n+3}(\tfrac{k}{3^n}) = \cdots \\ &\quad \vdots \end{align*}

and hence $f(\tfrac{k}{3^n}) = f_{n}(\tfrac{k}{3^n})$. Now by Lemma again, for $n \geq N$ and $k \in \{1,\cdots,3^N\}$ we have

\begin{align*} \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{n+1}(x) \, dx &= \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{n}(x) \, dx \\ &\hspace{2em} + \sum_{j=3^{n-N}(k-1)}^{3^{n-N}k - 1} \left( f(\tfrac{j+1}{3^n}) - f(\tfrac{j}{3^n}) \right) \\ &\hspace{8em}\times \int_{\frac{j}{3^n}}^{\frac{j+1}{3^n}} \left( f_1(3^n x - j) - (3^n x - j) \right) dx. \end{align*}

Using the fact that $\int_{\frac{j}{3^n}}^{\frac{j+1}{3^n}} \left( f_1(3^n x - j) - (3^n x - j) \right) dx = \frac{\alpha}{2 \cdot 3^n}$ and that we have

\begin{align*} \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{n+1}(x) \, dx &= \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{n}(x) \, dx + \sum_{j=3^{n-N}(k-1)}^{3^{n-N}k - 1} \left( f(\tfrac{j+1}{3^n}) - f(\tfrac{j}{3^n}) \right) \cdot \frac{\alpha}{2\cdot 3^n} \\ &= \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{n}(x) \, dx + \frac{\alpha}{2\cdot 3^n} \left( f(\tfrac{k}{3^N}) - f(\tfrac{k-1}{3^N}) \right). \end{align*}

Iterating this relation for $n \geq N$ and using that $f_n \to f$ uniformly and utilizing the equality $f(\tfrac{k}{3^N}) = f_N(\tfrac{k}{3^N})$,

\begin{align*} \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f(x) \, dx &= \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{N}(x) \, dx + \sum_{n\geq N} \frac{\alpha}{2\cdot 3^n} \left( f_N(\tfrac{k}{3^N}) - f_N(\tfrac{k-1}{3^N}) \right) \\ &= \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{N}(x) \, dx + \frac{\alpha}{3^N} \left( f_N(\tfrac{k}{3^N}) - f_N(\tfrac{k-1}{3^N}) \right). \end{align*}

Finally, notice that $f_N$ is linear on the interval $[\frac{k-1}{3^N}, \frac{k}{3^N}]$. So the integral is computed as

$$ \int_{\frac{k-1}{3^N}}^{\frac{k}{3^N}} f_{N}(x) \, dx = \frac{1}{2\cdot 3^N} \left( f_N(\tfrac{k}{3^N}) + f_N(\tfrac{k-1}{3^N}) \right) $$

which proves the desired identity in the theorem. ////

Answer 2

I think this is less easy than it sounds. So far, I only have a solution when $f$ is ${\mathcal C}^2$. The density argument suggested in the comments unfortunately seems to break down along the way (see Martin R's comment below). We will show that the limit of $d_n=n(b_n-a_n)$ is $\frac{f(1)^2-f(0)^2}{2}$. With my additional hypothesis on $f$, $|f|+|f''|$ is bounded by some constant $M$ on $[0,1]$. For any subinterval $(a,b) \subseteq [0,1]$, we have the following error estimate for the trapezoidal rule (see for example, here for a proof)

$$ \Bigg| \int_a^b f(t)dt - (b-a)\bigg(\frac{f(a)+f(b)}{2}\bigg) \Bigg| \leq \frac{M(b-a)^3}{12} \tag{1} $$

Using (1) with $a=\frac{k-1}{n}$ and $b=\frac{k}{n}$, we deduce :

$$ \Bigg| \int_{\frac{k-1}{n}}^{\frac{k}{n}} f(t)dt - \frac{1}{n}\bigg(\frac{f(\frac{k-1}{n})+f(\frac{k}{n})}{2}\bigg) \Bigg| \leq \frac{M}{12n^3} \tag{2} $$

Multiplying by $f(\frac{k}{n})-f(\frac{k-1}{n})$ :

$$ \Bigg| \bigg(f(\frac{k}{n})-f(\frac{k-1}{n}\bigg)\int_{\frac{k-1}{n}}^{\frac{k}{n}} f(t)dt - \frac{1}{n}\bigg(\frac{f(\frac{k}{n})^2-f(\frac{k-1}{n})^2}{2}\bigg) \Bigg| \leq \frac{M}{12n^3}(|f(\frac{k}{n})|+|f(\frac{k-1}{n})|) \leq \frac{M^2}{6n^3} \tag{3} $$

and summing and multiplying by $n$, we deduce

$$ \Big|d_n -\frac{f(1)^2-f(0)^2}{2}\Big| \leq \frac{M^2}{6n^2} $$

which finishes the proof.

Answer 3

It seems we can compute limit in the case when $f$ is of bounded variation which means that even if counterexample exists it must look very ugly. $f$ is continious so it is uniformly continious so we can assume that $|\int_{\frac{k-1}{n}}^{\frac{k}{n}} f(t)dt - \frac{1}{2n}(f(\frac{k}{n}) + f(\frac{k-1}{n}))| < \frac{\epsilon}{n}$ with $\epsilon \to 0$ as $n\to \infty$. So we have:

$|n(b_n - a_n) - \frac{1}{2}\sum\limits_{k=1}^n (f(\frac{k}{n}) - f(\frac{k-1}{n}))(f(\frac{k}{n}) + f(\frac{k-1}{n}))|\le \epsilon\sum\limits_{k=1}^n |f(\frac{k}{n}) - f(\frac{k-1}{n})| \le \epsilon Var(f)$

On the other hand $\frac{1}{2}\sum\limits_{k=1}^n (f(\frac{k}{n}) - f(\frac{k-1}{n}))(f(\frac{k}{n}) + f(\frac{k-1}{n})) = \frac{1}{2}(f(1)^2 - f(0)^2)$ so the limit is equal to $\frac{1}{2}(f(1)^2 - f(0)^2)$.

Answer 4

It seems, if I didn't made any mistake, in general $n(b_n-a_n)$ may not converge! I'll construct an explict counterexample to it. Consider periodic function $g:\mathbb{R}\to \mathbb{R}$ defined as:

$$g(x) = \begin{cases}0, \{x\} \le \frac{1}{4}\\ 4x - 1, \frac{1}{4} \le \{x\} \le \frac{1}{2}\\ 1, \frac{1}{2} \le \{x\} \le \frac{3}{4}\\ 4 - 4x, \frac{3}{4} \le \{x\} \le 1\end{cases}$$

and put $g_n(x) = g(2^{9n}x)$. We will construct our function $f$ as series $f(x) = \sum\limits_{n = 1}^\infty h_ng_n(x)$ with $\sum\limits_{n = 1}^\infty |h_n| < \infty$. We will prove that $2*2^{9n}(b_{2*2^{9n}} - a_{2*2^{9n}})$ is unbounded for suitable choise of $h_n$ thus sequence from the post can not converge. We are interested in the following sum: \begin{equation} \sum\limits_{k = 1}^{2*2^{9n}} \left(f\left(\frac{k}{2*2^{9n}}\right) - f\left(\frac{k-1}{2*2^{9n}}\right)\right)\int_{\frac{k-1}{2*2^{9n}}}^{\frac{k}{2*2^{9n}}}f(x)dx. \end{equation} Since for fixed $n$ everything is absolutely convergent we are basically interested in computing \begin{equation} \sum\limits_{k = 1}^{2*2^{9n}} \left(g_r\left(\frac{k}{2*2^{9n}}\right) - g_r\left(\frac{k-1}{2*2^{9n}}\right)\right)\int_{\frac{k-1}{2*2^{9n}}}^{\frac{k}{2*2^{9n}}}g_m(x)dx\qquad (1) \end{equation} for any $n, r, m > 0$. If $r > n$ then $ \left(g_r\left(\frac{k}{2*2^{9n}}\right) - g_r\left(\frac{k-1}{2*2^{9n}}\right)\right) = 0$ and so we are not interested in this cases. If $r < n$ then $ \left(g_r\left(\frac{k}{2*2^{9n}}\right) - g_r\left(\frac{k-1}{2*2^{9n}}\right)\right)$ has intervals of $k$ on which it is constant(those intervals of the length $2^{-9r}$ up to some factor of $2$ or $4$) and up to constant on them it equals to $0, 1, 0, -1, 0, 1, 0, -1, \ldots$ Now we have three cases:

1) $m > r$. In this case every copy of $g$ contained in $f_m$ contains in some interval of $k$ and moreover every interval is divided into some number(fixed for fixed $m, r$) of copyes of $g$ so we have sum of the kind $0 + I + 0 - I + ... = 0$ since in every tuple of $4$ intervals we get $0$(from now on lets call those tuples "quads").

2) $m < r$. In this case every quad is contained in some copy of $g$ in $f_m$ and moreover this copy(or, more preciesly, interval, to which it correspondes) is divided into some number of this quads. Even more since $9$ is a huge number we can say that every quater of copy of $g$ is divided into some number of our quads. On the first and third quaters of $g$ we clearly has zero sum. With some computations one can show that second and fourth quaters also adds up to $0$.

3) $m = r$. In this case we up to some constant interested in $0*\int_0^{\frac{1}{4}}g(x)dx + 1*\int_\frac{1}{4}^\frac{1}{2}g(x)dx + 0*\int_\frac{1}{2}^\frac{3}{4}g(x)dx + (-1)*\int_\frac{3}{4}^1g(x)dx = 0$.

So the remainig case is $r = n$. In this case we would have $ \left(g_r\left(\frac{k}{2*2^{9n}}\right) - g_r\left(\frac{k-1}{2*2^{9n}}\right)\right) = (-1)^{k-1}$. First and second cases could be treated the same as before while in the third case we would have:

$$1*\int_0^\frac{1}{2}g(x)dx + (-1)*\int_\frac{1}{2}^1g(x)dx = \frac{-1}{4}.$$

So (1) is nonzero iff $n = r = m$ and equals to some fixed constant $c < 0$. Thus we have:

$$2*2^{9n}(b_{2*2^{9n}} - a_{2*2^{9n}}) = 2ch_n^2*2^{9n}.$$

Choosing $h_n = 2^{-n}$ we get what we want. Moreover since over some subsequence $h_n$ can decay arbitary slow we can not say anything better than $b_n - a_n \to 0$

In fact, when I was thiking about this problem I treated (1) as some kind of bilinear form on the space of continious functions so I wanted to find sequence of functions $(g_m)$ such that $<g_r, g_m>_n = c\delta_{n, m}\delta_{n, r}$ so I was searching for some kind of continious Rademacher functions.