Prueba $\sum_{i=1}^n 2^i = 2^{n+1} - 2$ utilizando la inducción fuerte

Question

Acabo de empezar a aprender pruebas por inducción en clase, pero tengo un problema que requiere pruebas por fuerte la inducción.

Este es el problema.

Demostrar por inducción fuerte: $$\sum_{i=1}^n 2^i = 2^{n+1} - 2$$

He hecho la base, mostrando que la afirmación se mantiene para $n=1$ , $n=2$ y $n=3$ . (No mostraré aquí las sencillas matemáticas). Para $n=k$ la declaración sería $2^{k+1}-2$ . Pero ahí es donde me quedo atascado, ya que todavía estoy intentando comprender el concepto de inducción fuerte.

Para $n=k+1$ ¿hago lo siguiente y lo simplifico?

$$\sum_{i=1}^{k+1} 2^i = \sum_{i=1}^k 2^i + 2^{(k+1)+1} - 2$$ $$=[2^{k+1}-2]+[2^{k+2}-2]$$ $$=\text{etc}\ldots?$$

Answer 1

Para la inducción fuerte, una prueba es algo así:

Prueba de un caso base: aquí $n= 1$ lo hará:

$2 = 4 - 2$ .

La única diferencia entre la inducción "fuerte" y la "normal" es la forma de enunciar el paso inductivo:

Suponemos que para TODOS $n_0 \leq k < n$ el teorema se cumple, y luego utilizarlo para demostrar que se cumple para $k = n$ . Esto significa que tenemos acceso a CUALQUIER número entero no negativo anterior $k$ en ese rango, no sólo "el entero anterior", $n-1$ .

En este caso, eso significa que podemos asumir el resultado para todos $1 \leq k < n$ .

Por supuesto, ya que $k = n - 1 < n$ También podemos usar ese caso.

Así que tenemos:

$\sum\limits_{i = 1}^n 2^i = \sum\limits_{i = 1}^{n-1} 2^i + 2^n = (2^n - 2) + 2^n = \dots ?$

Answer 2

Su cálculo $$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^{k}2^i+2^{(k+1)+1}-2$$ es falso. Lo que es cierto es que $$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^k2^i+2^{k+1},$$ y $2^{k+1}\neq 2^{(k+1)+1}-2$ en general. Se puede aplicar la hipótesis de inducción al primer término de la derecha para obtener lo que se desea, aunque se trata de una inducción normal, en lugar de una inducción fuerte.

Answer 3

Supongamos que $\sum_{i=1}^k 2^i = 2^{k+1} - 2 $ para todos $k < n$ .

Entonces, elija algunos $k$ con $1 < k < n$ .

$\begin{array}\\ \sum_{i=1}^n 2^i &=\sum_{i=1}^k 2^i +\sum_{i=k+1}^n 2^i\\ &=2^{k+1} - 2 +2^k\sum_{i=k+1}^n 2^{i-k}\\ &=2^{k+1} - 2 +2^k\sum_{i=1}^{n-k} 2^{i}\\ &=2^{k+1} - 2 +2^k(2^{n-k+1}-2)\\ &=2^{k+1} - 2 +2^{n+1}-2^{k+1}\\ &=2^{n+1} - 2 \\ \end{array} $

Esta es la única manera que se me ocurrió de utilizar la inducción fuerte.

Answer 4

Tenemos que demostrarlo, $$\sum_{i=1}^{n}2^{i}=2^{n+1}-2$$ Paso 1: Configuración $n=1$ en la igualdad anterior, obtenemos $$\sum_{i=1}^{1}2^{i}=2^{1+1}-2\iff 2=4-2\iff 2=2$$ por lo que se mantiene para $n=1$

Paso 2: Suponiendo que se mantiene para $n=k$ obtenemos $$\sum_{i=1}^{k}2^{i}=2^{k+1}-2$$

Paso 3: Ahora, la configuración $n=k+1$ en la igualdad dada, obtenemos $$\sum_{i=1}^{k+1}2^{i}=2^{k+1+1}-2 $$$$ \sum_{i=1}^{k}2^{i}+2^{k+1}=2^{k+2}-2 $$ $$ \sum_{i=1}^{k}2^{i}=2.2^{k+1}-2-2^{k+1} $$ $$ \sum_{i=1}^{k}2^{i}=2^{k+1}-2 $$ Which is true from (2), hence it holds for $ n=k+1$

De (1), (2) y (3) se deduce que la igualdad dada es válida para todos los enteros positivos $\color{blue}{n\geq 1}$