Loading [MathJax]/jax/output/HTML-CSS/jax.js
Saltar al contenido principal
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
LibreTexts Español

2.5: Inducción

( \newcommand{\kernel}{\mathrm{null}\,}\)

Template:MathJaxLevin

La inducción matemática es una técnica de prueba, no muy diferente a la prueba directa o prueba por contradicción o prueba combinatoria. 3 Puede o no estar familiarizado con estos todavía. Los consideraremos en el Capítulo 3. En otras palabras, la inducción es un estilo de argumento que utilizamos para convencernos a nosotros mismos y a los demás de que una afirmación matemática es siempre cierta. Muchas afirmaciones matemáticas se pueden probar simplemente explicando lo que significan. Otros son muy difíciles de probar; de hecho, hay afirmaciones matemáticas relativamente simples que nadie sabe probar todavía. Para facilitar el descubrimiento de pruebas, es importante conocer algunos estilos estándar de argumentos. La inducción es uno de esos estilos. Empecemos con un ejemplo:

Sellos

¡Investiga!

Necesitas enviar un paquete por correo, pero aún no sabes cuánto franqueo necesitarás. Tienes un gran suministro de sellos de 8 centavos y sellos de 5 centavos. ¿Qué cantidades de franqueo puedes hacer exactamente usando estos sellos? ¿Qué cantidades son imposibles de hacer?

Quizás al investigar el problema anterior escogiste algunas cantidades de franqueo, y luego averiguaste si podrías hacer esa cantidad usando solo sellos de 8 centavos y 5 centavos. Quizás hiciste esto en orden: ¿puedes hacer 1 centavo de franqueo? ¿Puedes hacer 2 centavos? ¿3 centavos? Y así sucesivamente. Si esto es lo que hiciste, en realidad estabas respondiendo una secuencia de preguntas. Tenemos métodos para tratar las secuencias. A ver si eso ayuda.

En realidad, no vamos a hacer una secuencia de preguntas, sino más bien una secuencia de declaraciones. DejaP(n) ser la declaración “puedes hacern centavos de franqueo usando solo sellos de 8 centavos y 5 centavos”. Ya que para cada valor den,P(n) es una declaración, es verdadera o falsa. Entonces, si formamos la secuencia de declaraciones

\ comenzar {ecuación*} P (1), P (2), P (3), P (4),\ lpuntos\ final {ecuación*}

la secuencia consistirá enT's (para verdadero) yF's (para falso). En nuestro caso particular se inicia la secuencia

\ start {ecuación*} F, F, F, F, T, F, F, T, F, F, T, F, F, T,\ lpuntos\ final {ecuación*}

porque todosP(1),P(2),P(3),P(4) son falsos (no se puede hacer 1, 2, 3 o 4 centavos de franqueo) peroP(5) es cierto (usa un sello de 5 centavos), y así sucesivamente.

Pensemos un poco en cómo podríamos encontrar el valor deP(n) para algún específicon (el “valor” seráT o bienF). ¿Cómo encontramos el valor del términon th de una secuencia de números? ¿Cómo encontramos?an? Había dos formas en las que podíamos hacer esto: o bien había una fórmula cerrada paraan, que pudiéramos conectarnosn a la fórmula y obtener nuestro valor de salida, o teníamos una definición recursiva para la secuencia, así podríamos usar los términos anteriores de la secuencia para calcular el nº término. Al tratar con secuencias de declaraciones, podríamos usar cualquiera de estas técnicas también. A lo mejor hay una manera den aprovecharse para determinar si podemos hacern centavos de franqueo. Eso sería algo así como una fórmula cerrada. O en su lugar podríamos usar los términos anteriores en la secuencia (de declaraciones) para determinar si podemos hacern centavos de franqueo. Es decir, si conocemos el valor deP(n1), can obtenemos de eso al valor deP(n)? Eso sería algo así como una definición recursiva para la secuencia. Recuerde, encontrar definiciones recursivas para secuencias a menudo era más fácil que encontrar fórmulas cerradas. Lo mismo es cierto aquí.

