Pregunta final de la Abeja de Integración MIT 2023: Evaluar $\int^1_0 (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n})^2{\rm d}x$

Question

Estoy tratando de evaluar la última pregunta de la Final de la Bee de Integración del MIT 2023. $$\int^1_0 \left (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n} \right )^2{\rm d}x$$ Mi enfoque es dividir $(0,1)$ en intervalos de $1/2^n$ y escribir el término general del valor de $y$. Por ejemplo. Para $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$$ Sé que la integral final es simplemente sumar las áreas de todos los rectángulos infinitos pero no puedo resolverlo. Por favor ayuda. Gracias. (La respuesta final de esta pregunta es $27/32$. Se permitió a los candidatos resolverlo en 4 minutos.)

Answer 1

Aquí hay una solución un poco avanzada: Definimos $X_1, X_2, \ldots$ en $[0, 1]$ por

$$ X_k (x) := [\text{$k$-ésimo dígito en la expansión binaria de $x$}] = \lfloor 2^k x\rfloor - 2 \lfloor2^{k-1}x\rfloor. $$

Luego

\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*}

Ahora al considerar $[0, 1]$ como un espacio de probabilidad con la medida de probabilidad $\mathrm{d}x$, encontramos que $X_1, X_2, \ldots$ son variables i.i.d. $\text{Bernoulli}(\frac{1}{2})$. Por lo tanto,

\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*}

Usando la independencia, obtenemos $\mathbf{E}[X_j X_k] = \frac{1}{4} + \frac{1}{4} \mathbf{1}_{\{j = k\}}$. Por lo tanto, la esperanza se reduce a

\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*}

Answer 2

Esta respuesta utiliza el concepto algo más avanzado de que, en integrales de Riemann, cualquier número contable de discontinuidades (es decir, tienen medida cero) se pueden ignorar, como en la función de Thomae. Primero, definir

$$f(x) = \sum_{n=0}^\infty\frac{\left\lfloor 2^nx\right\rfloor}{3^n}, \; \; g(y) = \int_{0}^{y}f^2(x)dx \tag{1}\label{eq1A}$$

Usar la sustitución $x = 2z \; \; \to \; \; dx = 2dz$ para obtener

$$g(1) = 2\int_{0}^{0.5}\left(\sum_{n=0}^\infty\frac{\left\lfloor 2^{n+1}z\right\rfloor}{3^n}\right)^2 dz \tag{2}\label{eq2A}$$

Luego, para $0 \le z \le 0.5$, tenemos

$$\begin{equation}\begin{aligned} \sum_{n=0}^\infty\frac{\left\lfloor 2^{n+1}z\right\rfloor}{3^n} & = 3\sum_{n=0}^\infty\frac{\left\lfloor 2^{n+1}z\right\rfloor}{3^{n+1}} \\ & = 3\left(\sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z\right\rfloor}{3^{n}} -\frac{\lfloor2^{0}z\rfloor}{3^{0}}\right) \\ & = 3\left(\sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z\right\rfloor}{3^{n}}\right) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Sustituir esto en \eqref{eq2A} da

$$g(1) = 18g(0.5) \; \; \to \; \; g(0.5) = \frac{g(1)}{18} \tag{4}\label{eq4A}$$

De \eqref{eq1A}, usando la sustitución $x = 1 - z \; \; \to \; \; dx = -dz$ en la segunda integral a la derecha de la primera línea a continuación, y que $\lfloor m - a \rfloor = m - 1 - \lfloor a \rfloor$ para todos los enteros $m$ y no enteros $a$, obtenemos

