Demostrar por inducción. ¿Cómo probar $\sum_{i=0}^n2^i=2^{n+1}-1$ con la inducción?

Question

$\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$.

No entiendo la inducción que podría utilizar algo de ayuda.

Answer 1

El caso base es el cálculo de $2^0=2-1$. Suponga $\sum_{i=0} ^{n-1} 2^i=2^n-1$ (esta es la inducción de paso). La adición de $2^n$ a ambos lados, se obtiene:

$$\sum_{i=0} ^{n} 2^i=2^n-1+2^n=2\cdot2^n-1=2^{n+1}-1,$$

el cierre de la inducción y el acabado de la prueba.

Un enfoque combinatorio del problema es como sigue. El número total de subconjuntos de un conjunto de tamaño $n$$2^{n}$. Deje $N_i=\{1,2,...,i\}$. A continuación, el número total de subconjuntos de a$N_{j-1}$$2^{j-1}$. Todos los elementos de cada subconjunto de $N_{j-1}$ es de menos de $j$, por lo que la colocación de $j$ a cada uno de estos subconjuntos se crea una lista exhaustiva de los subconjuntos de a $N$ han $j$ es el mayor elemento.

Como antes, el número total de subconjuntos no vacíos de a$N=\{1,2,...,n+1\}$$2^{n+1}-1$, ya que estamos tomando es el conjunto vacío. Otra manera de contar esto es para contar el número de subconjuntos de a $N$ $j$ es el mayor elemento. Podemos partición $P(N)\setminus \emptyset$ donde $P(X)$ denota el poder conjunto de $X$, como sigue: vaya a $X_i$ denota el conjunto de los subconjuntos de a $N$ han $i$ como mayor elemento. A continuación,$P(N)\setminus \emptyset=\bigcup_{i=1} ^{n+1} X_i$, lo que implica:

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

Answer 2

Primero comprobemos el caso base es decir $n=0$. $$\sum_{i=0}^02^i=2^0=1$ $ $$2^{0+1}-1=1$ $, Por tanto, la afirmación es cierta para $n=0$.

---

Ahora Supongamos que la declaración es verdad $n$: $\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$. Debemos demostrar que también es cierto para $n+1$: $$\sum_{i=0}^{n+1}2^i=\sum_{i=0}^{n}2^i+2^{n+1}=2^{n+1}-1+2^{n+1}=2\cdot2^{n+1}-1=2^{n+2}-1 \ \Box $ $

---

Así que (i) la afirmación es cierta para $n=0$; y (ii) si la afirmación es cierta para $n$, entonces también es verdad $n+1$. Por lo tanto, por inducción, es cierto para todas las $n \ge 0$.

Answer 3

El objetivo con la inducción matemática para demostrar que la hipótesis de la verdad para el caso base y, a continuación, mostrar que si que tiene de arbitraria en el caso (normalmente llamado $k$), también se mantiene para el siguiente caso ($k+1$).

Para su problema, en nuestro caso base se produce cuando $n = 0$.

$$\sum\limits_{i=0}^{0} 2^i = 2^0 = 1 = 2^1 - 1$$

Entonces, suponemos que para algunos $k \geq 0$, el siguiente se tiene:

$$\sum\limits_{i=0}^{k} 2^i = 2^{k+1} - 1$$

Ahora, si podemos demostrar que este ser verdadero implica que la hipótesis tiene también para el $(k+1)$th caso, la hipótesis que se debe mantener para todos los enteros positivos. Así tenemos

$$\sum\limits_{i=0}^{k+1} 2^i = \sum\limits_{i=0}^{k} 2^i + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1} = 2 \cdot 2^{k+1} - 1 = 2^{(k+1) + 1} - 1.$$

Por lo tanto, la hipótesis que se tiene para todos los $n \geq 0$.