Supongamos que te dije que esoP(43) era cierto (lo es). ¿Se puede determinar a partir de este hecho el valor deP(44) (ya sea verdadero o falso)? Sí se puede. Aunque no sepamos exactamente cómo ganamos 43 centavos de los sellos de 5 y 8 centavos, sí sabemos que había alguna manera de hacerlo. ¿Y si de esa manera usara al menos tres sellos de 5 centavos (haciendo 15 centavos)? Podríamos reemplazar esos tres sellos de 5 centavos por dos sellos de 8 centavos (haciendo 16 centavos). El franqueo total ha subido en 1, así que tenemos una manera de hacer 44 centavos, asíP(44) es cierto. Por supuesto, asumimos que teníamos al menos tres sellos de 5 centavos. ¿Y si no lo hicimos? Entonces debemos tener al menos tres sellos de 8 centavos (haciendo 24 centavos). Si reemplazamos esos tres sellos de 8 centavos por cinco sellos de 5 centavos (haciendo 25 centavos) entonces nuevamente hemos aumentado nuestro total en 1 centavo para que podamos hacer 44 centavos, asíP(44) es cierto.

Observe que no hemos dicho cómo hacer 44 centavos, solo que podemos, sobre la base de que podemos hacer 43 centavos. ¿Cómo sabemos que podemos hacer 43 centavos? Quizás porque sabemos que podemos ganar42 centavos, lo que sabemos que podemos hacer porque sabemos que podemos ganar 41 centavos, y así sucesivamente. ¡Es una recursión! Al igual que con una definición recursiva de una secuencia numérica, debemos especificar nuestro valor inicial. En este caso, el valor inicial es “P(1)es falso”. Eso no es bueno, ya que nuestra relación de recurrencia solo dice queP(k+1) es cierto si tambiénP(k) es cierto. Tenemos que iniciar el proceso con un verdaderoP(k). Entonces, en cambio, podríamos querer usar “P(31)es verdadero” como condición inicial.

Armando todo esto llegamos al siguiente hecho: es posible (exactamente) hacer cualquier cantidad de franqueo mayor a 27 centavos usando solo sellos de 5 centavos y 8 centavos. 4 Esto no es afirmar que no haya montos menores a 27 centavos que también se puedan hacer. En otras palabras,P(k) es cierto para cualquierak28. Para probarlo, podríamos hacer lo siguiente:

  1. Demostrar que esoP(28) es cierto.
  2. Demostrar que siP(k) es cierto, entoncesP(k+1) es cierto (para cualquierak28).

Supongamos que lo hemos hecho. Entonces sabemos que el término 28 de la secuencia anterior es aT (usando el paso 1, la condición inicial o caso base), y que cada término posterior al 28 esT también (usando el paso 2, la parte recursiva o caso inductivo). Así es como se vería realmente la prueba.

Prueba

P(n)Sea el enunciado “es posible hacer exactamenten centavos de franqueo utilizando sellos de 5 y 8 centavos”. Vamos a mostrarP(n) es verdad para todosn28.

Primero, demostramos que esoP(28) es cierto:28=45+18, así podemos hacer28 centavos usando cuatro sellos de 5 centavos y un sello de 8 centavos.

Ahora supongamos queP(k) es cierto para algunos arbitrariosk28. Entonces es posible hacerk centavos usando sellos de 5 centavos y 8 centavos. Tenga en cuentak28, que como no puede ser que usemos menos de tres sellos de 5 centavos y menos de tres sellos de 8 centavos: usar dos de cada uno daría solo 26 centavos. Ahora bien, si hemos hechok centavos usando al menos tres sellos de 5 centavos, reemplace tres sellos de 5 centavos por dos sellos de 8 centavos. Esto reemplaza 15 centavos de franqueo por 16 centavos, pasando de un total dek centavos ak+1 centavos. AsíP(k+1) es cierto. Por otro lado, si hemos hechok centavos usando al menos tres sellos de 8 centavos, entonces podemos reemplazar tres sellos de 8 centavos por cinco sellos de 5 centavos, pasando de 24 centavos a 25 centavos, dando un total dek+1 centavos de franqueo. Entonces en este caso tambiénP(k+1) es cierto.

Por lo tanto, por el principio de inducción matemática,P(n) es cierto para todosn28.

Pruebas de formalización

