This problem has been discussed before, but I tried to write a more detailed proof based on this answer.

Problem: prove that $\displaystyle\lim_{n\to\infty}f_n(x)$ does not exist for any $x\in [0,1]$ if the sequence $(f_n)_{n\in\Bbb N}$ of functions $f_n:\Bbb R\to\Bbb R$ is given by $$f_n=1_{\left[\frac{n-2^k}{2^k},\frac{n-2^k+1}{2^k}\right]},\text{ where }k=\left\lfloor\log_2 n\right\rfloor.$$

My attempt:

Let's write $n\in\Bbb N$ as $n=2^m+k,$ where $m\in\Bbb N\cup\{0\}$ and $k\in\{0,\ldots,2^m-1\}.$ Then, \begin{aligned}\frac{n}{2^k}-1&=\frac{2^{\log_2(2^m+k)}}{2^{\left\lfloor\log_2\left(2^m+k\right)\right\rfloor}}-1\\&=2^{\log_2\left(2^m+k\right)-\left\lfloor\log_2\left(2^m+k\right)\right\rfloor}-1\\&=2^{m+\log_2\left(1+\frac{k}{2^m}\right)-m}-1\\&=2^{\log_2\left(1+\frac{k}{2^m}\right)}-1\\&=\frac{k}{2^m}.\end{aligned}

We can now find an increasing sequence $\left(\frac{p_n}{q_n}\right)_{n\in\Bbb N}$ of fractions with $q_n$ being powers of $2$ s. t. $\displaystyle\lim_{n\to\infty}\frac{p_n}{q_n}=x,$ which shows that for each $x\in[0,1],$ there is a subsequence $\left(f_{p_n}\right)_{n\in\Bbb N}$ s. t. $f_{p_n}(x)=1,\forall n\in\Bbb N.$ On the other hand, if $a_n:=\frac{n-2^{k_n}}{2^{k_n}},k_n=\left\lfloor\log_2(n)\right\rfloor,$ and we consider the following subsequence: \begin{aligned}b_m:=a_{2^m-1}&=\frac{2^m-1}{2^{k_{2^m-1}}}-1\\&=\frac{2^m-1}{2^{\left\lfloor\log_2\left(2^m-1\right)\right\rfloor}}-1\\&=\frac{2^m-1}{2^{m-1}}-1\\&=\frac{2^{m-1}}{2^{m-1}}\cdot\left(2-2^{1-m}\right)-1\\&=1-2^{1-m},\\\lim_{m\to\infty}b_m&=1\end{aligned} we see that, for any given $x\in[0,1],$ there is a subsequence $\left(f_{q_n}\right)_{n\in\Bbb N}$ s. t. $f_{q_n}(x)=0,\forall n\in\Bbb N.$

Therefore, the limit $\displaystyle\lim_{n\to\infty}f_n(x)$ doesn't exist for any $x\in[0,1].$

Is there anything wrong with my deduction and how can I improve my answer?


1 Answer 1


Since $k\neq\lfloor\log_2(2^m+k)\rfloor$ in general, your first line of working: $$\frac{n}{2^k}-1=\frac{2^{\log_2(2^m+k)}}{2^{\lfloor\log_2(2^m+k)\rfloor}}-1$$Is wrong. I assume you meant, $\frac{n}{2^m}-1=\cdots=\frac{k}{2^m}$. But that is a trivial calculation that does not need to involve (dubious?) manipulations with logarithms: $$\frac{n}{2^m}-1=\frac{n-2^m}{2^m}=\frac{k}{2^m}$$Your stated equation $\frac{n}{2^{\color{red}{k}}}-1=\frac{k}{2^m}$ is wrong. Note that if $n=2^m+k$ with $0\le k<2^m$, $\lfloor\log_2(n)\rfloor=m$, not $k$, so there is a confusion of notation with the $k$s appearing in the definition of the typewriter sequence.

I would say something like, "fix $x\in[0,1]$", to preface the next section. It's not clear to me at all why you expect $f_{p_n}(x)=1$, e.g. it is not given that $q_n=2^{\lfloor\log_2(p_n)\rfloor}$ or anything like that. You've shown that $b_m\to1$ but why should that imply the existence of $(q_n)_n$ with $f_{q_n}(x)\to0$? What if $x=1$?

If $x<1$ then you have shown there is a sequence along which $f_{b_m}(x)\to0$, but the case $x=1$ remains to be handled. However, the idea of showing there is a sequence along which $f_{b_m}(x)\to1$ is not, in any way clear to me, handled yet.

Fix $x\in(0,1)$ and $n\in\Bbb N$. Take $m:=1+\max(n,\lceil x^{-1}\rceil,\lceil(1-x)^{-1}\rceil)\in\Bbb N$. Using $2^m>m$, by choice of $m$ I know $x\in(2^{-m},1-2^{-m})$ so that there exists a unique integer $1\le k\le 2^m-1$ satisfying: $$\frac{k}{2^m}\le x\le\frac{k+1}{2^m}$$I define $n_1:=2^m$ and $n_2:=2^m+k$ for this choice of $k$ and $m$ (my $m$ is actually a lot larger than it needs to be, but I don't want to clutter the notation with lots of logs).

  • For any $n\in\Bbb N$, such $n_1,n_2\in\Bbb N$ exist with $n_1,n_2$ both greater than $n$
  • For these $n_{1,2}$, $f_{n_1}(x)=0$ and $f_{n_2}(x)=1$.

Hence $(f_n(x))_{n\in\Bbb N}$ is not convergent.

I invite you to handle the cases $x=0,1$ yourself.

  • 1
    $\begingroup$ Thank you for pointing out my abuse of notation. Also, your last edit made the choice of $m$ much clearer! I posted a sketch that I changed a few times and, while thinking about the density of dyadic integers, I totally forgot what properties the denominator should've had. $\endgroup$
    – PinkyWay
    May 21, 2023 at 10:33
  • 1
    $\begingroup$ @Invisible No worries. And yeah, in fact it is true that $x\in(1/m,1-1/m)$ but since $2^m>m$ it's true that $x\in(2^{-m},1-2^{-m})$ too. I realised it was maybe obscure, what I was doing. In fact, I could replace my $m$ with $\lceil\log_2(m)\rceil$ and still have a valid solution $\endgroup$
    – FShrike
    May 21, 2023 at 10:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .