Prueba de redacción: cómo escribir una clara inducción de la prueba?

Question

¿Qué es una eficaz manera de escribir de la inducción de las pruebas?

Esencialmente, hay buenos ejemplos o plantillas de inducción de pruebas que pueden ser útiles (para los principiantes, no-inglés-nativo de los estudiantes, etc.)?

Para guiar a los lectores, por favor indique si su respuesta asas:

• Caso 1: una simple inducción $(P_n \implies P_{n+1}$), o
• Caso 2: una fuerte inducción ($P_1,\ldots,P_n \implies P_{n+1}$), o
• Caso 3: una más exóticos de la inducción (por ejemplo,$\Bbb Q$$|p|+q$).

PS: he visto a muchos de inducción de preguntas relacionadas, y muy a menudo el problema se encuentra con el OP de la falta de una metodología adecuada (o estilo) en la escritura de la prueba, mientras que la respuesta se centra en el caso particular de que el OP pregunta. La cuestión de estilo es obviamente subjetiva, pero a mí me parece que el "arte" de escribir buenas pruebas es casi tan importante como la comprensión de los conceptos subyacentes, por lo que el asesoramiento sobre la forma correcta de la prueba de escritura de prácticas debe caer dentro del ámbito de aplicación del MSE (en virtud de la proof-writing tag).

Answer 1

Comentarios iniciales: Esta es una excelente pregunta, en mi opinión, y es justo lo que el proof-writing etiqueta. Por desgracia, a menudo hay muchos problemas que aquejan a los principiantes cuando se trata de la inducción de las pruebas:

• ¿Por qué la inducción es una prueba válida de la técnica debe ser entendido desde el principio, y esto es raramente el caso.
• Menos relevante en la escuela secundaria o de bachillerato, pero sin duda importante sobre el MSE--se espera que sean capaces de componer sus cálculos correctamente. A menudo, esto significa tomar el tiempo para aprender algunos MathJax, ${\rm\LaTeX}$, o un híbrido de estos, algo que requiere un poco de tiempo.
• Con el fin de ser capaz de comunicarse de una prueba de manera efectiva, debe necesariamente comprender cómo escribir bien, un talento que a menudo infravalorados y subdesarrollados, entre los matemáticos.

La lista podría seguir y seguir, pero estos son algunos de los puntos más salientes. Dicho esto, voy a proporcionar una plantilla para escribir bonito, pulido de inducción de las pruebas y, a continuación, voy a detalle la justificación de esta plantilla, ambos adoptados de David Gunderson maravilloso libro Manual de Inducción Matemática. Más concretamente, lo que ha sido adaptado es a partir del capítulo "El escrito de MI prueba" (sí, hay todo un capítulo dedicado a cómo escribir inducción pruebas--pgs 109-119, específicamente). Por último, voy a concluir, que muestra cómo se puede utilizar esta plantilla para demostrar la declaración de $\prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}$$n\geq 2$.

---

Plantilla

Nota: En la plantilla anterior, si la prueba es por la fuerte inducción, luego de la inducción de la hipótesis debe ser reemplazado con "supongamos que para cada una de las $j, 3\leq j\leq k$, $$ \text{$S(j) : $ (escribir lo $S(j)$ dice)} $$ sostiene. También, en la secuencia de ecuaciones, en el punto donde la hipótesis de inducción es invocado, ya sea escribir "IH" o mencionar que las declaraciones de la IH se utilizan (por ejemplo, por $S(4)$$S(k)$).

---

Justificación de la Plantilla

Supongamos que una declaración en particular con respecto a $n$ es para ser probado para $n\geq 3$.

1. Definir la declaración de que tiene que ser demostrado. Por ejemplo: "para cada una de las $n\geq 3$, vamos a $S(n)$ ser la declaración de $\ldots$". Si hay más de una variable, tenga cuidado de cuantificación; por ejemplo, la expresión $$ \text{Para cada una de las $n\geq 3$ deje $S(n)$ ser la afirmación de que para todos los $m\leq n$ $\ldots$} $$ es diferente de $$ \text{Para cada una de las $n\geq 3$ y todos los $m\leq n$, vamos a $S(n)$ ser la afirmación de que $\ldots$} $$ En la segunda expresión, el límite inferior de $m$, no se declara, y no está claro si o no $S(n)$ depende del valor de $m$, así que tal vez algo como $$ \text{Para cada una de las $n\geq 3$ y cada una de las $m$ satisfacción $1\leq m\leq n$, vamos a $S(m,n)$ ser la declaración de $\ldots$} $$ es mejor. Puede ayudar también a identificar con anticipación para que las variables de una frase en particular que incluso tiene sentido, más adelante restricción de la variable para los casos que están siendo probados.