Lo que hicimos en el ejemplo de sello anterior funciona para muchos tipos de problemas. La prueba por inducción es útil cuando se trata de probar declaraciones sobre todos los números naturales, o todos los números naturales mayores que algún primer caso fijo (como 28 en el ejemplo anterior), y en algunas otras situaciones también. En particular, la inducción debe usarse cuando hay alguna manera de pasar de un caso a otro, cuando se puede ver como siempre “hacer uno más”.

Esta es una gran idea. Pensar inductivamente en un problema puede dar una nueva visión del problema. Por ejemplo, para entender realmente el problema del sello, debes pensar en cómo se puede hacer cualquier cantidad de franqueo (mayor a 28 centavos) (esto es un razonamiento no inductivo) y también cómo las formas en que se puede hacer el franqueo cambia a medida que aumenta la cantidad (razonamiento inductivo). Cuando se le pide que proporcione una prueba por inducción, se le está pidiendo que piense en el problema dinámicamente; ¿cómo el aumenton cambia el problema?

Pero también hay otro lado de las pruebas por inducción. En matemáticas, no basta con entender un problema, también se debe poder comunicar el problema a los demás. Como cualquier disciplina, las matemáticas tienen lenguaje y estilo estándar, lo que permite a los matemáticos compartir sus ideas de manera eficiente. Las pruebas por inducción tienen cierto estilo formal, y es importante poder escribir en este estilo. Nos permite mantener nuestras ideas organizadas e incluso podría ayudarnos a formular una prueba.

Aquí está la estructura general de una prueba por inducción matemática:

Estructura de prueba de inducción

Empieza por decir cuál es la afirmación que quieres probar: “QueP(n) sea la declaración...” Para probar que esoP(n) es cierto para todosn0, debes probar dos hechos:

  1. Caso base: Demostrar queP(0) es cierto. Esto lo haces directamente. Esto suele ser fácil.
  2. Caso inductivo:P(k)\impP(k+1) Demuéstralo para todosk0. Es decir, probar que para cualquierak0 siP(k) es cierto, entonces tambiénP(k+1) es cierto. Esta es la prueba de una declaración if... entonces..., así que se puede suponer queP(k) es verdadera (P(k)se llama la hipótesis inductiva). Entonces hay que explicar por qué tambiénP(k+1) es cierto, dada esa suposición.

Asumiendo que tienes éxito en ambas partes anteriores, puedes concluir: “Por lo tanto, por el principio de inducción matemática, la afirmaciónP(n) es cierta para todos”n0.

En ocasiones la afirmación sóloP(n) será verdadera para valores den4, por ejemplo, o algún otro valor. En tales casos, reemplace todos los 0 anteriores por 4's (o el otro valor).

La otra ventaja de formalizar pruebas inductivas es que permite verificar que la lógica detrás de este estilo de argumento es válida. ¿Por qué funciona la inducción? Piensa en una fila de fichas de dominó puestas de pie sobre sus bordes. Queremos argumentar que en un minuto, todas las fichas de dominó se habrán caído. Para que esto suceda, necesitarás empujar el primer dominó. Ese es el caso base. También tendrá que ser que los dominó estén lo suficientemente cerca entre sí como para que cuando caiga algún dominó en particular, provocará que caiga el siguiente dominó. Ese es el caso inductivo. Si se cumplen ambas condiciones, empujas el primer dominó sobre y cada dominó hará que el siguiente caiga, entonces todos los dominó caerán.

¡La inducción es poderosa! Piensa en lo fácil que es derribar dominó cuando no tienes que empujar tú mismo cada dominó. Simplemente comienzas la reacción en cadena, y la confianza en la relativa cercanía de los dominó para cuidar del resto.

Piense en nuestro estudio de secuencias. Es más fácil encontrar definiciones recursivas para secuencias que fórmulas cerradas. Pasar de un caso a otro es más fácil que ir directamente a un caso particular. Eso es lo que es tan bueno de la inducción. En lugar de ir directamente al caso (arbitrario) porque solon, tenemos que decir cómo llegar de un caso a otro.

Cuando se le pide que pruebe una afirmación por inducción matemática, primero debe pensar en por qué la afirmación es verdadera, usando razonamiento inductivo. Explique por qué la inducción es lo correcto y aproximadamente por qué funcionará el caso inductivo. Después, siéntate y escribe una prueba formal y cuidadosa usando la estructura anterior.

