¿Cuál es la lógica detrás de la prueba por inducción? No puedo entender por qué el método de inducción proporciona una prueba, si el segundo paso es una hipótesis. Por lo tanto, no podemos probarlo, como en el caso base.

Supongamos que quiero probar la siguiente proposición:

• [math] P (n) [/ math] es verdadero para todos [math] n \ in \ mathbb {N} [/ math]

La prueba por inducción funciona porque la proposición anterior es equivalente a la siguiente proposición:

• [math] P (1) [/ math] es verdadero, y por cada [math] k \ in \ mathbb {N} [/ math], si [math] P (k) [/ math] es verdadero, entonces [ matemáticas] P (k + 1) [/ matemáticas] es cierto.

El truco es darse cuenta de que, en el paso inductivo, “k” es solo un número que puede sustituir a cualquier número entero positivo. Lo que está demostrando con ese paso inductivo es que, si algo es cierto para un número entero positivo, es cierto para el número entero positivo después de él.

Este paso es inútil por sí solo. Puede usarlo para probar cosas que son claramente falsas. Por ejemplo, podría decir que si “k” es mayor que un millón, entonces k + 1 también es mayor que un millón. Y dado que k es solo un sustituto de cualquier número entero positivo, cualquier número entero positivo es mayor que un millón. Locura.

Entonces el instinto en tu comentario es bueno. Las hipótesis no son pruebas. Puedes pensar en esto más como una plantilla para una prueba. Está todo listo, listo para usar, pero necesita un número concreto para que funcione y hacer que la máquina funcione.

Ese número concreto es el caso base. Tienes que demostrar algo verdadero para el número uno. Y luego puede aplicar esa plantilla, conectando “1” para “k” para demostrar que la propiedad es verdadera para 2. Y luego puede aplicar esa plantilla nuevamente a 2 (ya que ahora sabemos que 2 tiene la propiedad) para probar la propiedad es verdadera para 3. Y a partir de tres puede probar la propiedad para 4, utilizando la plantilla, y desde 4 podemos probarla para 5, etc.

Ahora tienes dos opciones. Puede continuar aplicando el paso inductivo a cada número consecuente, para siempre, o puede … hacer un poco de trampa y asumir que esta máquina de prueba seguirá funcionando para todos los números enteros positivos. Como lo primero es imposible, como era de esperar, los matemáticos eligen hacer lo segundo.

En el primer paso de la prueba de inducción, demostramos que la relación o igualdad dada es verdadera para n = 1 …

En el segundo paso, suponemos que la relación dada es verdadera para n = k, donde n pertenece al conjunto de números naturales … nos da una ecuación para su uso posterior …

Y, en el tercer y último paso, usando la ecuación anterior, demostramos que la relación dada es verdadera para n = k + 1….

Ahora, ¿cuál es la lógica detrás de esto?

La lógica detrás de la prueba de inducción es que cuando elegimos n = k en el segundo paso, puede ser cualquier no natural. incluyendo 1 también …

Entonces, cuando tomamos k = 1 … entonces nuestra suposición de que la relación dada es verdadera para n = k es correcta porque lo hemos demostrado en el primer paso. Además, será cierto para n = k + 1 = 2 también como se demuestra en el tercer paso …

Ahora, cuando tomamos k = 2, nuevamente nuestra suposición del segundo paso es verdadera porque se demostró que era verdadera cuando k era igual a 1. Además, se demuestra que es verdadera para n = k + 1 = 3 en virtud de el tercer paso …

Entonces, se demuestra a partir de la regla de la cadena que para cada valor de k = 1,2,3,4 …..n, la relación dada es verdadera para k = 2,3,4,5 …… n + 1, que tiende a la conclusión de que es cierto para todos los no naturales …

Espero eso ayude,

#hp

Me gusta esta analogía:

Imagine configurar un número (infinito) de fichas de dominó. Desea saber si todos van a caer. Primero, en una prueba por inducción, demuestra que el caso base es verdadero. Aquí: caerá el primer dominó. La siguiente parte de la prueba es el paso : suponga que si cae la enésima dominó, entonces caerá la [matemática] n + 1 [/ matemática]. Si ha probado estos dos pasos, ya ha terminado. Porque sabes que la primera ficha de dominó caerá, pero luego el peldaño mide que la segunda caerá, y luego la tercera, y así sucesivamente.

Muchas personas se confunden y tienen dificultades para convencerse de que este tipo de prueba funciona, pero si tiene en cuenta esta imagen, podría ayudar. No podrá probar el paso si no se cumple para todos los valores de n.

Solo recuerda que, por sí mismo, el paso no prueba nada. Básicamente dice: si cae una ficha de dominó, también caerá la siguiente. Sin embargo, sin probar el caso base , el primer dominó no caerá, por lo tanto, el segundo no caerá y así sucesivamente.

¿Cuál es la lógica detrás de la prueba por inducción?

