"Fija $k$" en la inducción matemática

Question

En la página 34, en su libro de Cálculo, Apostol da la siguiente descripción de la prueba por inducción:

Método de prueba por inducción. Deje $A(n)$ por una afirmación que involucran un número entero $n$. Llegamos a la conclusión de que $A(n)$ es verdadero para todos los $n \ge n_1$ si se pueden realizar los dos pasos siguientes:

una. Demostrar que $A(n_1)$ es cierto.
b. Deje $k$ ser arbitrario pero fijo entero $ \ge n_1 $. Suponga que $A(k)$ es verdad y demostrar que $A(k+1)$ también es cierto.

Yo no soy de nuevo a la prueba por inducción, pero no entiendo la intención detrás de $k$ "arbitrario pero fijo entero": no es necesario demostrar que, en el paso inductivo, que es el caso para todos los enteros $k \ge n_1$ que si $A(k)$ es verdadera, entonces el $A(k+1)$ es cierto?

Answer 1

Creo que eres la declaración del autor más complicado de lo que deben ser, o la lectura de "demasiado" en "arbitrario pero fijo." [Yo hubiera preferido ver la palabra "pero" se omite, porque "pero" hace que parezca que "arbitrario y fijo" están en desacuerdo en lo que significan, y que en realidad no son! Es sólo una manera de decir: "para cualquiera".]

La palabra clave es arbitraria: consideramos que, en la hipótesis inductiva, cualquier (arbitrario) integer $ \geq n_1$ y llamar a $k$. Entonces hacemos una suposición (hipótesis inductiva) acerca de $k$, que luego se mantenga fijo, de modo que en el paso inductivo, al considerar $P(k + 1)$, "$k+1$" tiene sentido: nuestra hipótesis se asume cierto para el elegido de forma arbitraria $n = k$, podemos "arreglar" lo que podemos considerar la hipótesis acerca de la $n = k+1$.

El punto de una prueba por inducción es ser capaz de decir algo, si la prueba tiene éxito, sobre todo a $n\geq n_1, n\in \mathbb N$. La prueba de $P(n)$ sí sólo necesita considerar un caso base $P(n_1)$, algunos (cualquiera) de una arbitraria entero $k\geq n_1$ de la cual asumimos $P(k)$, y luego el lo que esto significa para $P(k+1)$ donde $k+1$ es el inmediato sucesor de la que arbitrariamente elegido, luego se fija $k$.

Answer 2

$k$ es una especie de función de índice. Puede que desee probar su declaración $n_1+1, n_1+2,n_1+3,...$. El punto es que si la instrucción funciona para un número y los siguientes números, después trabaja para cada número por encima de aquél. (simplemente por reescalado $\tilde{k}=k+1$)

Answer 3

El principio de inducción dice que si $P(n)$ es una proposición acerca de un número natural $n$, y usted puede probar ambos de estos:

• $P(0)$ tiene

• Para cada número natural $k$ si $P(k)$ sostiene, a continuación, $P(k+1)$ tiene

entonces eso es suficiente para demostrar que para todos los $n$, $P(n)$ sostiene. Así que, sí, es necesario probar la segunda viñeta para todos los números naturales $k$ (a pesar de lo que ha de ser probado es sólo "si $P(k)$$P(k+1)$", que es a menudo más fáciles de tratar directamente demostrar $P(k)$).

Hay una forma estándar para demostrar que un enunciado de la forma "para todo número natural $k$, ...". Se supone que se le ha dado un fijo, pero se desconoce número natural $k$, y probar que los "..." de la parte para la que (desconocido). Que es el método que el Apóstol se refiere cuando dice:

Sea k un arbitrario pero fijo entero ≥n1. Supongamos que A(k) es verdadera y demostrar que A(k+1) también es cierto.

Por lo que este método general no es algo particular de la inducción, es simplemente el método general para la comprobación de una declaración universal. Lo que ocurre es que la segunda bala que tiene que probar a hacer una prueba por inducción es un universal de la declaración.

Answer 4

Me gustaría sugerir la siguiente explicación de la frase "arbitrario pero fijo" y a lo largo de la manera en que yo también voy a tratar de clasificar algunos de los usos de las variables.

Considere las siguientes frases:

Caso 1

1. Deje $\mathbb{N}$ ser el dominio de la variable $x$.
2. Es el caso de que $x+2=7$.

Aviso que nunca se nos ha asignado un valor a $x$. Por lo tanto, en este caso, $x$ no es realmente un "valor de la variable' sino que puede ser pensado como un espacio en blanco o un marcador de posición para el futuro valor. La única restricción que tenemos (Sentence 1) es que cada vez que asignar un valor a $x$, es ser un elemento de $\mathbb{N}$. Ya que tiene este espacio en blanco o "agujero", lógicamente, Sentence 2 es conocido como un enunciado abierto, que es, en realidad, no es afirmar nada ya que $x$ 'vacía'.