2. Indique el rango de $n$ para que la declaración es para ser probado. Por ejemplo:
   "Se ha demostrado es que para cada entero $n\geq 3$, la declaración de $S(n)$ es verdadero".

3. Base paso: Escribir las palabras "Base paso" y compruebe que el caso base es verdadero (dar razones si es que no es trivial). Por ejemplo:
   Base paso: $S(3)$ dice $\ldots$, lo cual es cierto.

4. Inductivo paso: Escribir las palabras "paso Inductivo:"

5. Estado de la hipótesis inductiva. Por simple inducción matemática, esto se lee como: Para algunos fijos $k\geq 3$, suponga que $S(k)$ es cierto. [Escribir precisamente lo $S(k)$ dice que es generalmente una excelente idea.] Para el fuerte de inducción, esto va a leer algo como: "Para algunos fijos $k\geq 3$, suponga que $S(3), S(4), \ldots, S(k)$ son todas verdaderas" o "Para algunos fijos $k\geq 3$, asumen que para $3\leq j\leq k, S(j)$ es verdadero". En el etiquetado de la hipótesis inductiva con las palabras "hipótesis inductiva" (o "IH") es a menudo una práctica útil para el principiante.

6. El estado lo que tiene que ser demostrado, a saber,$S(k+1)$. Es altamente recomendable que uno escribe $S(k+1)$ específicamente por lo que uno ve la forma requerida de la conclusión en el paso inductivo.

7. Demostrar $S(k+1)$. Si $S(n)$ es una igualdad (o desigualdad), es mejor empezar con uno de los lados de $S(k+1)$, y a través de una secuencia de iguala (o desigualdades), se derivan el otro lado. En el punto donde la hipótesis inductiva se utiliza, esto debe ser mencionado como un comentario "por $S(k)$", "por hipótesis de inducción", o incluso poniendo las iniciales "IH" a través de los pertinentes signo igual.

8. Mención cuando el paso inductivo se hace. Por ejemplo, podría escribir "$\ldots$ completar el paso inductivo $S(k)\to S(k+1)$.", o, simplemente, "Esto completa el paso inductivo."

9. Estado a la conclusión: "por lo Tanto, por inducción matemática, para todos los $n\geq 3, S(n)$ es cierto. $\Box$", utilizando el símbolo "$\Box$" para indicar que la totalidad de la prueba es completa (este símbolo es aún más abreviada para QED; más información sobre esto se puede encontrar aquí). Algunos de los matemáticos prefieren para cuantificar las variables antes de utilizarlas, como en "$\ldots$ todos los $n\geq 3, S(n)$ es verdadero". Esta es una buena práctica, como se lee de forma más lógica; sin embargo, recuerde insertar una coma (, porque "$n\geq 3\, S(n)$" podría ser sin sentido) adicional o una frase como"$\ldots$$n\geq 3$, la declaración de $S(n)$ sostiene."

Sorprendentemente, en un intento de simplemente memorizar el formato de una prueba inductiva, a menudo los estudiantes descubrir lo que estaba mal con sus formatos anteriores. La novedad de la plantilla es que las fuerzas de los estudiantes, más o menos, a comprender sus propias inductivo de las pruebas.

---

El uso de la Plantilla

Problema: Demostrar que para todos los $n\geq 2, \prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}$.

Solución: Para cualquier entero $n\geq 2$, vamos a $S(n)$ denotar la declaración de $$ S(n) : \prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}. $$

Base step ($n=2$): $S(2)$ says $\prod_{i=2}^2\left(1-\frac{1}{i}\right)=\frac{1}{2}$, and this is true because $$\prod_{i=2}^2\left(1-\frac{1}{i}\right)=1-\frac{1}{2}=\frac{1}{2}.$$