Sea [math] P (n) [/ math] la propuesta en cuestión para el número natural [math] n [/ math]. Por ejemplo, la proposición de que [math] \ sum \ limits_ {i = 1} ^ n = 1 + 2 + \ dotsb + n = \ frac12n (n + 1) [/ math].

El caso base es [matemática] P (1) [/ matemática]. Es decir, [matemática] \ suma \ límites_ {i = 1} ^ 1 = 1 \ quad \ marca de verificación [/ matemática]

El paso inductivo es [matemática] P (k) \ Rightarrow P (k + 1) [/ matemática]. Es decir [matemáticas] \ frac12k (k + 1) + (k + 1) = \ frac12 (k + 1) (k + 2) \ quad \ checkmark [/ math]

Por lo tanto, [math] P (1) \ Rightarrow P (2) [/ math] para que sepamos [math] P (2) [/ math].

Pero [math] P (2) \ Rightarrow P (3) [/ math] entonces sabemos [math] P (3) [/ math].

Entonces [matemáticas] P (1) \ Rightarrow P (2) \ Rightarrow P (3) \ Rightarrow \ dotsb \ Rightarrow P (n) [/ math].

Por el axioma de inducción, [matemática] P (n) [/ matemática] para todos [matemática] n [/ matemática].

Ni el caso base ni el paso inductivo son hipótesis. Ambos son lemas que deben ser probados. El axioma de inducción permite el salto de cualquier [matemática] n [/ matemática] particular (que puede probarse mediante un número finito de aplicaciones del paso inductivo) a todas las [matemática] n \ in \ mathbb N [/ matemática].

Algunos finitistas rechazan el axioma de inducción pero, para la mayoría de las personas, es una conclusión bastante natural.

Bueno, en el primer caso, la prueba había sido hecha para el caso base por cálculo difícil.

En la hipótesis asumimos algo que ya sabemos (al menos para el caso base), de la declaración para x mostramos que es cierto para el sucesor de x.

por ejemplo, podemos probar que la suma de todos los enteros de 1 a x es [math] \ frac {x \ cdot (x + 1)} {2} [/ math].

Vamos a probarlo para x = 1 (debería ser 1). Y en sí [matemáticas] \ frac {1 \ cdot (1 + 1)} {2} = \ frac {1 \ cdot 2} {2} = \ frac {2} {2} = 1 [/ matemáticas].

Ahora supongamos que sabemos que la suma de 1 a x es [matemática] \ frac {x \ cdot (x + 1)} {2} [/ matemática].

Cuando podemos usar este conocimiento para probar que la fórmula también es válida para x + 1, es vaild. Entonces, reemplacemos x con x + 1. La suma de 1 a x + 1 es la suma de 1 a x + (x + 1). Pero ya sabemos cuál es la suma de 1 a x, por lo que podemos reemplazarla: entonces tenemos [matemática] \ frac {x \ cdot (x + 1)} {2} + (x + 1) = \ frac { x \ cdot (x + 1) + 2x + 2} {2} = frac {x ^ 2 + x + 2x + 2} {2} = \ frac {(x + 1) \ cdot (x + 2)} { 2} [/ math] y si reemplaza x con x + 1 en [math] \ frac {x \ cdot (x + 1)} {2} [/ math] obtenemos lo mismo.

El segundo paso implica algo llamado “hipótesis inductiva” porque lo que haces en el segundo paso es probar una afirmación de si-entonces. Específicamente, está demostrando la afirmación “Para cada número k, si lo que originalmente queríamos demostrar es cierto para k, entonces también es cierto para k + 1”, y la parte “si lo que originalmente queríamos demostrar es cierto para k “es la” hipótesis de inducción “.

Por ejemplo, si está tratando de demostrar que la suma de los primeros N números impares es igual a N al cuadrado, entonces la declaración se convierte en “Para cada número k, si la suma de los primeros k números impares es igual a k al cuadrado, entonces la suma de los primeros k + 1 números impares es igual a (k + 1) al cuadrado “y la hipótesis inductiva es” la suma de los primeros k números impares es igual a k al cuadrado “.

Para probar la afirmación if-then, primero * asume * la hipótesis de inducción: que k es un número del que no sabemos nada, excepto que lo que originalmente intentamos probar es cierto, y luego intenta demostrar que esto significa que originalmente estábamos tratando de demostrar que también es cierto para k + 1.

Volviendo al ejemplo, suponemos que la suma de los primeros k enteros impares es k al cuadrado, luego intentamos demostrar que esto significa que la suma de los primeros k + 1 enteros impares es al cuadrado (k + 1).

Esto no es muy difícil. El número entero impar k es igual a 2k – 1, por lo que el número entero impar (k +1) es igual a 2k + 1. Como suponemos que la suma de los primeros enteros impares k es k ^ 2, la suma de los primeros Los enteros impares k + 1 deben ser k ^ 2 + 2k + 1, lo que equivale a (k + 1) ^ 2. Entonces, para todos los k, si los primeros enteros impares k suman k ^ 2, entonces los primeros enteros impares k + 1 suman (k + 1) ^ 2.

