Cna probar cada entero positivo es expresable en binario?

Question

El uso del sistema binario para escribir números enteros se supone que cada número puede ser representado como la suma de las potencias de dos, donde cada potencia de dos es que no se repitió más de una vez.

Cómo podemos probar que todo entero es expresable en forma binaria?

Answer 1

Tal vez el más intuitivo prueba de ello es la elaboración de un explícito algoritmo de búsqueda de la base de $2$ de representación. (El número para ser representado en binario es $c$) :

$1)$ Vamos a encontrar $n$ que $2^{n} \le c < 2^{n+1}$. El resultado de la división entera de a $c = 2^n + r_1$.Aquí $r_1$ es nuestra primera (no cero) dígitos.

$2)$ Ahora vamos a tomar el $r_1$ (lo cual es, obviamente, menos de $2^n$) y se divide por $2^{n−1}$,

Si $~; ~2^{n-2} \le r < 2^{n-1}$, $$r_1=2^{n-1}+r_2 \implies c = 2^n +2^{n-1}+r_2 ~~~ ; (r_2 < 2^{n-1})$$

o,

Si $~;~ 2^{n-3} \le r < 2^{n-2}$,
$$r_1=2^{n-2}+r_2 \implica c = 2^n +0 \cdot 2^{n-1}+ 2^{n-2} +r_2 ~~~ ; (r_2 < 2^{n-2})\ \\\text{etc} \\. \\.$$

El resultado de la división entera nos da la siguiente dígito y así sucesivamente.

Siguiendo el proceso hasta que $n=0$, es fácil ver que recuperar el (único) de la representación de $c$ base $2$.

Este algoritmo, en general puede ser aplicado para mostrar que cada número puede ser definitivamente y únicamente representado en cualquier base $b > 1$.

Answer 2

Un número entero es par o impar. Un número puede ser exactamente dividido por dos. Un número impar incluso puede deducir una unidad. El uso de estas dos reglas, usted puede reducir cualquier entero a cero en un número finito de pasos, porque todos dan valores más pequeños.

Seguimiento de la reducción de atrás, es una cuestión fácil de demostrar que el número inicial es una suma de potencias (incremento de todos los exponentes, haciéndolos $>0$ y posiblemente añadir $2^0$).

E. g.

$$27\to26\to13\to12\to6\to3\to2\to1$$

$$2^0\to2^1\to2^1+2^0\to2^2+2^1\to2^3+2^2\to2^3+2^2+2^0\to2^4+2^3+2^1\\\to2^4+2^3+2^1+2^0$$

Answer 3

Voy a probar esto por inducción.

Reclamo: Cada número $n$ puede ser representado como la suma de un finito número de potencias de dos, donde cada potencia de dos es que no se repitió más de una vez. En otras palabras:

$n = \sum_{i=0}^{k}{a_i \cdot 2^i}$ para algunos finito $k$ donde $a_i = 0$ o $a_i = 1$ todos los $0 \le i \le k$

Prueba por inducción sobre $n$:

Base: $0 = \sum_{i=0}^{0}{a_i \cdot 2^i}$$a_0 = 0$!

Paso: Supongamos que para algunos arbitraria $n$: $n = \sum_{i=0}^{k}{a_i \cdot 2^i}$ para algunos finito $k$ donde $a_i = 0$ o $a_i = 1$ todos los $0 \le i \le k$

A continuación, se sostiene también que $n = \sum_{i=0}^{k+1}{a_i \cdot 2^i}$ para algunos finito $k$ donde $a_i = 0$ o $a_i = 1$ todos los $0 \le i \le k$ $a_{k+1} = 0$

Ahora vamos a considerar $n + 1$:

Deje $j = min \{ 0 \le i \le k+1 |a_i = 0\}$

Ahora definir:

• $a_i' = 0$ todos los $0 \le i \le j-1$
• $a_j' = 1$
• $a_i' = a_i$ todos los $j+1 \le i \le k+1$

Así tenemos que para algunos finito $k$ donde $a_i = 0$ o $a_i = 1$ todos los $0 \le i \le k + 1$:

$$\sum_{i=0}^{k+1}{a_i' \cdot 2^i} =$$

$$ \sum_{i=0}^{j-1}{a_i' \cdot 2^i} + a_j'\cdot2^j + \sum_{i={j+1}}^{k+1}{a_i' \cdot 2^i} =$$

(por la definición de $a_i'$)

$$ \sum_{i=0}^{j-1}{0 \cdot 2^i} + 1\cdot2^j +\sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} =$$

$$ 0 + 2^j +\sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} =$$

$$ 2^j +\sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} =$$

$$ 2^j - 1 + 1 + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} =$$

$$ \sum_{i=0}^{j-1}{2^i} + 1 + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} = $$

$$ \sum_{i=0}^{j-1}{1 \cdot 2^i} + 1 + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} = $$

(desde $a_i = 1$ todos los $0 \le i \le j-1$)

$$\sum_{i=0}^{j-1}{a_i \cdot 2^i} + 0 + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} + 1 =$$

$$ \sum_{i=0}^{j-1}{a_i \cdot 2^i} + 0\cdot 2^j + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} + 1 = $$

$$\sum_{i=0}^{j-1}{a_i \cdot 2^i} + a_j \cdot 2^j + \sum_{i={j+1}}^{k+1}{a_i \cdot 2^i} + 1 = $$

$$\sum_{i=0}^{j-1}{a_i \cdot 2^i} + \sum_{i={j}}^{k+1}{a_i \cdot 2^i} + 1 =$$

$$ \sum_{i=0}^{k+1}{a_i \cdot 2^i} + 1 =$$

$$ n + 1$$ Cheque!

Answer 4

Si te refieres a los números enteros se desprende el algoritmo de Euclides.

Usted sólo necesita ver que $$\sum_{n=0}^{p-1}2^n=2^p-1$$

y es inmediatamente claro que la diferencia entre una potencia de $2$ y la suma de todos los de abajo siempre es $1$ y por lo tanto no puede haber números enteros en el medio.