Ejemplos

Aquí hay algunos ejemplos de pruebas por inducción matemática.

Ejemplo2.5.1

Demostrar para cada número naturaln1 que1+2+3++n=n(n+1)2.

Contestar

Primero, pensemos inductivamente sobre esta ecuación. De hecho, sabemos que esto es cierto por otras razones (revertir y agregar viene a la mente). Pero, ¿por qué podría ser aplicable la inducción? El lado izquierdo suma los números del 1 aln. If we know how to do that, adding just one more term (n+1) would not be that hard. For example, if n=100, suppose we know that the sum of the first 100 numbers is 5050 (so 1+2+3++100=5050, which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have 1+2+3++100+101=5050+101=5151. In fact, it would always be easy to add just one more term. This is why we should use induction.

Ahora la prueba formal:

Prueba

LetP(n) be the statement 1+2+3++n=n(n+2)2. We will show that P(n) is true for all natural numbers n1.

Caso base:P(1) is the statement 1=1(1+1)2 which is clearly true.

Caso inductivo: Letk1 be a natural number. Assume (for induction) that P(k) is true. That means 1+2+3++k=k(k+1)2. We will prove that P(k+1) is true as well. That is, we must prove that 1+2+3++k+(k+1)=(k+1)(k+2)2. To prove this equation, start by adding k+1 to both sides of the inductive hypothesis:

\ begin {ecuación*} 1 + 2 + 3 +\ cdots + k + (k+1) =\ frac {k (k+1)} {2} + (k+1). \ end {ecuación*}

Ahora, simplificando el lado derecho obtenemos:

\ begin {alinear*}\ frac {k (k+1)} {2} + k+1\ amp =\ frac {k (k+1)} {2} +\ frac {2 (k+1)} {2}\\ amp =\ frac {k (k+1) + 2 (k+1)} {2}\\ amp =\ frac {(k+2) (k+1)} {2}. \ end {alinear*}

Por lo tantoP(k+1) is true, so by the principle of mathematical induction P(n) is true for all natural numbers n1.

Obsérvese que en la parte de la prueba en la queP(k), probamosP(k+1) a partir se utilizó la ecuaciónP(k). Esta fue la hipótesis inductiva. Ver cómo usar las hipótesis inductivas suele ser sencillo a la hora de probar un hecho sobre una suma como esta. En otras pruebas, puede ser menos obvio dónde encaja.

Ejemplo2.5.2

Demostrar que para todosn\N,6n1 es un múltiplo de 5.

Solución

Nuevamente, comience por comprender la dinámica del problema. ¿Qué hace aumentarn do? Let's try with a few examples. If n=1, then yes, 611=5 is a multiple of 5. What does incrementing n to 2 look like? We get 621=35, which again is a multiple of 5. Next, n=3: but instead of just finding 631, what did the increase in n do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number which is one more than a multiple of 5 by 6 (because 621 is a multiple of 5, so 62 is one more than a multiple of 5). What do numbers which are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? Depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

El punto es, cada vez que multiplicamos por sólo uno más seis, todavía obtenemos un número con el último dígito 6, así que restar 1 nos da un múltiplo de 5. Ahora la prueba formal:

Prueba

LetP(n) be the statement, “6n1 is a multiple of 5.” We will prove that P(n) is true for all n\N.

Caso base:P(0) is true: 601=0 which is a multiple of 5.

Caso inductivo: Letk be an arbitrary natural number. Assume, for induction, that P(k) is true. That is, 6k1 is a multiple of 5. Then 6k1=5j for some integer j. This means that 6k=5j+1. Multiply both sides by 6:

\ begin {ecuación*} 6^ {k+1} = 6 (5j+1) = 30j + 6. \ end {ecuación*}

Pero queremos saber sobre6k+11, so subtract 1 from both sides:

\ begin {ecuación*} 6^ {k+1} - 1 = 30j + 5. \ end {ecuación*}

Por supuesto30j+5=5(6j+1), so is a multiple of 5.

Por lo tanto6k+11 is a multiple of 5, or in other words, P(k+1) is true. Thus, by the principle of mathematical induction P(n) is true for all n\N.

Teníamos que ser un poco inteligentes (es decir, usar algo de álgebra) para localizar el6k1 interior de6k+11 antes de poder aplicar la hipótesis inductiva. Esto es lo que puede hacer que las pruebas inductivas sean desafiantes.

En los dos ejemplos anteriores, empezamos conn=1 on=0. Podemos comenzar más tarde si es necesario.

Ejemplo2.5.3

Demuéstralon2<2n para todos los enterosn5.

Solución

Primero, la idea del argumento. ¿Qué pasa cuando aumentamosn by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have (n+1)2n2. This factors:

\ begin {ecuación*} (n+1) ^2 - n^2 = (n+1-n) (n+1+n) = 2n+1. \ end {ecuación*}

Pero duplicar el lado derecho lo incrementa2n, since 2n+1=2n+2n. When n is large enough, 2n>2n+1.

Lo que estamos diciendo aquí es que cada vezn increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when n=5), it will never catch up.

