Why does this simple function converge pointwise to every positive measurable function

Question

Let $f$ be a measurable function.

Then

$$ f_n : = \sum_{k=1}^{n 2^n} \left( \frac{k-1}{2^n} \right) \mathbb{1}_{ \left\{ \frac{k-1}{2^n} \leq f < \frac{k}{2^n} \right\} } + n \mathbb{1}_{\left\{ f \geq n \right\}} $$ converges pointwise to $f$

I'm struggling to see how this function is pointwise increasing to $f$, and that

$$| {f - f_n } | \leq \frac{1}{2^n}$$

I see how $\frac{k}{2^n} - \frac{k-1}{2^n}$ leads to that inequality bu how do we know $f = k/2^n$?

Answer 1

It looks like your function $f$ is non-negative. Then you can think of this expression as the result of an algorithm which goes something like this:

1. First cut off the function $f$ at height $n$, i.e. everywhere that your function exceeds the value $n$, simply replace it by a function taking exactly the value $n$. This gives you the final term in the expression.
2. Now divide up the $y$ axis into little intervals of width $2^{-n}$, this means you put notches on the $y$ axis at the points $\{k/2^n : k = 0,1,2,3,...,n2^n\}$. You only need to go up to $k = n2^n$ because you already cut-off your function to make its maximum value $n$.
3. Then for each $k$ in turn, look at where your function takes values between $(k-1)/2^n$ and $k/2^n$. On this set, you replace by a function taking exactly the value $(k-1)/2^n$. Notice that when you do this, you alter the function pointwise by at most $2^{-n}$.

OK so now I don't fully understand your questions. It's not literally true that $\|f-f_n\|_{\infty}$ is small, because $f$ might be unbounded.

Answer 2

This works for a positive function $f$. Let $I_j^k = \left(\frac{j-1}{2^k},\frac{j}{2^k}\right]$ with $j \in \{1, \dots k2^k\}$ and $E_{k,j} = \{x : f(x) \in I_j^k\}$, $E_k = \{f > k\}$. For each fixed $k$, the latter partition the image of $f$ (except maybe when $f$ is zero, in which case each $f_n$ is zero and there is nothing to prove). So, fix an $x$ in the domain of $f$ so that $f(x) > 0$. Then, there exists $n \in \mathbb{N}$ so that $x < n$. Thus, $f_i(x) = i$ when $i < n$. We can thus restrict ourselves to prove monotony and convergence for $k > n$. Now, for each step $k$, since $f(x) > 0$ there exists $j_k$ so that $f(x) \in I_{k,j_k}$ and so $$ f_k(x) = \frac{j_k-1}{2} \quad (\forall k > n). $$

Now, since $f(x), f_k(x) \in I_{k,j_k}$ for each $k > n$,

$$ |f(x) - f_k(x)| \leq |I_{k,j_k}| = \frac{1}{2^k} \to 0. $$

Thus, $f_k \to f$ pointwise. Now we ought to see that the convergence is monotone. For convenience, we can do it pointwise, and so our task reduces to seeing that the sequence $\frac{j_k-1}{2}$ is increasing. From the fact that

$$ f(x) \in \left(\frac{j_k-1}{2^k},\frac{j_k}{2^k}\right] = \left(\frac{2j_k-2}{2^{k+1}},\frac{2j_k-1}{2^{k+1}}\right] \sqcup \left(\frac{2j_k-1}{2^{k+1}},\frac{2j_k}{2^{k+1}}\right] $$

we know that $j_{k+1}$ is either $2j_k-1$ or $2j_k$. In any case we get $j_{k+1} -1 \geq 2j_k - 2$ and diving by $2^{k+1}$, we get

$$ \frac{j_{k+1} -1 }{2^{k+1}} \geq \frac{j_k-1}{2^k} $$

as desired.