¿Por qué nos importa? Porque esto nos permite comenzar con cualquier número k y pruebas de “cadena” tan altas como queramos. “K + 1” también es un número k para el que la suma de los primeros enteros impares suma k ^ 2, por lo que “k + 1 + 1” también funciona. Y así sucesivamente, hasta el infinito.

Por supuesto, todavía tiene que haber un número k que pueda usar para iniciar la cadena de pruebas. Solo hemos demostrado que * si * hay tal que nuestra hipótesis es cierta, entonces la hipótesis es cierta para todos los números superiores a k. El número real que utilizamos para demostrar que realmente hay uno se llama “caso base”. (¡Puedes “probar” algunas cosas bastante tontas si olvidas que necesitas un número real para comenzar la cadena!)

En nuestro ejemplo, podemos tomar el número 1 como nuestro caso base. La suma de los primeros 1 enteros impares es 1, que de hecho es igual a 1 al cuadrado. Entonces, la suma de los primeros k enteros impares, donde k es mayor o igual que 1, realmente es igual a k ^ 2.

En conclusión, la prueba por inducción implica una “hipótesis inductiva” porque suponiendo que una hipótesis es la forma en que las personas generalmente prueban declaraciones de la forma “si hipótesis, luego conclusión”, y “prueba por inducción” implica probar ese tipo de declaración.

¡Espero que tenga sentido!

Otras respuestas han explicado por qué funciona, así que solo te daré una manera de pensarlo.

Si puedes probar algo verdadero, entonces es cierto. Si no fuera cierto, entonces obviamente no podría demostrarse que es cierto (en un conjunto consistente de axiomas).

Para cualquier número entero n, la prueba por inducción muestra que si desea probar que la afirmación es verdadera para n, puede hacerlo en n pasos probando primero para 1 y luego 2 y luego 3 …

Por lo tanto, puede probarse que es cierto para n independientemente de lo que sea n (siempre que sea un número entero positivo). Si es cierto para cualquier número entero positivo, entonces es cierto para todos los números enteros positivos.

Voy a intentar dar una respuesta que tenga sentido intuitivamente. Suponga que está parado en la orilla de un río (para que la analogía sea exactamente correcta, tiene que ser un río infinitamente ancho, pero ignore eso por ahora), que tiene una serie de escalones a través de él.

Sabes que puedes cruzar el río si sabes dos cosas: (1) puedes saltar al primer peldaño, y (2) si estás parado en cualquiera de los peldaños, siempre puedes saltar al siguiente.

(2) es el que tiene ganas de hacer trampa, lo sé: se siente como si estuvieras usando lo que estás tratando de probar para probarse a sí mismo. Pero en este paso, no estás asumiendo lo que estás tratando de demostrar. No estás asumiendo que estás parado en un peldaño. Todo lo que está probando es que si lo fuera, podría pasar al siguiente.

Al suponer que la declaración es verdadera para n = k y demostrar que es verdadera para n = 1 yn = k + 1, mostramos que la declaración es verdadera para todos los valores positivos de n.

Probar la declaración para n = 1 proporciona un ancla para la prueba. Más sobre eso más tarde.

Una vez comprobado que la afirmación es verdadera para n = 1, suponemos que es verdadera para n = k y usamos esta suposición para probarla para n = k + 1. Esencialmente, estos dos números (k y k + 1) podrían estar en cualquier lugar del conjunto de todos los enteros positivos. Además, dado que la declaración ha sido probada para k + 1, también está probada para k. Por lo tanto, se ha demostrado que la afirmación es verdadera para todos los valores de n mayores que 1.

Una prueba inductiva requiere que demuestre que la veracidad de la proposición P (k) implica la veracidad P (k + 1). Piensa en el efecto dominó. Para que caigan todas las fichas de dominó, también se debe demostrar que la primera ficha de dominó P (0) es verdadera.

sí.

Objetivo: tienes que demostrarlo para todos los n.

Empiezas probando 1.

Si lo demuestra por 2, ¡felicidades! lo has probado con 2 enteros. Pero tenías que probarlo para todos ellos.

Entonces tienes que probar para n.

Voila! lo has hecho por todo n.

Una vez que haya probado la segunda parte, aplíquela al caso base de n = 1. La segunda parte muestra que la afirmación es verdadera para n = 2. Luego aplique a n = 2 para ver que es verdadera para n = 3. Claramente, al continuar el proceso, el reclamo es verdadero para cualquier persona que desee especificar. Por lo tanto, es cierto para todos los n, y la afirmación queda así comprobada.

Su suposición principal es que si una proposición es cierta para algún número entero, también lo es para la siguiente.

Su suposición secundaria es que la proposición es verdadera para 1.

Entonces, por la suposición principal, es cierto para el sucesor de 1, que es 2.

Entonces, por la suposición principal, es cierto para el sucesor de 2, que es 3.

Entonces, por la suposición principal, es cierto para el sucesor de 3, que es 4.

Y, después de una cantidad infinita de tiempo, será cierto para cada entero positivo.