2.5: Inducción

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. ³ 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. Deja$P(n)$ ser la declaración “puedes hacer$n$ centavos de franqueo usando solo sellos de 8 centavos y 5 centavos”. Ya que para cada valor de$n\text{,}$$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á en$T$'s (para verdadero) y$F$'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 todos$P(1), P(2), P(3), P(4)$ son falsos (no se puede hacer 1, 2, 3 o 4 centavos de franqueo) pero$P(5)$ es cierto (usa un sello de 5 centavos), y así sucesivamente.

Pensemos un poco en cómo podríamos encontrar el valor de$P(n)$ para algún específico$n$ (el “valor” será$T$ o bien$F$). ¿Cómo encontramos el valor del término$n$ th de una secuencia de números? ¿Cómo encontramos?$a_n\text{?}$ Había dos formas en las que podíamos hacer esto: o bien había una fórmula cerrada para$a_n\text{,}$ que pudiéramos conectarnos$n$ 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 de$n$ aprovecharse para determinar si podemos hacer$n$ 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 hacer$n$ centavos de franqueo. Es decir, si conocemos el valor de$P(n-1)\text{,}$ can obtenemos de eso al valor de$P(n)\text{?}$ 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 eso$P(43)$ era cierto (lo es). ¿Se puede determinar a partir de este hecho el valor de$P(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 ganar$42$ 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 que$P(k+1)$ es cierto si también$P(k)$ es cierto. Tenemos que iniciar el proceso con un verdadero$P(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. ⁴ 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 cualquiera$k \ge 28$. Para probarlo, podríamos hacer lo siguiente:

1. Demostrar que eso$P(28)$ es cierto.
2. Demostrar que si$P(k)$ es cierto, entonces$P(k+1)$ es cierto (para cualquiera$k \ge 28$).

Supongamos que lo hemos hecho. Entonces sabemos que el término 28 de la secuencia anterior es a$T$ (usando el paso 1, la condición inicial o caso base), y que cada término posterior al 28 es$T$ 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 exactamente$n$ centavos de franqueo utilizando sellos de 5 y 8 centavos”. Vamos a mostrar$P(n)$ es verdad para todos$n \ge 28$.

Primero, demostramos que eso$P(28)$ es cierto:$28 = 4 \cdot 5+ 1\cdot 8\text{,}$ así podemos hacer$28$ centavos usando cuatro sellos de 5 centavos y un sello de 8 centavos.

Ahora supongamos que$P(k)$ es cierto para algunos arbitrarios$k \ge 28$. Entonces es posible hacer$k$ centavos usando sellos de 5 centavos y 8 centavos. Tenga en cuenta$k \ge 28\text{,}$ 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 hecho$k$ 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 de$k$ centavos a$k+1$ centavos. Así$P(k+1)$ es cierto. Por otro lado, si hemos hecho$k$ 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 de$k+1$ centavos de franqueo. Entonces en este caso también$P(k+1)$ es cierto.

Por lo tanto, por el principio de inducción matemática,$P(n)$ es cierto para todos$n \ge 28$.

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 aumento$n$ 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: “Que$P(n)$ sea la declaración...” Para probar que eso$P(n)$ es cierto para todos$n \ge 0\text{,}$ debes probar dos hechos:

1. Caso base: Demostrar que$P(0)$ es cierto. Esto lo haces directamente. Esto suele ser fácil.
2. Caso inductivo:$P(k) \imp P(k+1)$ Demuéstralo para todos$k \ge 0$. Es decir, probar que para cualquiera$k \ge 0$ si$P(k)$ es cierto, entonces también$P(k+1)$ es cierto. Esta es la prueba de una declaración if... entonces..., así que se puede suponer que$P(k)$ es verdadera ($P(k)$se llama la hipótesis inductiva). Entonces hay que explicar por qué también$P(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ón$P(n)$ es cierta para todos”$n \ge 0$.

En ocasiones la afirmación sólo$P(n)$ será verdadera para valores de$n \ge 4\text{,}$ 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 solo$n\text{,}$ 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.

Ejemplo$\PageIndex{1}$

Demostrar para cada número natural$n \ge 1$ que$1 + 2 + 3 + \cdots + n = \frac{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 al$n$. If we know how to do that, adding just one more term ($n+1$) would not be that hard. For example, if $n = 100\text{,}$ suppose we know that the sum of the first 100 numbers is $5050$ (so $1 + 2 + 3 + \cdots + 100 = 5050\text{,}$ 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 + \cdots + 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

Let$P(n)$ be the statement $1 + 2 + 3 + \cdots + n = \frac{n(n+2)}{2}$. We will show that $P(n)$ is true for all natural numbers $n \ge 1$.

Caso base:$P(1)$ is the statement $1 = \frac{1(1+1)}{2}$ which is clearly true.

Caso inductivo: Let$k \ge 1$ be a natural number. Assume (for induction) that $P(k)$ is true. That means $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$. We will prove that $P(k+1)$ is true as well. That is, we must prove that $1 + 2 + 3 + \cdots + k + (k+1) = \frac{(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 tanto$P(k+1)$ is true, so by the principle of mathematical induction $P(n)$ is true for all natural numbers $n \ge 1$.

Obsérvese que en la parte de la prueba en la que$P(k)\text{,}$ probamos$P(k+1)$ a partir se utilizó la ecuación$P(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.

Ejemplo$\PageIndex{2}$

Demostrar que para todos$n \in \N\text{,}$$6^n - 1$ es un múltiplo de 5.

Solución

Nuevamente, comience por comprender la dinámica del problema. ¿Qué hace aumentar$n$ do? Let's try with a few examples. If $n = 1\text{,}$ then yes, $6^1 - 1 = 5$ is a multiple of 5. What does incrementing $n$ to 2 look like? We get $6^2 - 1 = 35\text{,}$ which again is a multiple of 5. Next, $n = 3\text{:}$ but instead of just finding $6^3 - 1\text{,}$ 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 $6^2 - 1$ is a multiple of 5, so $6^2$ 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

Let$P(n)$ be the statement, “$6^n - 1$ is a multiple of 5.” We will prove that $P(n)$ is true for all $n \in \N$.

Caso base:$P(0)$ is true: $6^0 -1 = 0$ which is a multiple of 5.

Caso inductivo: Let$k$ be an arbitrary natural number. Assume, for induction, that $P(k)$ is true. That is, $6^k - 1$ is a multiple of $5$. Then $6^k - 1 = 5j$ for some integer $j$. This means that $6^k = 5j + 1$. Multiply both sides by $6\text{:}$

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

Pero queremos saber sobre$6^{k+1} - 1\text{,}$ so subtract 1 from both sides:

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

Por supuesto$30j+5 = 5(6j+1)\text{,}$ so is a multiple of 5.

Por lo tanto$6^{k+1} - 1$ 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 \in \N$.

Teníamos que ser un poco inteligentes (es decir, usar algo de álgebra) para localizar el$6^k - 1$ interior de$6^{k+1} - 1$ 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 con$n = 1$ o$n = 0$. Podemos comenzar más tarde si es necesario.

Ejemplo$\PageIndex{3}$

Demuéstralo$n^2 \lt 2^n$ para todos los enteros$n \ge 5$.

Solución

Primero, la idea del argumento. ¿Qué pasa cuando aumentamos$n$ 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)^2 - n^2$. 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 incrementa$2^n\text{,}$ since $2^{n+1} = 2^n + 2^n$. When $n$ is large enough, $2^n > 2n + 1$.

Lo que estamos diciendo aquí es que cada vez$n$ 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:

Let$P(n)$ be the statement $n^2 \lt 2^n$. We will prove $P(n)$ is true for all integers $n \ge 5$.

Caso base:$P(5)$ is the statement $5^2 \lt 2^5$. Since $5^2 = 25$ and $2^5 = 32\text{,}$ we see that $P(5)$ is indeed true.

Caso inductivo: Let$k \ge 5$ be an arbitrary integer. Assume, for induction, that $P(k)$ is true. That is, assume $k^2 \lt 2^k$. We will prove that $P(k+1)$ is true, i.e., $(k+1)^2 \lt 2^{k+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 \lt 2^{k+1}\text{,}$ in other words, $P(k+1)$. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 5$.

$\square$

El ejemplo anterior podría recordarte el principio del hipódromo a partir del cálculo, que dice que si$f(a) \lt g(a)\text{,}$ y$f'(x) \lt g'(x)$$f(x) \lt g(x)$ para$x > a\text{,}$ entonces por$x > 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 que$P(k)$ es cierto. Después de todo, estamos tratando de demostrar que$P(n)$ es verdad y la única diferencia está en la variable:$k$ vs$n$. ¿Asumimos que lo que queremos probar es cierto? En realidad no. Asumimos que$P(k)$ es cierto sólo por el bien de probar que eso$P(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: Que$P(n)$ sea la afirmación de que cualquier$n$ 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 que$P(k)$ es verdad. Es decir, supongamos que en cualquier grupo de$k$ canadienses, todos tienen el mismo color de ojos. Consideremos ahora a un grupo arbitrario de$k+1$ canadienses. El primero$k$ de estos debe tener el mismo color de ojos, ya que$P(k)$ es cierto. Además, el último$k$ de estos debe tener el mismo color de ojos, ya que$P(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 todos$n$.

Claramente algo salió mal. El problema es que la prueba que$P(k)$ implica lo$P(k+1)$ asume$k \ge 2$. Sólo hemos demostrado que$P(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 eso$P(k+1)$ es cierto, sería útil saber eso$P(k)$ y$P(k-1)$ y$P(k-2)$ son todos ciertos. Considera el siguiente rompecabezas:

Tienes una barra de chocolate rectangular, compuesta por cuadrados$n$ 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 cuadrados$n$ 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. Si$n=2\text{,}$ debes tener un$1\times 2$ rectángulo, el cual se puede reducir a piezas individuales en una sola rotura. Con$n=3\text{,}$ debemos tener una$1\times 3$ barra, que requiere dos descansos: el primer break crea un solo cuadrado y un$1\times 2$ compás, que sabemos que toma uno (más) break.

Y$n=4\text{?}$ ahora podríamos tener un$2\times 2$ bar, o un$1 \times 4$ bar. En el primer caso, rompa la barra en dos$2\times 2$ barras, cada una de las cuales requiera una rotura más (es decir, un total de tres descansos requeridos). Si empezamos con un$1 \times 4$ bar, tenemos opciones para nuestro primer descanso. Podríamos romper la barra por la mitad, creando dos$1\times 2$ barras, o podríamos romper una sola casilla, dejando una$1\times 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 los$n$ cuadrados en un rectángulo), siempre tendremos el mismo número de descansos requeridos. También parece que ese número es uno menos que$n\text{:}$

Conjetura 2.5.4

Dada una barra de chocolate rectangular$n$ -cuadrada, siempre toma$n-1$ descansos para reducir la barra a cuadrados individuales.

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 que$k+1$.

¿Es válido hacer esta suposición más fuerte? Recuerden, en la inducción estamos tratando de demostrar que eso$P(n)$ es cierto para todos$n$. ¿Y si ese no fuera el caso? Entonces habría algunos primeros$n_0$ para los que$P(n_0)$ era falso. Ya que$n_0$ es el primer contraejemplo, sabemos que eso$P(n)$ es cierto para todos$n \lt n_0$. Ahora procedemos a probar que en realidad$P(n_0)$ es cierto, con base en el supuesto que$P(n)$ es cierto para todos los más pequeños$n$.

Esto es toda una ventaja: ahora tenemos una hipótesis inductiva más fuerte. Podemos suponer que$P(1)\text{,}$$P(2)\text{,}$$P(3)\text{,}$...$P(k)$ es verdad, sólo para demostrar que eso$P(k+1)$ es cierto. Anteriormente, acabamos de asumir$P(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: “Que$P(n)$ sea la declaración...” Luego establezca dos hechos:

1. Caso base: Demostrar que$P(0)$ es cierto.
2. Caso inductivo: Supongamos que$P(k)$ es cierto para todos$k \lt n$. Demostrar que eso$P(n)$ es cierto.

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

Por supuesto, es aceptable reemplazar 0 por una caja base más grande si es necesario. ⁵ 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 necesitan$n-1$ descansos para reducir una barra de chocolate$n$ -cuadrada a cuadrados individuales”.

Caso base: Considerar$P(2)$. Los cuadrados deben estar dispuestos en un$1\times 2$ rectángulo, y requerimos$2-1 = 1$ descansos para reducir esto a cuadrados simples.

Caso inductivo: Se corrige un arbitrario$n\ge 2$ y$P(k)$ se asume que es cierto para todos$k \lt n$. Considera una barra de chocolate rectangular$n$ 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ños$a$ y$b$. Es decir, tenemos una barra de chocolate rectangular$a$ -cuadrada, una barra de chocolate rectangular$b$ -cuadrada, y$a+b = n$.

También sabemos eso$a \lt n$ y$b \lt n\text{,}$ así por nuestra hipótesis inductiva,$P(a)$ y$P(b)$ son ciertos. Para reducir la barra$a$ -sqaure a cuadrados individuales toma$a-1$ descansos; para reducir la barra$b$ -cuadrada a cuadrados individuales toma$b-1$ descansos. Hacer esto da como resultado que nuestra barra original se reduzca a cuadrados simples. Todos juntos se llevó el descanso inicial, más los$a-1$ y$b-1$ descansos, para un total de$1+a-1+b-1 = a+b-1 = n-1$ descansos. Así$P(n)$ es cierto.

Por lo tanto, por fuerte inducción,$P(n)$ es cierto para todos$n \ge 2$.

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

Ejemplo$\PageIndex{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úmero$n\text{,}$ 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

Let$P(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 $n \ge 2$.

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

Caso inductivo: asuma$P(k)$ is true for all $k \lt 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 = m_1 \cdot m_2\text{,}$ with $m_1$ and $m_2$ less than $n$ (and greater than 1). By the inductive hypothesis, $m_1$ and $m_2$ 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 $n \ge 2$.

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 hacer$k$ centavos de franqueo para todos$k \lt n$ siempre y cuando$k \ge 28$. Siempre y cuando$n > 32\text{,}$ esto signifique en particular podemos hacer$k = n-5$ centavos. Ahora agrega un sello de 5 centavos para obtener hacer$n$ centavos.