Fuerte Inducción de la Prueba: Cada número natural = suma de las distintas potencias de 2

Question

La pregunta que yo estoy mirando, es mostrar que cada entero positivo $n$ puede ser escrita como una suma de distintas potencias de dos.

Puedo ver que usted puede formar cualquier número basado en el más alto $2^t$ que es menor que el número, además de una combinación de $2^j<n$'s. Y que puede hacer que el número impar, mediante la adición de $2^0$ al final.

Yo no sé cómo crear la fórmula para la prueba. Estoy tratando de encontrar mi caso base, y luego mi inductivo fórmula para averiguar $k+1$, y no tengo nada.

Answer 1

La declaración es obviamente cierto para $n=0$.

Suponga que se nos da una $n\geq1$ y eso es cierto para todos los $m$$0\leq m<n$.

Al $n=2m$ $m<n$ y, por tanto, $m=\sum_k 2^{p_k}$ con un número finito de $p_k$, todos ellos diferentes. De ello se desprende que $n=\sum_k 2^{p_k+1}$ todos $p_k+1$ diferente.

Al $n=2m+1$ $m$ como antes, a continuación, $n=2^0+\sum_k 2^{p_k+1}$ todos $p_k+1$ diferente y diferente de $0$.

Answer 2

Encontrar este tipo de representación es equivalente a la expresión de las $n$ en binario. Podemos hacer la inducción de la siguiente manera: Vamos a $2^h$ ser el más alto poder de $2$ menos que o igual a$n.$, Entonces debemos tener $n-2^{h}< 2^{h+1} - 2^{h}=2^{h}(2-1)=2^{h}.$ por lo tanto la mayor potencia, de decir $2^{g},$ $2$ tal que $2^{g}\le n-2^{h}$ debe satisfacer $g<h.$ Por la fuerte inducción en $h$ podemos asumir que $n-2^{h} = \sum_{i=0}^{h-1}c_i2^i$ donde cada una de las $c_i$ es $0$ o $1.$ Pero luego hemos terminado, ya que esto implica $n= \sum_{i=0}^{h-1}c_i2^i + 2^h$ es una suma de diferentes poderes de $2.$

Para ser explícitos, vamos a incluir la hipótesis de inducción. Es decir, para $h=0$ positivo $n\le 2^h=2^0=1$ se puede expresar como una potencia de $2,$, ya que la única posibilidad es $1=2^0.$ por Lo que suponemos que para un determinado $h>0$ y cualquier $n\le2^h,$ que este tipo de representación existe.