¿Cómo hacemos para 'llenar el vacío' Sentence 2 , de modo que lo que realmente hace algún tipo de reclamación? Por medio de la cuantificación; en particular, mediante el uso de la $\forall$ (para todos) y $\exists$ (existe) cuantificadores. La aplicación de estos a Sentence 2, se puede revisar la sentencia y decir

Caso 2

Para todos los $x$, es el caso de que $x+2=7$.

Aquí, estamos asignando un valor a $x$. En este caso, estamos en realidad ('de forma iterativa') asignar a cada valor de $\mathbb{N}$$x$, y es como si se está afirmando que " ${0+2=7}$ $1+2=7$ $2+2=7 \ldots$ obviamente Una declaración falsa, sino una afirmación, no obstante. El uso de la variable $x$ más que el último, de forma explícita, claramente nos ahorra un montón de escritura. Este es un ejemplo del uso de una variable como la taquigrafía.

Del mismo modo, podemos afirmar Sentence 2 como

Caso 3

Existe alguna $x$ tal que $x+2=7$.

De nuevo, estamos 'llenar el vacío', pero en este caso, sólo estamos afirmando que, al menos, un único valor de $\mathbb{N}$ $x$ puede tomar va a satisfacer la fórmula. ¿Por qué utilizar una variable en lugar de forma explícita el uso de un único valor? Así, podemos saber que es el caso que $x+2=7$ a partir de algunos antes de axioma o teorema, pero no podemos saber que el valor de $\mathbb{N}$ $x$ toma; por lo tanto, el uso de una variable. Este es un ejemplo de una variable se utiliza para un desconocido.

Ahora, consideremos nuestro caso, en el que nos gustaría probar para todos los $k$ que si $A(k)$ es verdadera, entonces el $A(k+1)$ es cierto.

Bueno, como Qiaochu Yuan señala, el uso de $k$ con una cuantificación universal para referirse a todos los de $\mathbb{N}$ colectivamente, nos obligaría varias veces decir cosas tales como "para todos los $k$ ..." a lo largo de nuestra prueba; es bastante doloroso para decir lo menos. También podemos, fallaciously, intento de formular nuestra prueba de la siguiente manera:

Deje $k$ ser una variable sobre el dominio $\mathbb{N}$.

"Proceder a probar que si A(k) es verdadera, entonces(k+1) también es cierto."

Este enfoque evidentemente no, ya que estamos dejando $k$ 'abrir'.

Cómo podemos construir una lógica válida, pero claro la prueba? Elegimos un único elemento de $\mathbb{N}$ y llevar a cabo la prueba de este elemento que muestra que si la aserción $A$ es válido para este elemento, entonces es cierto para la 'next' elemento así. Para completar nuestra prueba para todos los $\mathbb{N}$ , (implícitamente) extrapolar nuestra prueba para el resto de los números naturales. Con este fin, la hora de seleccionar el número en el que se ejecuta la prueba, hacemos una elección arbitraria y prefieren dejar el número anónimo. Esto pone de relieve el hecho de que nada acerca de nuestra prueba depende de las particularidades de un número específico, más bien todo lo que se supone acerca de nuestro número es el hecho de que es un miembro de $\mathbb{N}$. Esto hace que sea fácil para nosotros ver que la prueba puede ser extendido a todos los demás números naturales. ¿Cómo podemos 'anónimo' nuestra elección en $\mathbb{N}$? Mediante el uso de una variable como Apostol del

Caso 4

Deje $k$ ser arbitrario pero fijo entero $\ge n_1$.

Este es un ejemplo de una variable se utiliza para el 'arbitraje' y 'anonimato'.

Ahora, en este último caso, donde se realiza una elección arbitraria de $k$ $\mathbb{N}$ para nuestra prueba, uno puede malinterpretar nuestro enfoque de la siguiente manera: ya que creemos que nuestra prueba tendrá para cualquier elemento de $\mathbb{N}$, (en lugar de poner la prueba de un solo número y, a continuación, generalizar para todos los números naturales), se utiliza como el objeto de nuestra prueba de un solo 'abstracto' número natural, $k$, lo cual es suficiente como prueba para el conjunto total $\mathbb{N}$.

Un enfoque de este tipo, definitivamente, sufren de ser "abiertas", y no es lógicamente válido. Creo que la frase "arbitrario pero fijo" fue acuñado para dirigir a nosotros fuera de este concepto erróneo: sí, nuestra elección del número es "arbitraria" y, de hecho, no estamos dando el nombre de ella, sin embargo, no ser engañados a pensar que estamos utilizando un 'resumen' $k$, en lugar de "$k$ es fijo", y es a partir de esta fija $k$ que vamos posteriormente extender la prueba a todos los de $\mathbb{N}$.