Sean $a_1,a_2,\ldots ,a_M$ números enteros no negativos tales que$$\frac{1}{2^{a_1}}+\frac{1}{2^{a_2}}+\cdots +\frac{1}{2^{a_M}}=1.$$Demostrar que $a_i<M$ para todo $i$.
Y supongamos que existe $a_i$ tal que $a_i \geq m$
Entonces $a_1 \geq m$
Ahora supongamos que existe $K$ tal que:
$1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv 0 \pmod {2^u}$ y $a_1 - a_{k+1} \geq u$ Para algún $1 \leq u \leq m$ natural
Como $a_{k+1} \geq a_{k+2}...\geq a_m$ entonces $a_1- a_{k+1} \leq a_1 - a_{k+2} \leq ... \leq a_1 - a_m$
Así que si que si $a_1 - a_{k+1} \geq u$ entonces $ a_1 - a_{k+2}, ... ,a_1 - a_m$ también.
Así que $2^{a_1-a_{k+1}} \equiv 2^{a_1-a_{k+2}} ... \equiv 2^{a_1-a_{m}} \equiv 0 \pmod{2^u}$
Entonces $ 1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv \pmod{2^{k}}$
así que $a_1 - a_{k+1} \leq k-1$
Y tenemos caso base con $k = 2$.
Nota: Voy a usar $2^{-x}$ en vez de $\frac{1}{2^x}$ porque es más corto.
Resumen de la solución: Primero pruebo que en todas las sumas así hay dos $a_i$ que son iguales. Esto lo uso para hacer inducción, porque puedo sumar esos dos para crear una suma con un término menos pero que suma lo mismo, y así hasta llegar a $1 = 1$. También pruebo que en esta transformación, la propiedad $a_i<M$ se conserva. Entonces hago inducción y queda probado.
Lema 1: Para cualquier x entero, $2^m + 2^n = 2^x$ si y solo si $m = n = x - 1$
Prueba:
Las únicas dos potencias de 2 que difieren por 1 son $2^0$ y $2^1$, entonces
$d = 0$, $x - n = 1$.
$m = n = x - 1$. QED
Lema 1.2: Para cualquier x entero, si $m = n = x - 1$, $2^m + 2^n = 2^x$
Prueba: $ 2^x = 2^x = 2 \cdot 2^{x - 1} = 2^{x - 1} + 2^{x - 1} = 2^m + 2^n$. QED
Entonces:
Lema 1: Para cualquier x entero, $2^m + 2^n = 2^x$ si y solo si $m = n = x - 1$
Lema 2: Asumimos sin pérdida de generalidad que $a_m$ es el mayor de todos los numeros en conjunto, y que todos los numeros están ordenados de menor a mayor.
Lema 3: Para cualquier serie de sumas del tipo especificado en el problema con $m > 1$, siempre va a haber dos $a_x$ que sean iguales.
Vamos a probarlo por contradicción. Asumimos que todos son distintos.
Como $m > 1$, entonces todos los $a_x$ son mayores a $0$. (porque $2^{-0}+2^{-a_x}$ ya es $> 1$ sin importar el valor de $a_x$).
Es un hecho conocido que la suma infinita $2^{-1}+2^{-2}+2^{-3}...$ converge a 1.
En la suma $2^{-1}+2^{-2}+2^{-3}...$ hay infinitos terminos, todos de la forma $2^{-n}$ donde n es un entero positivo
En la suma $2^{-a_0}+2^{-a_1}+...+2^{-a_m}$ hay $m$ terminos, todos de la forma $2^{-n}$ donde n es un entero positivo
Entonces, por el principio del palomar, hay términos en la suma $2^{-1}+2^{-2}+2^{-3}...$ que no están en $2^{-a_0}+2^{-a_1}+...+2^{-a_m}$, pero no al revés (porque la suma $2^{-1}+2^{-2}+2^{-3}...$ tiene a todos los enteros negativos en los exponentes, pero $m$ es finito)
Entonces $2^{a_0}+2^{a_1}+...+2^{a_m} < 2^{-1}+2^{-2}+2^{-3}...$, entonces $2^{-a_0}+2^{-a_1}+...+2^{-a_m} < 1$ que contradice lo que dice el problema.
Entonces necesariamente hay dos $a_x$ que son iguales. QED
En este caso, $a_i - 1$ está en $S$ porque $a_x - 1$ está en $S$.
Por el lema 4.2.1, $a_i - 1 < q$. Entonces, $a_i < q + 1$. QED
Cubrimos todos los casos entonces $a_i < q + 1$ siempre. Entonces, $a_m < q + 1$ porque $i$ puede ser $m$. QED.
Tenemos una prueba para $a_m < m$ cuando $m = 1$, y $a_m < m$ cuando $m = n + 1$ y la condición se cumple para $m = n$. Entones, por inducción en los naturales, podemos probar que $a_m < m$ para todo $m > 0$. QED
Como $a_m$ es el mayor de los términos, entonces $a_i < m$ para todo $m$, $i$. QED