Ahora la prueba formal:

LetP(n) be the statement n2<2n. We will prove P(n) is true for all integers n5.

Caso base:P(5) is the statement 52<25. Since 52=25 and 25=32, we see that P(5) is indeed true.

Caso inductivo: Letk5 be an arbitrary integer. Assume, for induction, that P(k) is true. That is, assume k2<2k. We will prove that P(k+1) is true, i.e., (k+1)2<2k+1. To prove such an inequality, start with the left-hand side and work towards the right-hand side:

\ begin {align*} (k+1) ^2\ amp = k^2 + 2k + 1\ amp\\ amp\ amp\ lt 2^k + 2k + 1\ amp\ ldots\ text {por la hipótesis inductiva.}\\ amp\ lt 2^k + 2^k\ amp\ ldots\ text {since} 2k + 1\ lt 2^k\ text {for} k\ ge 5.\\ amp = 2^ {k+1}. \ amp\ final {alinear*}

Siguiendo las igualdades y desigualdades a través de, obtenemos(k+1)2<2k+1, in other words, P(k+1). Therefore by the principle of mathematical induction, P(n) is true for all n5.

El ejemplo anterior podría recordarte el principio del hipódromo a partir del cálculo, que dice que sif(a)<g(a), yf(x)<g(x)f(x)<g(x) parax>a, entonces porx>a. La misma idea: la función más grande está aumentando a un ritmo más rápido que la función más pequeña, por lo que la función más grande se mantendrá más grande. En matemáticas discretas, no tenemos derivados, así que miramos las diferencias. Así la inducción es el camino a seguir.

Advertencia:

Con gran poder, viene una gran responsabilidad. La inducción no es magia. Parece muy poderoso poder asumir queP(k) es cierto. Después de todo, estamos tratando de demostrar queP(n) es verdad y la única diferencia está en la variable:k vsn. ¿Asumimos que lo que queremos probar es cierto? En realidad no. Asumimos queP(k) es cierto sólo por el bien de probar que esoP(k+1) es cierto.

Aún así podrías empezar a creer que puedes probar cualquier cosa con inducción. Considera esta “prueba” incorrecta de que cada canadiense tiene el mismo color de ojos: QueP(n) sea la afirmación de que cualquiern canadiense tiene el mismo color de ojos. P(1)es cierto, ya que todos tienen el mismo color de ojos que ellos mismos. Ahora supongamos queP(k) es verdad. Es decir, supongamos que en cualquier grupo dek canadienses, todos tienen el mismo color de ojos. Consideremos ahora a un grupo arbitrario dek+1 canadienses. El primerok de estos debe tener el mismo color de ojos, ya queP(k) es cierto. Además, el últimok de estos debe tener el mismo color de ojos, ya queP(k) es cierto. Entonces, de hecho, todos los grupos deben tener el mismo color de ojos. AsíP(k+1) es cierto. Entonces, por el principio de inducción matemática,P(n) es cierto para todosn.

Claramente algo salió mal. El problema es que la prueba queP(k) implica loP(k+1) asumek2. Sólo hemos demostrado queP(1) es verdad. De hecho,P(2) es falso.

Inducción Fuerte

¡Investiga!