Inductive step $S(k)\S(k+1)$: Fix some $k\geq 2$. Suponga que $$ S(k) : \prod_{i=2}^k\left(1-\frac{1}{i}\right)=\frac{1}{k} $$ sostiene. Se ha demostrado es que $$ S(k+1) : \prod_{i=2}^{k+1}\left(1-\frac{1}{i}\right)=\frac{1}{k+1} $$ de la siguiente manera. Comenzando con el lado izquierdo de $S(k+1)$, \begin{align} \prod_{i=2}^{k+1}\left(1-\frac{1}{i}\right) &= \left[\prod_{i=2}^k\left(1-\frac{1}{i}\right)\right]\left(1-\frac{1}{k+1}\right)\tag{by defn. of %#%#%}\\[1em] &= \frac{1}{k}\left(1-\frac{1}{k+1}\right)\tag{by %#%#%, the ind. hyp.}\\[1em] &= \frac{1}{k}\left(\frac{k+1-1}{k+1}\right)\tag{common denom.}\\[1em] &= \frac{1}{k}\cdot\frac{k}{k+1}\tag{simplify}\\[1em] &= \frac{1}{k+1},\tag{simplify further} \end{align} uno llega al lado derecho de la $\Pi$, demostrando $S(k)$ también es cierto, completando el paso inductivo.

Conclusión: Por inducción matemática, se demuestra que para todos los $S(k+1)$, la declaración de $S(k+1)$ es cierto. $n\geq 2$

Answer 2

Aquí está mi plantilla para el caso $1$%:

Como ejemplo, vamos a demostrar por inducción que $\sum\limits_{k=0}^{n-1}2\cdot3^k=3^n-1$.

---

En primer lugar, demostrar que esto es cierto para $n=1$:

$\sum\limits_{k=0}^{1-1}2\cdot3^k=3^1-1$

Segundo, se supone que esto es cierto para $n$:

$\sum\limits_{k=0}^{n-1}2\cdot3^k=3^n-1$

Tercero, demostrar que esto es cierto para $n+1$:

$\sum\limits_{k=0}^{n}2\cdot3^k=$

$\color{red}{\sum\limits_{k=0}^{n-1}2\cdot3^k}+2\cdot3^n=$

$\color{red}{3^n-1}+2\cdot3^n=$

$3\cdot3^n-1=$

$3^{n+1}-1$

Por favor, tenga en cuenta que la hipótesis se utiliza sólo en la parte marcada con rojo.

Answer 3

Esta es una respuesta que cubre un poco más exóticos de la prueba. La demanda es uno de los que he usado en mi respuesta a probar o refutar $H$ es un subgrupo , pero voy a ampliar los detalles aquí y escribir tan bien como sea posible.
Para más información sobre la inducción puede ser hecho en estos más exóticos ejemplos, ver mi blog http://math.blogoverflow.com/2015/03/10/when-can-we-do-induction/.

Reclamo: Vamos a $A\subseteq \mathbb{Z}$ ser el más pequeño subconjunto que contiene $1$ y cerrado bajo la operación $(n,m)\mapsto -(n+m)$.
A continuación,$A = \{ n\in \mathbb{Z}\mid n\equiv 1\pmod{3}\}$.

Prueba de reclamación: Vamos a $B = \{ n\in \mathbb{Z}\mid n\equiv 1\pmod{3}\}$. En primer lugar, nos muestran que la $A\subseteq B$ (esta parte no hace uso de la inducción, pero voy a incluir para la integridad), que, por definición, significa que tenemos que mostrar que $1\in B$ y que para cualquier $n,m\in B$ tenemos $-(n+m)\in B$. La primera parte es trivialmente cierto, y para el segundo, se nota que si $n\equiv m\equiv 1\pmod{3}$ $n+m\equiv 2\pmod{3}$ e lo $-(m+n)\equiv -2 \equiv 1\pmod{3}$, que fue la segunda parte.

Para mostrar que $B\subseteq A$ nos gustaría proceder por inducción, con la bien fundada de pedido "está más cerca de a $0$" (más precisamente, podemos decir que $x\leq y$ si $x = y$ o $|x| < |y|$). Que este orden es, de hecho, bien fundada voy a dejar como un ejercicio, ya que se trata de la inducción de la prueba que es importante aquí.

Para $n\in \mathbb{Z}$ definimos la declaración de $P_n =$ "$n\in A$", y nos gustaría mostrar que $P_n$ es cierto para todos los $n\in B$. Tenga en cuenta que la suposición sobre la $A$, ahora se traduce a$P_1$$P_m\wedge P_n\implies P_{-(m+n)}$.

Deje $n\in B$ y asumir que $P_m$ es cierto para todos los $m < n$ (en el orden definido anteriormente).
Lo primero que tendrá que lidiar con la $n=1$ de los casos, ya que no hay elementos más pequeños en $B$. Pero $P_1$ es cierto por supuesto, así que esto está claro.
Nos dividimos en dos casos, dependiendo de si $n$ es positivo o negativo.
Si $n$ es negativa, entonces la $-n - 1 < n$ (en el orden en que se está utilizando). Así que por la hipótesis de inducción, $-n-1\in A$ desde $-n-1\in B$. Pero $n = -((-n - 1) + 1)$, por lo que desde ambos $P_{-n-1}$ $P_1$ son verdaderas, también tenemos $P_n$ (por la definición de $A$).

Ahora, si $n$ es positivo,$-n + 2 < n$, de modo que por la hipótesis de inducción tenemos $-n + 2 \in A$. Pero hemos visto antes que $-2\in A$ desde $-2$ es negativo y en $B$. Así que tenemos tanto en $P_{-n+2}$ $P_2$ y desde $n = -((-n+2) + -2)$ esto demuestra que tenemos $P_n$, lo que termina la prueba.

Answer 4

Una propuesta para el caso 1 (simple inducción):

Aquí están algunas recomendaciones genéricas para los principiantes que he dado en respuestas anteriores (aquí o aquí):

• Anote en toda la longitud de la declaración de $P_n$ a ser probado en el rango de $n$, y el rango de valores de $n$ más que $P_n$ debería estar de pie
• Marque claramente los anclajes de la inducción de la prueba: caso base, el paso inductivo, conclusión

Vamos a demostrar que $\forall q \in \Bbb C - \{1\}$, $1+q+\cdots+q^n = \tfrac{1-q^{n+1}}{1-q}$.

1. Empezamos por la fijación de $q \in \Bbb C- \{1\}$.

2. Para $n \in \Bbb N$, podemos definir la declaración de $\displaystyle P_n\;:\; \sum_{k=0}^{n} q^k = \tfrac{1-q^{n+1}}{1-q}$.

3. Caso Base: si $n=0$, el lado izquierdo plazo (LHS) en $P_0$ sólo tiene plazo igual a $1$, y el lado derecho es igual a $\tfrac{1-q}{1-q} = 1$. Así pues, hemos probado que $P_0$ es cierto.

4. Inductivo paso: vamos a $n$ ser un número entero mayor que $1$, y vamos a suponer que $P_{n-1}$ es cierto. Entonces: $$\begin{align} \sum_{k=0}^{n} q^k & = \sum_{k=0}^{n-1} q^k + q^n \quad & \text{(by definition)}\\ & = \color{red}{\tfrac{1-q^n}{1-q}} + q^n & \color{red}{\text{(since %#%#% is assumed to be true)}} \\ & = \frac{1-q^n + q^n(1-q)}{1-q} = \frac{1-q^{n+1}}{1-q} \end{align}$$ Hemos demostrado que $P_{n-1}$.

5. Conclusión: desde $P_{n-1} \implies P_n$ es verdadera y $P_0$, $\forall n \ge 1$, $P_{n-1} \implies P_n$ tiene para todos los $P_n$. QED

Answer 5

Un (canónica, si no es emocionante) propuesta para el caso 2 (fuerte inducción):

Vamos a probar que todo entero $\ge 2$ se puede expresar como un producto de uno o más números primos.

1. Para $n \ge 2$, podemos definir la declaración de $P_n \;:\; \forall k \in \{2,\ldots,n\}$, existe una (finito) de la secuencia de los números primos $p_{n_1}, \ldots, p_{n_k}$ como $k = p_{n_1} \ldots p_{n_k}$.

2. Caso Base: si $n=2$, $P_2$ es trivial desde $2$ es primo.

3. Inductivo paso: vamos a $n$ ser un número entero mayor que $2$ y vamos a suponer que $P_{n}$ es cierto. Entonces:

   • cualquiera de las $n+1$ es primo, y $P_{n+1}$ es trivialmente verdadera (desde $n+1=n+1$ es un producto de (uno de) primera(s) y los casos de $\le n$ son verdaderas por la hipótesis de inducción);
   • o $n+1$ es compuesto; entonces, por definición, $n+1$ puede ser expresado como $n+1 = uv$ $u,v$ enteros $>1$. Pero, a continuación, $ u,v \in \{2,\ldots,n\}$ (desde $u = (n+1)/v < n+1$) y por la inducción de la asunción, $u$ $v$ puede ser expresado como el producto de números primos: $u = p_{n^u_1}\ldots p_{n^u_u}$$v = p_{n^v_1}\ldots p_{n^v_v}$. Pero, a continuación,$n+1 = p_{n^u_1}\ldots p_{n^u_u}p_{n^v_1}\ldots p_{n^v_v}$, que es un producto de números primos, y de nuevo $P_{n+1}$ es cierto.

4. Conclusión: desde $P_2$ es verdadera y $\forall n \ge 2$, $P_n \implies P_{n+1}$, $P_n$ tiene para todos los $n \ge 2$. QED