$$\begin{equation}\begin{aligned} g(1) & = \int_{0}^{0.5}f^2(x)dx + \int_{0.5}^{1}f^2(x)dx \\ & = g(0.5) - \int_{0.5}^{0}\left(\sum_{n=0}^\infty\frac{\left\lfloor 2^n(1-z) \right\rfloor}{3^{n}}\right)^2 dz \\ & = g(0.5) + \int_{0}^{0.5}\left(\sum_{n=0}^\infty\frac{2^n - 1}{3^n} - \sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)^2 dz \\ & = g(0.5) + \int_{0}^{0.5}\left(\left(\frac{1}{1-\frac{2}{3}} - \frac{1}{1-\frac{1}{3}}\right) - \sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)^2 dz \\ & = g(0.5) + \int_{0}^{0.5}\left(\frac{3}{2} - \sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)^2 dz \\ & = g(0.5) + \int_{0}^{0.5}\left(\frac{9}{4} - 3\sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}} + \left(\sum_{n=0}^\infty\frac{\left\lfloor 2^{n+1}z\right\rfloor}{3^n}\right)^2\right)dz \\ & = g(0.5) + \frac{9}{8} - 3\int_{0}^{0.5}f(x)dx + g(0.5) \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

Luego, utilizando $x = 0.5 - z \; \; \to \; \; dx = -dz$, así como $\lfloor 2^{0}(0.5 - z) \rfloor = \lfloor 2^{1}(0.5 - z) \rfloor = 0$ y $\lfloor 2^{0}z \rfloor = \lfloor 2^{1}z \rfloor = 0$ para $0 \lt z \le 0.25$, entonces

$$\begin{equation}\begin{aligned} \int_{0}^{0.5}f(x)dx & = \int_{0}^{0.25}f(x)dx + \int_{0.25}^{0.5}f(x)dx \\ & = \int_{0}^{0.25}f(x)dx - \int_{0.25}^{0}\sum_{n=0}^\infty\frac{\left\lfloor 2^n(0.5-z) \right\rfloor}{3^{n}}dz \\ & = \int_{0}^{0.25}f(x)dx + \int_{0}^{0.25}\left(\sum_{n=2}^\infty\frac{2^{n-1} - 1}{3^n} - \sum_{n=2}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)dz \\ & = \int_{0}^{0.25}f(x)dx + \int_{0}^{0.25}\left(\left(\frac{\frac{2}{9}}{1-\frac{2}{3}} - \frac{\frac{1}{9}}{1-\frac{1}{3}}\right) - \sum_{n=2}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)dz \\ & = \int_{0}^{0.25}f(x)dx + \int_{0}^{0.25}\left(\frac{1}{2} - \sum_{n=0}^\infty\frac{\left\lfloor 2^{n}z \right\rfloor}{3^{n}}\right)dz \\ & = \int_{0}^{0.25}f(x)dx + \frac{1}{8} - \int_{0}^{0.25}f(x)dx \\ & = \frac{1}{8} \end{aligned}\end{equation}\tag{6}\label{eq6A}$$

Sustituyendo esto en \eqref{eq5A}, y usando \eqref{eq4A}, obtenemos

$$\begin{equation}\begin{aligned} g(1) & = 2g(0.5) + \frac{9}{8} - 3\left(\frac{1}{8}\right) \\ g(1) & = \frac{g(1)}{9} + \frac{3}{4} \\ \frac{8g(1)}{9} & = \frac{3}{4} \\ g(1) & = \frac{27}{32} \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

Answer 3

$\newcommand{\d}{\,\mathrm{d}}$Lo primero que me llama la atención es que deberíamos expandir la serie al cuadrado. Llame a esta integral $I$. Al expandir en términos pares e impares, desde $n\ge2$ (los sumandos correspondientes $n=0,1$ son claramente cero al examinar los pisos) tenemos: $$\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}$$

Por lo tanto, necesitamos averiguar cómo evaluar $\int_0^1\lfloor2^ax\rfloor\lfloor2^bx\rfloor\d x$ donde $a\le b$ son enteros positivos. Con ese fin, necesitamos dividir $(0,1)$ en subdivisiones finas donde cada piso sea constante: $$\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}$$Usando fórmulas estándar de sumatorias.

Solo insertamos $a,b$ en la fórmula anterior, luego colocamos el resultado en la expresión en serie de $I$. Ya no hay detalles interesantes: es simplemente un proceso tedioso de usar la suma de una serie geométrica muchas, muchas, muchas, muchas, muchas veces, y sale el resultado deseado.

