Demostrando $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ todos los $n\geq 1$ por inducción

Question

Estoy practicando las pruebas por inducción, y las igualdades parecen ser los más difíciles para mí. Puede alguien por favor ayuda a demostrar que para todos los enteros $n \geq 1$: $$ 2^n -1 = \sum \límites de _{i=0} ^{n-1} 2^i\;? $$

Answer 1

Para $n\geq 1$, vamos a $S(n)$ denotar la declaración de $$ S(n) : \sum_{i=0} ^{n-1} 2^i=2^n-1. $$ Caso Base ($n=1$): $S(1)$ dice que $\sum_{i=0}^{1-1}2^i = 2^0=1=2^1-1$, y esto es cierto.

Inductivo paso: Revisión de algunos $k\geq 1$ y asumir que $S(k)$ es cierto cuando $$ S(k) : \sum_{i=0} ^{k-1} 2^i=2^k-1. $$ Para ser mostrado es que $S(k+1)$ sigue donde $$ S(k+1) : \sum_{i=0} ^{k} 2^i=2^{k+1}-1 $$ Comenzando con el lado izquierdo de $S(k+1)$, \begin{align} \sum_{i=0}^k 2^i &= 2^k+\sum_{i=0}^{k-1}2^i\tag{by defn. of %#%#%}\\[0.5em] &= 2^k+(2^k-1)\tag{by induction hypothesis}\\[0.5em] &= 2\cdot 2^k-1\tag{simplify}\\[0.5em] &=2^{k+1}-1,\tag{desired expression} \end{align} terminamos en el lado derecho de la $\Sigma$, completando así el paso inductivo.

Por inducción matemática, la declaración de $S(k+1)$ es cierto para todos los $S(n)$.

Answer 2

Detallado o ligeramente rigurosa prueba:

Tenemos que demostrar que el conjunto $$S = \{k\in \mathbb{N} : 2^k -1 = \sum_{i=0}^{k-1} 2^i \} = \mathbb{N}.$$ Con el fin de hacer eso, vamos a comprobar que $ S \subset \mathbb{N}$$\mathbb{N} \subset S$, de manera que obtenemos $S = \mathbb{N}$.

Primera parte: $S \subset \mathbb{N}$:

Por la definición del conjunto S, es claro que $S \subset \mathbb{N}$, debido a $k \in S \Rightarrow k \in \mathbb{N}. \,\,\,\,\,\square$

Segunda parte: $\mathbb{N} \subset S$.

Vamos a mostrar que el $k \in \mathbb{N} \Rightarrow k \in S$.

Para lograrlo, debemos demostrar $1 \in S$, e $j \in S \Rightarrow j+1 \in S$.

• $1 \in S$:

$2^1 - 1 = 1$ $1 \in \mathbb{N}$ conduce a $1 \in S$

• $j \in S \Rightarrow j+1 \in S$

Nuestra hipótesis es que el $j \in S$, y tenemos que demostrar que, si la hipótesis es verdadera, entonces la conclusión también es verdadera. Tenga en cuenta que no estamos demostrando que la hipótesis ES verdadera, estamos a sólo muestra que la hipótesis que se GARANTIZA la conclusión (esto me confunde mucho cuando yo estaba aprendiendo de la inducción).

Procedimiento, este paso se llama el paso de inducción: Comenzando con $j \in S$, tenemos (que se supone verdadero) de la proposición: $$ 2^{j} - 1 = \sum_{i=0}^{j-1}2^i$$

Por definición de suma, podemos escribir:

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

Sin embargo, puesto que estamos suponiendo que por el bien del argumento que $ 2^{j} - 1 = \sum_{i=0}^{j-1}2^i$ entonces podemos sustituir en $2^{j}- 1$ en la fórmula que acabamos de llegar, lo que conduce a:

$$ \sum_{i=0}^{j}2^i = (2^j -1)+ 2^{j}$$

Que podemos simplificar a dar:

$$ \sum_{i=0}^{j}2^i = 2(2^j) -1 = 2^{j+1} -1.$$

Así hemos demostrado que $ j \in S \Rightarrow j+1 \in S$.

Por lo tanto, si un elemento $b \in \mathbb{N}$, $b \in \mathbb{s}. \,\,\,\,\,\,$

Esto completa la prueba. $\square$

Answer 3

Paso 1: Para $n=1$, el LHS es $2^1-1=1$, mientras que el lado derecho es $\sum_{i=0}^0 2^i=0$, que son iguales.

Paso 2: Suponga que el $2^n-1=\sum_{i=0}^{n-1}2^i$ mantiene, y tratar de usar este hecho para demostrar que $2^{n+1}-1=\sum_{i=0}^n2^i$.

Answer 4

Debemos demostrar para n=1. $$2^1-1=1=2^0=\sum_{i=0}^{1}2^i$$ Ahora supongamos que es válido para $n=k$

Podemos comprobarlo por $n=k+1$ $$\sum_{i=0}^{k+1}2^i=\sum_{i=1}^{k+1}2^i+1=\sum_{i=1}^{k+1}2^i+2-1=2(\sum_{i=0}^{k}2^i+1)-1=2((2^k-1)+1)-1=2^{k+1}-1$$