¿Atrapados en la inducción, cómo salir?

Question

Ejemplo 1:

Demostrar por inducción que $1+3+5+...+(2n-1)=n^2 \text{ for all } n \in \mathbb{N}....(*)$

Prueba:

Paso 1: Para $n=1$, del lado izquierdo tenemos $(2(1)-1) = 1$. Del lado derecho tenemos a $(1)^2 = 1$.

Paso 2: Supongamos que (*) es verdadera para algunos $n=k \in \mathbb{N}$ que es $$1+3+5+...+(2k-1)=k^2$$

Paso 3: Probar que (*) es cierto para $n=k \in \mathbb{N}$ que es (añadiendo $(2k+1)$ a ambos lados) $$1+3+5+...+(2k-1)+(2k+1)=(k)^2+(2k+1)$$

tenemos

que muestra los dos lados son iguales?

pero usted puede hacer esto a un número de problemas....

Ejemplo 2:

Demostrar por inducción que $1^3+2^3+...+n^3=(1+2+...+n)^2 \text{ for all } n \in \mathbb{N}....(*)$

Prueba:

Paso 1: Para $n=1$, del lado izquierdo tenemos $1^3 = 1$. Del lado derecho tenemos a $(1)^2 = 1$. Que muestra ambos lados son verdaderas.

Paso 2: Supongamos que (*) es verdadera para algunos $n=k \in \mathbb{N}$ que es $$1^3+2^3+...+k^3=(1+2+...+k)^2$$

Paso 3: Probar que (*) es cierto para $n=k \in \mathbb{N}$ que es (añadiendo $(k+1)^3$ a ambos lados) $$1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k)^2 + (k+1)^3$$

tenemos

que muestra los dos lados son iguales otra vez...

¿qué estoy fundamentalmente haciendo mal?

Answer 1

El problema es que utiliza muchas veces el paso 2:

Voy a explicar para el primer ejemplo:

Para saber que $$1+3+\ldots +(2k-1)=k^2$$ . Now add $2 k +1$ (como hiciste):

$$1+3+\ldots+(2k-1)+(2k+1)=k^2+2k+1$ $ Esto ya es cierto porque se la supone. No necesita demostrarlo. Lo que usted necesita para realmente probar es que: $$1+3+\ldots+(2k+1)=(k+1)^2$$ for the inductive step to follow . But you already known that the sum is $k ^ 2 +2 k +1$ así que todos necesita demostrar que es:

%#% $ #% que debería ser obvio.

Answer 2

En el Paso 3 del segundo ejemplo, puede escribir "Demostrar que (*) es cierto para $n = k \in N$", pero que debería ser $n = k + 1$.

Me parece útil en pruebas como esta para escribir algo que me llame a $P(n)$, la proposición de que quiero demostrar, que normalmente está destinado a ser verdadera para todo entero $n$. En el ejemplo 3, $P(n)$ es la declaración de

$$ 1^3+2^3+...+n^3=(1+2+...+n)^2 $$ Eso significa que $P(1)$ es la declaración de $$ 1^3=(1)^2 $$ y $P(2)$ es la declaración de $$ 1^3 + 2^3=(1+2)^2 $$ y así sucesivamente.

Ahora usted puede decir esto:

Voy a suponer que para algunos $k \in \mathbb N$, $P(k)$ es cierto, es decir, que $$ 1^3+2^3+...+k^3=(1+2+...+k)^2 $$ Y mediante manipulación algebraica, voy a usar este para establecer que $P(k+1)$ es verdadera, es decir, que $$ 1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k + (k+1))^2. $$

Ahora usted tiene un punto de partida y una meta clara.

Yo diría que, en este punto:

A partir de la hipótesis, hemos $$ 1^3+2^3+...+k^3=(1+2+...+k)^2 $$ La adición de $(k+1)^3$ a cada lado, obtenemos $$ 1^3+2^3+...+k^3+ (k+1)^3=(1+2+...+k)^2 + (k+1)^3 $$ Para finalizar la prueba, tenemos que demostrar que el lado derecho es el mismo que $(1 + 2 + \ldots + (k+1))^2$. Para ello, veamos la diferencia entre estos dos, \begin{align} S &= (1+2+...+k)^2 + (k+1)^3 - ((1+2+...+k+(k+1))^2) \end{align} Si podemos mostrar a $S = 0$, hemos terminado. Bien, \begin{align} S &= (1+2+...+k)^2 + (k+1)^3 - ((1+2+...+k+(k+1))^2)\\ &= (1+2+...+k)^2 - (1+2+...+k+(k+1))^2 + (k+1)^3 \end{align} Los primeros dos términos parecen a $A^2 - B^2 = (A-B)(A+B)$, por lo que \begin{align} S &= (1 + 2 + \ldots + k)^2 - (1 + 2 + \ldots + k+(k+1))^2 + (k+1)^3 \\ &= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k+(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3 \\ &= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k +(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3 \\ &= -(k+1)\cdot(2 (1 + 2 + \ldots + k) + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot(2 \frac{k(k+1)}{2} + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( k(k+1) + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( k(k+1) + 1\cdot(k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( (k+1)(k+1) ) + (k+1)^3 \\ &= -(k+1)^3 + (k+1)^3 \\ &= 0. \end{align}

Answer 3

¿Qué estoy fundamentalmente haciendo mal?

En realidad sólo hay una cosa que puedo decir que están haciendo mal, pero no es tan trivial. Supongamos que su declaración de demostrar que es $S(n)$; el inductivo hipótesis se $S(k)$ (donde se supone que para ser cierto para algunos fijos $k\geq ?$), y luego va a estar tratando de mostrar que $S(k)\to S(k+1)$, donde trabaja desde el lado izquierdo de $S(k+1)$ a el lado derecho de la $S(k+1)$. El problema es que usted no está trabajando para el lado derecho de la $S(k+1)$. Simplemente tirar en tu extra sumando en ambos ejemplos, pero en realidad no trabajo hacia persuadir al lado derecho de la $S(k+1)$ fuera de la parte izquierda de $S(k+1)$. Para ilustrar específicamente de qué estoy hablando, te voy a mostrar a través de su primer ejemplo (lo mismo se aplica para el segundo ejemplo).

---

Ejemplo 1: Aquí se están tratando de establecer que $$ S(n) : \sum_{i=1}^n(2i-1)=n^2. $$ Su hipótesis inductiva es $$ S(k) : \sum_{i=1}^k(2i-1)=k^2. $$ Ahora, usted necesita demostrar que $$ S(k+1) : \sum_{i=1}^{k+1}(2i-1)=(k+1)^2 $$ sigue de $S(k)$. Lo que están haciendo es simplemente bofetadas en la $2k+1$ plazo en la izquierda y mano derecha de $S(k+1)$. Esto no puede ser visto como técnicamente incorrecta en que se va a arruinar tu prueba, pero es muy descuidado y debe ser evitado. En una simple sumatoria problema como este, no hay mucho de un problema, pero es un mal hábito para cultivar (la mala costumbre de no ser la formulación de la perspectiva de prueba muy claramente). Aquí, claramente tenemos que $k^2+2k+1=(k+1)^2$, pero ¿qué sucede cuando se trata de algo mucho más complicado? Usted termina con un complicado innecesariamente la prueba de que es descuidado, claro, etc. Aquí es cómo me gustaría escribir tu prueba:

Reclamo: Para $n\geq 1$, vamos a $S(n)$ el valor de la proposición de $$ S(n) : \sum_{i=1}^n(2i-1)=n^2. $$

Caso Base ($n=1$): $S(1)$ dice que $2(1)-1=1=1^1$, y esto es cierto.

Inductivo paso: Supongamos que $$ S(k) : \sum_{i=1}^k(2i-1)=k^2 $$ es cierto para algunos fijos $k\geq1$. Para ser mostrado es que $$ S(k+1) : \sum_{i=1}^{k+1}(2i-1)=(k+1)^2 $$ de la siguiente manera. Comenzando con el lado izquierdo de $S(k+1)$, \begin{align} \sum_{i=1}^{k+1}(2i-1)&= \sum_{i=1}^k(2i-1)+2(k+1)-1\tag{by %#%#%-defn.}\\[0.5em] &= k^2+(2k+1)\tag{by %#%#%}\\[0.5em] &= (k+1)^2\tag{factor} \end{align} terminamos en el lado derecho de la $\Sigma$, completando el paso inductivo.

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

---

Finalmente, usted puede encontrar este post útil en lo que respecta a la escritura clara inducción de las pruebas.