Comience con un trozo de papel cuadrado. Quieres cortar este cuadrado en cuadrados más pequeños, sin dejar residuos (cada trozo de papel con el que termines debe ser un cuadrado). Obviamente es posible cortar el cuadrado en 4 cuadrados. También puedes cortarlo en 9 cuadrados. Resulta que puedes cortar el cuadrado en 7 cuadrados (aunque no todos del mismo tamaño). ¿Con qué otros números de cuadrados podrías terminar?

A veces, para demostrar que esoP(k+1) es cierto, sería útil saber esoP(k) yP(k1) yP(k2) son todos ciertos. Considera el siguiente rompecabezas:

Tienes una barra de chocolate rectangular, compuesta por cuadradosn idénticos de chocolate. Puedes tomar una barra de este tipo y romperla a lo largo de cualquier fila o columna. ¿Cuántas veces tendrás que romper la barra para reducirla a cuadradosn individuales de chocolate?

Al principio, esta pregunta puede parecer imposible. ¿Quizás pretendía pedir el menor número de descansos necesarios? Investiguemos.

Comienza con algunos casos pequeños. Sin=2, debes tener un1×2 rectángulo, el cual se puede reducir a piezas individuales en una sola rotura. Conn=3, debemos tener una1×3 barra, que requiere dos descansos: el primer break crea un solo cuadrado y un1×2 compás, que sabemos que toma uno (más) break.

Yn=4? ahora podríamos tener un2×2 bar, o un1×4 bar. En el primer caso, rompa la barra en dos2×2 barras, cada una de las cuales requiera una rotura más (es decir, un total de tres descansos requeridos). Si empezamos con un1×4 bar, tenemos opciones para nuestro primer descanso. Podríamos romper la barra por la mitad, creando dos1×2 barras, o podríamos romper una sola casilla, dejando una1×3 barra. Pero de cualquier manera, todavía necesitamos dos descansos más, dando un total de tres.

Está empezando a verse como no importa cómo rompamos la barra (y no importa cómo estén dispuestos losn cuadrados en un rectángulo), siempre tendremos el mismo número de descansos requeridos. También parece que ese número es uno menos quen:

Tiene sentido probar esto por inducción porque después de romper la barra una vez, te quedan barras de chocolate más pequeñas. Reducir a casos más pequeños es de lo que se trata la inducción. Podemos suponer inductivamente que ya sabemos cómo lidiar con estas barras más pequeñas. El problema es que si estamos tratando de probar el caso inductivo sobre una barra(k+1) -cuadrada, no sabemos que después del primer descanso la barra restante tendrák cuadrados. Entonces realmente necesitamos asumir que nuestra conjetura es cierta para todos los casos menos quek+1.

¿Es válido hacer esta suposición más fuerte? Recuerden, en la inducción estamos tratando de demostrar que esoP(n) es cierto para todosn. ¿Y si ese no fuera el caso? Entonces habría algunos primerosn0 para los queP(n0) era falso. Ya quen0 es el primer contraejemplo, sabemos que esoP(n) es cierto para todosn<n0. Ahora procedemos a probar que en realidadP(n0) es cierto, con base en el supuesto queP(n) es cierto para todos los más pequeñosn.

Esto es toda una ventaja: ahora tenemos una hipótesis inductiva más fuerte. Podemos suponer queP(1),P(2),P(3),...P(k) es verdad, sólo para demostrar que esoP(k+1) es cierto. Anteriormente, acabamos de asumirP(k) para este propósito.

Es un poco más fácil si cambiamos nuestras variables por inducción fuerte. Así es como se vería la prueba formal:

Estructura resistente a prueba de inducción

Nuevamente, comience diciendo lo que quiere probar: “QueP(n) sea la declaración...” Luego establezca dos hechos:

  1. Caso base: Demostrar queP(0) es cierto.
  2. Caso inductivo: Supongamos queP(k) es cierto para todosk<n. Demostrar que esoP(n) es cierto.

Concluye, “por lo tanto, por una fuerte inducción,P(n) es cierto para todos”n>0.

