Question from MIT integration Bee 2023 final: Evaluate $\int^1_0 (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n})^2{\rm d}x$ I am trying to evaluate the last question from MIT integration Bee 2023 Final.
$$\int^1_0 \left (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n} \right )^2{\rm d}x$$
My approach is to divide $(0,1)$ into $1/2^n$ intervals and write the general term of the $y$-value. E.g. For $x \in (k/2^n, (k+1)/2^n)$,
$$f(x)=\left (\sum^{n-1}_{k=0}\frac{\left\lfloor k/2^k\right\rfloor}{3^{n-k}}\right)^2$$
I know that the final integral is just summing up the areas of all the infinite rectangles but I can't solve it. Please help. Thank you.
(The final answer of this question is $27/32$. Candidates were allowed to solve it within 4 minutes.)
 A: $\newcommand{\d}{\,\mathrm{d}}$The first thing that jumps at me is that we should expand the squared series. Call this integral $I$. By expanding into odd and even terms, from $n\ge2$ (the corresponding $n=0,1$ summands is clearly zero by examining the floors) we have: $$\begin{align}I&=\sum_{n\ge2}3^{-n}\sum_{k=0}^n\int_0^1\lfloor2^kx\rfloor\lfloor2^{n-k}x\rfloor\d x\\&=\sum_{n\ge1}3^{-2n}\left(2\sum_{k=1}^{n-1}\int_0^1\lfloor2^kx\rfloor\lfloor2^{2n-k}\rfloor\d x+\int_0^1\lfloor2^nx\rfloor^2\d x\right)\\&+2\sum_{n\ge1}3^{-(2n+1)}\sum_{k=1}^n\int_0^1\lfloor2^kx\rfloor\lfloor2^{2n-k+1}x\rfloor\d x\end{align}$$
