Números enteros positivos expresables como sumas de potencias de 2

Question

Necesito demostrar que cualquier número entero positivo es expresable como $$x=2^{j_0}+2^{j_1}+2^{j_2}+...+2^{j_m}$$ donde $m\ge 0$ y $0\le j_0\lt j_1\lt j_2\lt ... \lt j_m. $

Creo que entiendo la esencia de la prueba; lo que quiero decir es que creo entender intuitivamente lo que ocurre aquí, pero busco una verificación, ya sea un argumento más simplista o el rigor adecuado.

Empiezo diciendo que un entero positivo es expresable como un entero par o impar. Por lo tanto, un número entero positivo, $x=2k$ o $x=2k+1$ para algún número entero positivo $k$ . Si $x$ es impar, entonces podemos escribir $1=2^0$ . Ahora, un número entero $k$ también es expresable como un entero par o impar. Por lo tanto, ahora tenemos $2^2=4$ posibilidades; si $x$ está en paz; $$x=2k=2(2k_1)=2^2k_1$$ $$x=2k=2(2k_1+1)=2^2k_1+2^1$$ si $x$ es impar; $$x=2k+1=2(2k_1)+1=2^2k_1+2^0$$ $$x=2k+1=2(2k_1+1)+1=2^2k_1+2^1+2^0$$ está claro que $k>k_1$ desde $k=2k_1$ . Ahora repetimos el proceso con $k_1=2k_2$ o $k_1=2k_2+1$ y eventualmente, $k_n=2k_{n+1}$ o $k_n=2k_{n+1}+1$ . Desde $x$ es un número entero positivo, $k_i$ es positivo para todos los $i=1,2,...,n$ y, por tanto, cuanto mayor sea el $i$ cuanto más pequeño sea el $k_i$ . Este proceso termina finalmente, ya que $k_i>0$ y por lo tanto $k_n=1$

Ahora cómo simplifico este argumento, suponiendo que sea correcto. Si no es correcto,, ¿cómo lo reparo o lo hago más riguroso?

Answer 1

Podemos hacerlo por inducción (fuerte). Sea $P(x)$ sea la afirmación de que $x$ es una suma de $0$ o más poderes distintos de $2$ . El número $0$ es una suma de $0$ o más poderes distintos de $2$ . Así que $P(0)$ se mantiene.

Supongamos que $P(k)$ es cierto para todos los $k\lt x$ . Demostramos que $P(x)$ es cierto. Sea $2^p$ sea la mayor potencia de $2$ que es $\le x$ . Entonces $x-2^p \lt 2^{p-1}$ . Por la hipótesis de inducción, $x-2^p$ es expresable como una suma de $0$ o más poderes distintos de $2$ . Todos estos poderes de $2$ son $\lt 2^p$ ya que $x-2^p\lt 2^p$ . De ello se desprende que $x=2^p$ más una suma de $0$ o más poderes distintos de $2$ que son inferiores a $2^p$ . Así que $x$ es una suma de potencias distintas de $2$ .

Answer 2

Mucho más en general, puedes probar esto:

Dejemos que $(b_k)_{k=1}^{\infty}$ sea una secuencia de enteros tal que cada $b_k \ge 2$ y que $B_0 = 1$ y $B_k = \prod_{j=1}^k b_j$ para $k \ge 1$ . Entonces todo entero positivo $n$ puede representarse de forma única en la forma $n = \sum_{k=0}^{D(n)} d_kB_k$ donde $D(n)$ es un número entero positivo que depende de $n$ y el $d_k$ son números enteros tales que $0 \le d_k < b_{k+1}$ .

Si todos los $b_k$ son iguales a $b$ , esto da la representación estándar en base $b$ .

Si $b_k = k+1$ , esta la representación "factorial".

Esto tiene su contrapartida:

Si $B_k$ es una secuencia creciente de enteros positivos con $B_1 \ge 2$ y $\frac{B_{k+1}}{B_k} \ge 2$ entonces todo entero positivo $n$ se puede representar en la forma $n = \sum_{k=0}^{D(n)} d_kB_k$ con $d_k$ enteros tales que $0 \le d_k < \frac{B_{k+1}}{B_k}$ y la representación es única si y sólo si $B_k $ divide $B_{k+1}$ para todos $k$ .

Answer 3

Esto es sólo la expresión de $x$ como binario (base $2$ ) número, ¿no es así?

Answer 4

Como tú dices, $x=2k$ o $x=2k+1$ . Ahora, $k<x$ y así, por inducción, $k$ puede expresarse como una suma de distintas potencias de $2$ . Entonces $2k$ también puede expresarse así. Si $x=2k$ hemos terminado. Si $x=2k+1$ entonces $x=2k+2^0$ y hemos terminado, porque $2^0$ no aparece en la expresión de $2k$ .

Answer 5

Para una variación, podemos utilizar la contradicción.

Supongamos que existe un conjunto de enteros positivos que no puede expresarse como la suma de potencias distintas de dos. Como los enteros positivos están bien ordenados, debe haber uno más pequeño. Llamémoslo $x$ .

Ahora, reste de $x$ la mayor potencia de dos que aún es menor que $x$ . Llame a este número $y$ .

$y = x-2^N$

Si $y$ es expresable como una suma de potencias distintas, entonces $x = y + 2^N$ contradiciendo nuestra suposición. No corremos el riesgo de $2^N$ que ya aparece en $y$ desde $y$ debe ser menor que $2^N$ . Si este no fuera el caso, $2^N$ sería menor que $x/2$ y por lo tanto no ser la mayor potencia de dos menos que $x$ ). Por lo tanto, $y$ no puede expresarse como una suma de potencias distintas de dos.

Pero, $y$ es menor que $x$ contradiciendo nuestra suposición de que $x$ era el ejemplo más pequeño. Nuestra única salida posible es establecer $y=0$ ya que $0$ no es un número entero positivo, evitando así la contradicción de la parte del "ejemplo más pequeño". Sin embargo, esto significa que $x=2^N$ lo que obviamente contradice la suposición de "no es una suma de potencias de dos".

Dado que nuestra suposición no conduce más que a contradicciones, debe ser falsa. Todos los números son expresables como suma de potencias distintas de dos.