Este es un método. El alto nivel de tedio asociado a esto me hace pensar que no es la elegante solución de $4$ minutos, pero es una solución que es razonablemente fácil de llevar a cabo razonablemente rápido siempre y cuando no cometas errores con tu álgebra.

Por ejemplo, demostraré cómo evaluar las subseries que involucran $\lfloor2^nx\rfloor^2$. Tomamos $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}$$Probablemente sea sensato dejar estas fracciones expandidas en caso de que haya cancelaciones con las otras series.

Answer 4

Aquí hay una solución elemental:

Define

$$ I_b = \int_0^b \left(\sum_{n=1}^\infty \frac{\lfloor 2^nx\rfloor}{3^n}\right)^2\,dx $$ La idea es escribir $I_1$ en términos de $I_{1/2}$ de dos maneras diferentes: una usando la sustitución $x \rightarrow 2x$, la otra dividiendo el rango integral en dos y escribiendo ambas partes en términos de $I_{1/2}$. Luego resolvemos el sistema de ecuaciones para $I_1$.

La sustitución es sencilla, solo hay que tener en cuenta que $\lfloor 2^1x\rfloor = 0$ para $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*} $$

Otra manera de escribir $I_1$ es la siguiente:

$$ \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*} $$

Ahora la integral sin el cuadrado es mucho más fácil de resolver:

$$ \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}{4}\cdot\frac{1}{2} = \frac{1}{8} \end{align*} $$

Recordando que $I_{1/2} = I_1/18$, sustituimos los valores y resolvemos para $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} $$

Answer 5

Solución oficial (del autor)

Escriba $ f (x) $ para la suma en el integrando. Supongamos que $ x \in [0,1) $ tiene una representación binaria $ x = (0.a_1a_2a_3\cdots)_2 = \sum_{k\geq1} a_k 2^{-k} $, donde $ a_k \in \{0,1\} $ y la secuencia $(a_k)$ no es eventualmente toda 1s. Entonces \begin{align*} f(x) & = \frac{(a_1)_2}{3} + \frac{(a_1a_2)_2}{3^2} + \frac{(a_1a_2a_3)_2}{3^3} + \cdots \\ & = a_1 \left( \frac13 + \frac2{3^2} + \frac{2^2}{3^3} + \cdots \right) + a_2 \left( \frac1{3^2} + \frac2{3^3} + \frac{2^2}{3^4} + \cdots \right) + \cdots \\ & = \left(1 + \frac23 + \left( \frac23 \right)^2 + \cdots \right) \left( \frac{a_1}3 + \frac{a_2}{3^2} + \cdots \right) \\ & = 3\sum_{k\geq1} a_k 3^{-k}. \end{align*} La forma más simple de terminar es reinterpretando la integral en términos probabilísticos. Queremos encontrar $\int_0^1 f(x)^2\,dx$, que es lo mismo que la expectativa de $f(x)^2$ cuando $x$ se elige uniformemente al azar de $[0,1)$. Pero esto es equivalente a elegir los dígitos binarios $(a_k)$ uniformemente de $\{0,1\}$, independientemente entre sí. Por lo tanto \begin{align*} \int_0^1 f(x)^2\,dx & = \mathbb E(f(x)^2) \\ & = \mathbb E\left( 3\sum_{k\geq1} a_k 3^{-k} \right)^2 \\ & = 9\mathbb E\left( \sum_{k\geq1} a_k 9^{-k} + \sum_{k\neq l} a_k a_l 3^{-k-l} \right) \\ & = 9 \left( \frac12 \sum_{k\geq1} 9^{-k} + \frac14 \sum_{k\neq l} 3^{-k-l} \right) \\ & = 9 \left( \frac14 \sum_{k\geq1} 9^{-k} + \frac14 \sum_{k,l} 3^{-k-l} \right) \\ & = 9 \left( \frac14 \cdot \frac18 + \frac14 \left( \frac12 \right)^2 \right) \\ & = \frac{27}{32}. \end{align*}