Demostrando $\sum_{i=0}^n 2^i=2^{n+1}-1$ por inducción.

Question

En primer lugar, este es un problema de tarea, así que por favor no des la respuesta directamente. Realmente solo estoy buscando pistas y sugerencias.

Debo demostrar lo siguiente usando inducción matemática:

Para todo $n\in\mathbb{Z^+}$, $1+2+2^2+2^3+\cdots+2^n=2^{n+1}-1$.

Esto es lo que tengo en mi prueba hasta ahora:

Prueba: Sea $p\left(n\right)$ igual a $\sum_{j=0}^n 2^j=1+2+2^2+\cdots+2^n=2^{n+1}-1$. Entonces $P\left(0\right)$ es \begin{align} \sum\limits_{j=0}^0 2^j=1=2^1-1.\tag{1} \end{align} Por lo tanto, $P\left(0\right)$ es verdadero. Luego, para algún $k\in\mathbb{Z^+}$, supongamos que $P\left(k\right)$ es verdadero. Entonces \begin{align} \sum\limits_{j=0}^{k+1}2^j&=\left(\sum\limits_{j=0}^k 2^j\right)+2^{k+1}\tag{2}\\ &=2^{k+1}-1+2^{k+1}\tag{3} \\ &=2\cdot 2^{k+1}-1\tag{4}\\ &=2^{k+2}-1\tag{5}\\ &=2^{\left(k+1\right)+1}-1.\tag{6} \end{align} Por lo tanto, $P\left(n\right)$ es válido para todos los $n$.$\;\;\;\;\blacksquare$

¿Está todo correcto? Mi profesor explicó la metodología en clase bastante rápido (y tomé un poco de café de más esa noche) y quiero asegurarme de entenderlo para el examen de mañana.

Answer 1

Comentario inicial: En primer lugar, +1 por el esfuerzo. Tus preguntas casi siempre muestran mucho esfuerzo. Además, veo que estás tratando de mejorar activamente basándote en preguntas como esta, donde claramente estás tratando de implementar los consejos dados por los usuarios aquí. Eso es genial. Basado en varias de tus preguntas, al menos en las de inducción, parece que una de las principales dificultades que tienes es en escribir la demostración de manera adecuada (es decir, haciéndola clara, pulida, etc.). Por lo tanto, al final de esta publicación, te proporcionaré una plantilla para escribir demostraciones de inducción adaptada del Manual de Inducción Matemática de David Gunderson (algo me dice que realmente te gustaría este libro, por cierto). Me ayudó inmensamente cuando estaba comenzando.

---

Caso general de tu problema: Fijamos $r\in\mathbb{R}, r\neq 1$, y para $n\geq 1$, sea $S(n)$ la afirmación $$ S(n) : 1+r+r^2+\cdots+r^n=\frac{r^{n+1}-1}{r-1}.\tag{1} $$ Tu problema específico se resuelve estableciendo $r=2$ en $(1)$. De hecho, probé $(1)$ por inducción hace algún tiempo, pero no puedo encontrar esa pregunta (o bien fue eliminada o simplemente no la encuentro). De todos modos, al menos deberías saber que tu problema es realmente una instancia de un escenario más general.

---

Tu problema específico: Voy a proporcionar lo que creo que es una buena explicación para tu problema exacto (nota: solo sigue leyendo si deseas la solución completa). Mi principal razón para proporcionarlo es mostrarte cómo se vería una demostración bien escrita (en mi opinión de todos modos).

Para $n\geq 0$, sea $S(n)$ la afirmación $$ S(n) : \sum_{i=1}^n 2^i = 2^{n+1}-1. $$

Paso base ($n=0$): $S(0)$ dice que $2^0 = 2^1-1$, lo cual es cierto.

Paso de inducción ($S(k)\to S(k+1)$): Fijamos algún $k\geq 0$ y suponemos que $$ S(k) : \sum_{i=1}^k 2^i = 2^{k+1}-1 $$ es cierto. Lo que se debe demostrar es que $$ S(k+1) : \sum_{i=1}^{k+1} 2^i = 2^{k+2}-1 $$ se sigue. Comenzando con el lado izquierdo de $S(k+1)$, \begin{align} \sum_{i=1}^{k+1} 2^i &= \sum_{i=1}^k 2^i+2^{k+1}\tag{por definición de $\Sigma$}\\[0.75em] &= (2^{k+1}-1)+2^{k+1}\tag{por $S(k)$}\\[0.75em] &= 2\cdot 2^{k+1} - 1\tag{agrupar términos similares}\\[0.75em] &= 2^{k+2}-1, \end{align} vemos que se sigue el lado derecho de $S(k+1)$. Esto completa el paso inductivo.

Así, por inducción matemática, para todo $n\geq 0, S(n)$ se cumple. $\Box$

---

Plantilla: Como prometí, aquí tienes una plantilla que puedes usar de ahora en adelante que debería ayudarte enormemente a escribir demostraciones de inducción claras.

Answer 2

Su problema ya ha sido respondido en detalle. Me gustaría señalar que si desea entrenar sus habilidades inductivas, una vez que tenga una solución a su problema, aún puede explorarlo desde muchos otros ángulos, especialmente usando pruebas visuales que pueden ser bastante efectivas. Y encontrar otras pruebas. Algunas están ilustradas en Una invitación a demostraciones sin palabras. Intentaré describir dos de ellas relacionadas con su caso.

Primero, $2^k$ se puede representar en binario con solo ceros, excepto un $1$ en la posición $(k+1)^{\textrm{th}}$ desde la derecha:

 - 01: 00000001
 - 02: 00000010
 - 04: 00000100
 - 08: 00001000
 - 16: 00010000

Entonces la suma agregaría las columnas. Dado que hay exactamente un $1$, no hay acarreos, y por lo tanto se obtienen unos hasta la posición $(K+1)^{\textrm{th}}$, y el número que estás buscando es:

 - ??: 00011111

La inducción puede aparecer como: si tienes un dígito binario con unos hasta la posición $(K+1)^{\textrm{th}}$, sumar uno a eso resulta en un número con un solo uno en la posición $(K+2)^{\textrm{th}}$, por ejemplo:

 - 00011111 + 0000001 = 0010000 

Así que tu número misterioso es $2^{K+2}-1$.

La segunda prueba también se ilustra con fracciones de potencias de dos (ver la imagen en la parte superior derecha en 1/2 + 1/4 + 1/8 + 1/16 + ). Se puede observar que las potencias de dos son:

1. cuadrados puros con lados $2^k\times 2^k$
2. rectángulos de doble cuadrado con lados $2^k\times 2^{k+1}$

Aquí, puedes obtener una doble inducción, que a menudo sucede en series: una propiedad para índices impares, otra propiedad para índices pares. Las dos propiedades son:

1. la suma de potencias de dos hasta un cuadrado ($k=2K$) da el próximo rectángulo menos uno,
2. la suma de potencias de dos hasta un rectángulo ($k=2K+1$) da el próximo cuadrado menos uno,

lo cual puedes demostrar mediante inducciones alternadas.