So we need to figure out how to evaluate $\int_0^1\lfloor2^ax\rfloor\lfloor2^bx\rfloor\d x$ where $a\le b$ are positive integers. To that end, we need to partition $(0,1)$ into fine subdivisions where each floor is constant: $$\begin{align}\int_0^1\lfloor2^ax\rfloor\lfloor2^bx\rfloor\d x&=\sum_{j=0}^{2^a-1}\sum_{i=0}^{2^{b-a}-1}\int_{(j2^{b-a}+i)\cdot2^{-b}}^{(j2^{b-a}+i+1)\cdot2^{-b}}\lfloor2^ax\rfloor\lfloor2^bx\rfloor\d x\\&=\sum_{j=0}^{2^a-1}\sum_{i=0}^{2^{b-a}-1}2^{-b}(j)(j2^{b-a}+i)\\&=\sum_{j=0}^{2^a-1}\sum_{i=0}^{2^{b-a}-1}j^22^{-a}+ij2^{-b}\\&=\sum_{j=0}^{2^a-1}(j^2\cdot2^{b-2a}+j\cdot(2^{b-2a-1}-2^{-a-1})\\&=\cdots\\&=\frac{1}{3}2^{b+a}-\frac{1}{4}(2^b+2^a)-\frac{1}{12}2^{b-a}+\frac{1}{4}\end{align}$$Using standard summation formulae.
We just insert $a,b$ into the above formula, then plug the result into the series expression for $I$. There are no longer any interesting details: it is just a tedious process of using the sum of a geometric series many many many many many times, and out pops the desired result.
This is a method. The high level of tedium associated to it makes me think this is not the fancy $4$-minute solution, but it is a solution that is reasonably easy to carry out reasonably quickly so long as you don't make mistakes with your algebra.
For example, I will demonstrate how to evaluate the subseries involving $\lfloor2^nx\rfloor^2$. We let $a=b=n$. $$\begin{align}\sum_{n\ge1}3^{-2n}\int_0^1\lfloor2^nx\rfloor^2\d x&=\sum_{n\ge1}3^{-2n}\frac{1}{3}2^{2n}-\sum_{n\ge1}3^{-2n}\frac{1}{4}2\cdot2^n-\sum_{n\ge1}3^{-2n}\left(\frac{1}{12}2^0+\frac{1}{4}\right)\\&=\frac{1}{3}\sum_{n\ge1}\left(\frac{4}{9}\right)^n-\frac{1}{2}\sum_{n\ge1}\left(\frac{2}{9}\right)^n+\frac{1}{6}\sum_{n\ge1}9^{-n}\\&=\frac{1}{3}\cdot\frac{4}{9}\cdot\frac{1}{1-\frac{4}{9}}-\frac{1}{2}\cdot\frac{2}{9}\cdot\frac{1}{1-\frac{2}{9}}+\frac{1}{6}\cdot\frac{1}{9}\cdot\frac{1}{1-\frac{1}{9}}\\&=\frac{4}{15}-\frac{1}{7}+\frac{1}{48}\end{align}$$It is probably sensible to leave these fractions expanded in case there are cancellations with the other series.
A: Here's an elementary solution:
Define
$$
I_b = \int_0^b \left(\sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\right)^2\,dx
$$
The idea is to write $I_1$ in terms of $I_{1/2}$ in two different ways: one using the substitution $x \rightarrow 2x$, the other by splitting the integral range into two and writing both parts in terms of $I_{1/2}$. Then we solve the system of equations for $I_1$.
The substitution is straightforward, you just have to note that $\lfloor 2^1x\rfloor = 0$ for $0\le x<1/2$:
$$
\begin{align*}
I_1 &= 2\int_0^{1/2} \left(\sum_{n=1}^\infty \frac{\lfloor 2^{n+1}x\rfloor}{3^n}\right)^2\,dx = 2\int_0^{1/2} \left(\sum_{n=\color{red}{2}}^\infty \frac{\lfloor 2^nx\rfloor}{3^{n-1}}\right)^2\,dx \\
&= 2\int_0^{1/2} \left(3\sum_{n=\color{red}{1}}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\right)^2\,dx = 18\,I_{1/2}
\end{align*}
$$
The other way to write $I_1$ is as follows:
$$
\begin{align*}
I_1 &= \int_0^{1/2} \left(\sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\right)^2\,dx + \int_{1/2}^1 \left(\sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\right)^2\,dx \\
&= I_{1/2} + \int_0^{1/2} \left(\sum_{n=1}^\infty \frac{\lfloor 2^n(x+1/2)\rfloor}{3^n}\right)^2\,dx \\
&= I_{1/2} + \int_0^{1/2} \left(\sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n} + \underbrace{\sum_{n=1}^\infty \frac{2^{n-1}}{3^n}}_{=1}\right)^2\,dx \\
&= 2\,I_{1/2} + 2\int_0^{1/2} \sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\,dx + \frac{1}{2}
\end{align*}
$$
Now the integral without the square is much easier to solve:
$$
\begin{align*}
\int_0^{1/2} \sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\,dx &= \sum_{n=1}^\infty \frac{1}{3^n} \int_0^{1/2} \lfloor 2^nx\rfloor\,dx \\
&= \sum_{n=1}^\infty \frac{1}{3^n}\cdot\frac{1}{2^n} \int_0^{2^{n-1}} \lfloor x\rfloor\,dx \\
&= \sum_{n=1}^\infty \frac{1}{3^n}\cdot\frac{1}{2^n} \sum_{k=1}^{2^{n-1}-1} k \\
&= \sum_{n=1}^\infty \frac{1}{3^n}\cdot\frac{1}{2^n}\cdot\frac{1}{2}2^{n-1}\left(2^{n-1}-1\right) \\
&= \frac{1}{8}\sum_{n=1}^\infty \left(\frac{2}{3}\right)^n - \frac{1}{4}\sum_{n=1}^\infty \left(\frac{1}{3}\right)^n \\
&= \frac{1}{8}\cdot 2 - \frac{1}{8}\cdot\frac{1}{2} = \frac{1}{8}
\end{align*}
$$
Recalling that $I_{1/2} = I_1/18$, substitute the values and solve for $I_1$:
$$
I_1 = 2\cdot\frac{1}{18}\,I_1 + 2\cdot\frac{1}{8} + \frac{1}{2} \\
\Rightarrow\frac{8}{9}\,I_1 = \frac{3}{4} \\
\Rightarrow I_1 = \frac{27}{32}
$$
A: Here is a slightly advanced solution: Define $X_1, X_2, \ldots$ on $[0, 1]$ by
$$ X_k (x) := [\text{$k$th digit in the binary expansion of $x$}] = \lfloor 2^k x\rfloor - 2 \lfloor2^{k-1}x\rfloor. $$
Then
\begin{align*}
\sum_{n=0}^{\infty} \frac{\lfloor 2^n x \rfloor}{3^n}
= \sum_{n=1}^{\infty} \frac{1}{3^n} \sum_{k=1}^{n} 2^{n-k}X_k
= \sum_{k=1}^{\infty} \frac{X_k}{2^k} \sum_{n=k}^{\infty} \frac{2^n}{3^n}
= \sum_{k=1}^{\infty} \frac{X_k}{3^{k-1}} .
\end{align*}
Now by regarding $[0, 1]$ as a probability space with the probability measure $\mathrm{d}x$, we find that $X_1, X_2, \ldots$ are i.i.d. $\text{Bernoulli}(\frac{1}{2})$ variables. So,
\begin{align*}
\int_{0}^{1} \left( \sum_{n=0}^{\infty} \frac{\lfloor 2^n x \rfloor}{3^n} \right)^2 \, \mathrm{d}x
= \mathbf{E} \left[ \left( \sum_{k=1}^{\infty} \frac{X_k}{3^{k-1}} \right)^2 \right]
= \sum_{j,k=1}^{\infty} \frac{1}{3^{j+k-2}} \mathbf{E}[X_j X_k].
\end{align*}
Using the independence, we get $\mathbf{E}[X_j X_k] = \frac{1}{4} + \frac{1}{4} \mathbf{1}_{\{j = k\}}$. Hence, the expectation reduces to
\begin{align*}
\sum_{j,k=1}^{\infty} \frac{1}{3^{j+k-2}} \left( \frac{1}{4} + \frac{1}{4} \mathbf{1}_{\{j = k\}} \right)
= \frac{1}{4} \left( \sum_{k=1}^{\infty} \frac{1}{3^{k-1}} \right)^2 + \frac{1}{4} \left( \sum_{k=1}^{\infty} \frac{1}{9^{k-1}} \right)
= \boxed{\frac{27}{32}}
\end{align*}
