B.2: Inducción en

Template:MathJaxZach

En su forma más simple, la inducción es una técnica utilizada para demostrar resultados para todos los números naturales. Utiliza el hecho de que al comenzar\(0\) y sumar repetidamente eventualmente\(1\) alcanzamos cada número natural. Entonces, para probar que algo es cierto para cada número, podemos (1) establecer que es cierto para\(0\) y (2) mostrar que siempre que sea cierto para un número\(n\), también lo es para el siguiente número\(n+1\). Si abreviamos “número\(n\) tiene propiedad\(P\)” por\(P(n)\) (y “número\(k\) tiene propiedad\(P\)” por\(P(k)\), etc.), entonces una prueba por inducción que\(P(n)\) para todos \(n \in \Nat\)consta de:

1. una prueba de\(P(0)\), y

2. una prueba de que, para cualquiera\(k\), si\(P(k)\) entonces\(P(k+1)\).

Para que esto quede claro como el cristal, supongamos que tenemos tanto (1) como (2). Entonces (1) nos dice que eso\(P(0)\) es cierto. Si también tenemos (2), sabemos en particular que si\(P(0)\) entonces\(P(0+1)\), es decir,\(P(1)\). Esto se desprende de la declaración general “para cualquiera\(k\), si es que\(P(k)\) entonces\(P(k+1)\)” poniendo\(0\) para\(k\). Entonces por modus ponens, tenemos eso\(P(1)\). De (2) otra vez, tomando ahora\(1\) para\(n\), tenemos: si\(P(1)\) entonces\(P(2)\). Desde que acabamos de establecer\(P(1)\), por modus ponens, tenemos\(P(2)\). Y así sucesivamente. Para cualquier número\(n\), después de hacer estos\(n\) tiempos, finalmente llegamos a\(P(n)\). Entonces (1) y (2) juntos establecen\(P(n)\) para cualquier\(n \in \Nat\).

Veamos un ejemplo. Supongamos que queremos saber cuántas sumas diferentes podemos lanzar con\(n\) dados. A pesar de que pueda parecer una tontería, comencemos con\(0\) los dados. Si no tienes dados solo hay una suma posible que puedes “lanzar”: no hay puntos en absoluto, que suma a\(0\). Entonces el número de diferentes lanzamientos posibles es\(1\). Si solo tienes un dado, es decir,\(n=1\), hay seis valores posibles,\(1\) a través de\(6\). Con dos dados, podemos lanzar cualquier suma de\(2\) a través\(12\), eso es\(11\) posibilidades. Con tres dados, podemos lanzar cualquier número desde\(3\) hasta\(18\), es decir,\(16\) diferentes posibilidades. \(1\),\(6\),\(11\),\(16\): parece un patrón: ¿tal vez la respuesta es\(5n+1\)? Por supuesto,\(5n+1\) es el máximo posible, porque solo hay\(5n+1\) números entre\(n\), el valor más bajo que puedes lanzar con\(n\) dados (todos\(1\)) y\(6n\), el más alto puedes lanzar ( \(6\)todos's).

Teorema\(\PageIndex{1}\)

Con\(n\) los dados se pueden lanzar todos los valores\(5n+1\) posibles entre\(n\) y\(6n\).

Comprobante. \(P(n)\)Sea el reclamo: “Es posible lanzar cualquier número entre\(n\) y\(6n\) usando\(n\) dados”. Para utilizar la inducción, demostramos:

1. La base de inducción\(P(1)\), es decir, con un solo dado, puedes lanzar cualquier número entre\(1\) y\(6\).

2. El paso de inducción, para todos\(k\), si\(P(k)\) entonces\(P(k+1)\).

(1) Se prueba inspeccionando una matriz\(6\) de lados. Tiene los 6 lados, y cada número entre\(1\) y\(6\) aparece en uno de los lados. Por lo que es posible lanzar cualquier número entre\(1\) y\(6\) usando un solo dado.

Para probar (2), asumimos el antecedente del condicional, es decir,\(P(k)\). Esta suposición se denomina hipótesis inductiva. Lo usamos para probar\(P(k+1)\). Lo difícil es encontrar una manera de pensar sobre los posibles valores de un lanzamiento de\(k+1\) dados en términos de los posibles valores de lanzamientos de\(k\) dados más de tiros de tiros del extra\(k+1\) -st die—esto es lo que tenemos que hacer, sin embargo, si queremos usar el inductivo hipótesis.

La hipótesis inductiva dice que podemos obtener cualquier número entre\(k\) y\(6k\) usando\(k\) dados. Si lanzamos un\(1\) con nuestro\((k+1)\) -st morir, esto se suma\(1\) al total. Entonces podemos lanzar cualquier valor entre\(k+1\) y\(6k+1\) lanzando\(5\) dados y luego rodando un\(1\) con el\((k+1)\) -st dado. ¿Qué queda? Los valores\(6k+2\) a través de\(6k+6\). Podemos obtener estos rodando\(k\)\(6\) s y luego un número entre\(2\) y\(6\) con nuestro\((k+1)\) -st morir. Juntos, esto significa que con los\(k+1\) dados podemos lanzar cualquiera de los números entre\(k+1\) y\(6(k+1)\), es decir, hemos probado\(P(k+1)\) usando la suposición\(P(k)\), la hipótesis inductiva. ◻

Muy a menudo usamos la inducción cuando queremos probar algo sobre una serie de objetos (números, conjuntos, etc.) que a su vez se define “inductivamente”, es decir, definiendo el\((n+1)\) -st objeto en términos del\(n\) -th. Por ejemplo, podemos definir la suma\(s_n\) de los números naturales hasta\(n\) por\[\begin{aligned} s_0 & = 0\\ s_{n+1} & = s_n + (n+1)\end{aligned}\] Esta definición da:\[\begin{aligned} s_0 & = 0,\\ s_1 & = s_0 + 1 && = 1,\\ s_2 & = s_1 + 2 && = 1 + 2 = 3\\ s_3 & = s_2 + 3 && = 1 + 2 + 3 = 6, \text{ etc.}\end{aligned}\] Ahora podemos probar, por inducción, eso\(s_n = n(n+1)/2\).

Proposición\(\PageIndex{1}\)

\(s_n = n(n+1)/2\).

Comprobante. Tenemos que probar (1) eso\(s_0 = 0\cdot(0 + 1)/2\) y (2) si\(s_k = k(k+1)/2\) entonces\(s_{k+1} = (k+1)(k+2)/2\). (1) es obvio. Para probar (2), asumimos la hipótesis inductiva:\(s_k = k(k+1)/2\). Usándolo, tenemos que demostrarlo\(s_{k+1} = (k+1)(k+2)/2\).

¿Qué es\(s_{k+1}\)? Por la definición,\(s_{k+1} = s_k + (k+1)\). Por hipótesis inductiva,\(s_k = k(k+1)/2\). Podemos sustituir esto en la ecuación anterior, y luego solo necesitamos un poco de aritmética de fracciones:\[\begin{aligned} s_{k+1} & = \frac{k(k+1)}{2} + (k+1) = {}\\ & = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = {}\\ & = \frac{k(k+1) + 2(k+1)}{2} = {}\\ & = \frac{(k+2)(k+1)}{2}. \end{aligned}\] ◻

La lección importante aquí es que si estás demostrando algo sobre alguna secuencia definida inductivamente\(a_n\), la inducción es el camino obvio a seguir. E incluso si no lo es (como en el caso de las posibilidades de tiradas de dados), puedes usar inducción si de alguna manera puedes relacionar el caso\(k+1\) para con el caso para\(k\).