Por supuesto, es aceptable reemplazar 0 por una caja base más grande si es necesario. 5 Técnicamente, la inducción fuerte no requiere que demuestres una caja base separada. Esto se debe a que al probar el caso inductivo, debes demostrar que\(P(0)\) is true, assuming \(P(k)\) is true for all \(k \lt 0\). But this is not any help so you end up proving \(P(0)\) anyway. To be on the safe side, we will always include the base case separately.

Demostremos nuestra conjetura sobre el rompecabezas de la barra de chocolate:

Prueba

P(n)Sea el enunciado, “se necesitann1 descansos para reducir una barra de chocolaten -cuadrada a cuadrados individuales”.

Caso base: ConsiderarP(2). Los cuadrados deben estar dispuestos en un1×2 rectángulo, y requerimos21=1 descansos para reducir esto a cuadrados simples.

Caso inductivo: Se corrige un arbitrarion2 yP(k) se asume que es cierto para todosk<n. Considera una barra de chocolate rectangularn cuadrada. Rompe la barra una vez a lo largo de cualquier fila o columna. Esto da como resultado dos barras de chocolate, digamos de tamañosa yb. Es decir, tenemos una barra de chocolate rectangulara -cuadrada, una barra de chocolate rectangularb -cuadrada, ya+b=n.

También sabemos esoa<n yb<n, así por nuestra hipótesis inductiva,P(a) yP(b) son ciertos. Para reducir la barraa -sqaure a cuadrados individuales tomaa1 descansos; para reducir la barrab -cuadrada a cuadrados individuales tomab1 descansos. Hacer esto da como resultado que nuestra barra original se reduzca a cuadrados simples. Todos juntos se llevó el descanso inicial, más losa1 yb1 descansos, para un total de1+a1+b1=a+b1=n1 descansos. AsíP(n) es cierto.

Por lo tanto, por fuerte inducción,P(n) es cierto para todosn2.

Aquí hay un ejemplo matemáticamente más relevante:

Ejemplo2.5.5

Demostrar que cualquier número natural mayor que 1 es primo o puede escribirse como producto de primos.

Solución

Primero, la idea: si tomamos algún númeron, maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than n (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

Ahora la prueba formal:

Prueba

LetP(n) be the statement, “n is either prime or can be written as the product of primes.” We will prove P(n) is true for all n2.

Caso base:P(2) is true because 2 is indeed prime.

Caso inductivo: asumaP(k) is true for all k<n. We want to show that P(n) is true. That is, we want to show that n is either prime or is the product of primes. If n is prime, we are done. If not, then n has more than 2 divisors, so we can write n=m1m2, with m1 and m2 less than n (and greater than 1). By the inductive hypothesis, m1 and m2 are each either prime or can be written as the product of primes. In either case, we have that n is written as the product of primes.

Así, por la fuerte inducción,P(n) is true for all n2.

Si usas inducción regular o inducción fuerte depende de la afirmación que quieras probar. Si quisieras estar seguro, siempre podrías usar una inducción fuerte. Realmente es más fuerte, así que puede lograr todo lo que la inducción “débil” puede. Dicho esto, el uso de la inducción regular suele ser más fácil ya que solo hay un lugar donde puedes usar la hipótesis de inducción. También hay algo que decir para la elegancia en las pruebas. Si puedes probar una declaración usando herramientas más simples, es bueno hacerlo.

Como contraste final entre las dos formas de inducción, considere una vez más el problema del sello. La inducción regular trabajó mostrando cómo aumentar el franqueo en un centavo (ya sea reemplazando tres sellos de 5 centavos por dos sellos de 8 centavos, o tres sellos de 8 centavos con cinco sellos de 5 centavos). Podríamos dar una prueba ligeramente diferente usando inducción fuerte. Primero, podríamos mostrar cinco casos base: es posible hacer 28, 29, 30, 31 y 32 centavos (en realidad diríamos cómo se hace cada uno de estos). Ahora supongamos que es posible hacerk centavos de franqueo para todosk<n siempre y cuandok28. Siempre y cuandon>32, esto signifique en particular podemos hacerk=n5 centavos. Ahora agrega un sello de 5 centavos para obtener hacern centavos.


This page titled 2.5: Inducción is shared under a CC BY-SA license and was authored, remixed, and/or curated by Oscar Levin.

Support Center

How can we help?