¿Estamos utilizando correctamente la inducción matemática?

Question

Hace poco tuve una conferencia en un curso de Informática que implicaba el uso de la inducción. La principal discrepancia radica en que algunos estudiantes y yo pensamos que nuestra prueba debería ser suficiente, pero nuestro instructor argumenta que hay lagunas en nuestra lógica. En realidad, lo que queremos es entender por qué puede haber lagunas en nuestra lógica.

El problema: Demostrar que para $K\geq8$ el valor $K$ puede estar formado por la suma de dos tipos diferentes de monedas con valor $3$ y $5$ .

Nuestra prueba: Demostramos que esto es cierto para $K=8,9,10$ .

Dejemos que $m$ denotan una $3$ moneda y $n$ denotan una $5$ moneda.

$K=8=3+5=m+n$

$K=9=3+3+3=3m$

$K=10=5+5=2n$

Así que hemos establecido que esto es válido para $K=8,9,10$ . Dejemos que $N>10$ . Supongamos que nuestra hipótesis se mantiene para $8\leq K\leq N$ . Queremos demostrar que esto implica que se mantiene para $K=N+1$ .

Así que, $K=N+1=(N-2)+3$ y por nuestra hipótesis inductiva, $N-2$ puede estar formado por 3 monedas y 5 monedas, (ya que $N>10$ ), y claramente $3$ es simplemente un 3-coin., por lo tanto $K=N+1$ puede estar formado por 3 monedas y 5 monedas.

Hemos establecido nuestro caso base ( $K=8,9,10$ ) y se ha demostrado que asumiendo $K=N$ se mantiene para $N\geq10$ Esto implica que $K=N+1$ se mantiene, y por tanto, por el principio de inducción matemática, cualquier valor $K\geq8$ puede estar formado por 3 monedas y 5 monedas.

¿Es nuestro argumento poco sólido? El desacuerdo de nuestro profesor fue que para demostrarlo de esta manera, en realidad debemos demostrar para 3 secuencias diferentes, es decir, 3 secuencias separadas en las que nuestro $K$ valor es $8,11,14,...$ y $9,12,15,...$ y $10,13,16,...$ respectivamente. Afirma que esto se debe a que la inducción debe se basan únicamente en el plazo inmediatamente anterior, es decir $A_N$ implica $A_{N+1}$ implica $A_{N+2}$ ... pero que nuestra prueba sólo se refiere $A_{N+1}$ a $A_{N-2}$ . ¿Es así como funciona la inducción?

Creemos que esto se debe tal vez a la forma en que se definen la inducción y las secuencias en nuestro curso, pero basándonos en nuestros cursos anteriores de matemáticas, creemos que esto debería ser suficiente.

Answer 1

En primer lugar tenemos este principio: tomar cualquier propiedad (matemáticamente bien formada) $P(n)$ , en función de $n$ si puede demostrar que

$$P(0)$$

$$\forall n \in \mathbb{N}\, P(n) \implies P(n+1)$$

de esto se puede concluir $$\forall n \in \mathbb{N}\, P(n)$$

A partir de este principio de inducción se pueden derivar muchos otros principios de inducción: inducción finita, inducción hacia atrás, etc., pero sólo necesitamos dos de los siguientes:

Se puede partir de cualquier otro número natural que no sea $0$ :

$$P(k)$$

$$\forall n \in \mathbb{N_{\ge{k}}}\, P(n) \implies P(n+1)$$

$$\forall n \in \mathbb{N_{\ge{k}}}\, P(n)$$

y un principio de inducción fuerte:

Supongamos que usted prueba

$$\forall n \in \mathbb{N_{\ge{k}}}\,\Bigl(\forall k \in \mathbb{N_{\ge{k}}}\, [k < n \implies P(k)]\Bigr) \implies P(n)$$

entonces se puede concluir

$$\forall n \in \mathbb{N_{\ge{k}}} P(n)$$

En palabras, el primer principio de la inducción matemática funciona así: Se demuestra el caso base (¡es absolutamente necesario hacerlo!) y después se demuestra que la propiedad se cumple para algún número $n$ sabiendo sólo que es válida para el número anterior $n-1$ ¡! Y si se trabaja con el principio de inducción fuerte no sólo que no es necesario demostrar el caso base - también se puede considerar que la propiedad se mantiene para todos los números anteriores ¡! ¿No es genial? Y esto es exactamente lo que hiciste en tu prueba por inducción fuerte:

Supongamos que $P(n)$ significa que $n$ puede reescribirse como la suma de $2$ y $3$ 's.

Así que toma cualquier número $n \ge 8$ . Se supone que para todos $8 \le k < n$ esa propiedad se mantiene y luego se demuestra que también se mantiene para $n$ . Esto se hace por casos:

si $n = 8$ entonces $P(n)$

si $n = 9$ entonces $P(n)$

si $n = 10$ entonces $P(n)$

si $n > 10$ entonces $8 \le n - 3 < n$ y, por tanto, por suposición $P(n-3)$ de esto se desprende $P(n)$ ya que sólo tiene una más $3$ .

Por lo tanto, usted ve que $P(n)$ es válida en todos los casos, por lo que por el principio de inducción fuerte se puede concluir $\forall n \in \mathbb{N_{\ge{8}}}\, P(n)$

Ahora veamos cómo se podría proceder utilizando la primera inducción (ordinaria):

La idea es utilizar la inducción ordinaria 3 veces para demostrar que la propiedad se mantiene para 3 secuencias diferentes de números naturales, es decir para $8 + 3n$ , $9+3n$ , $10+3n$ $n \ge 8$ de esto podrás concluir que en los hechos se sostiene para cualquier número natural mayor que $8$ ya que definitivamente estará en una de esas secuencias.

Mostraré cómo hacerlo para la primera, las otras dos están probadas al pie de la letra.

Demostramos $$\forall n \in \mathbb{N} \mbox{ we have } P(8+3n)$$

$$n = 0, \mbox{ we certainly have } P(8)$$

Ahora supongamos que tenemos $P(8+3k)$ para algunos $k \in \mathbb{N}$ entonces tenemos que demostrar que $P[8 + 3(k+1)]$ .

Pero $8+3(k+1) = (8 + 3k) + 3$ y como $8 + 3k$ podría reescribirse como una suma de $3$ y $2$ 's entonces $(8+3k)+3$ también se puede reescribir de esta manera ya que es la misma pero tiene un 3 más. Así, tenemos $P[8 + 3(k+1)]$ y así por la inducción ordinaria se puede concluir $$\forall n \in \mathbb{N}\, P(8+3n)$$

Answer 2

Tenga en cuenta que $P(N)$ no implica $P(N+1)$ de forma inmediata (por ejemplo, no es inmediatamente claro por qué $17$ debería tener la propiedad sólo porque $16$ tiene la propiedad ... aunque véase la prueba inductiva que doy un poco más adelante en este post).

Por lo tanto, si usted tienen utilizar la inducción débil, lo obvio es hacer lo que hace tu profesor, y hacer $3$ pruebas inductivas débiles separadas:

1. Demostrar que $P(8)$ y demostrar que para todo $n$ : $P(8+3n)\Rightarrow P(8+3(n+1))$

2. Demostrar que $P(9)$ y demostrar que para todo $n$ : $P(9+3n)\Rightarrow P(9+3(n+1))$

3. Demostrar que $P(10)$ y demostrar que para todo $n$ : $P(10+3n)\Rightarrow P(10+3(n+1))$

Combinadas, estas pruebas demuestran que para todo $n \ge 8$ : $P(n)$

Otra posible prueba inductiva débil es ésta:

Demostrar que $P(8)$ , $P(9)$ y $P(10)$ mantener. Supongamos ahora que $P(N)$ se mantiene con $N \ge 10$ . Porque $N \ge 10$ sabemos que para formar $N$ necesitamos utilizar al menos un $5$ o (si no usamos ninguna $5$ en absoluto), al menos tres $3$ 's. Pero si $P(N)$ se forma utilizando al menos una $5$ , entonces podemos formar $P(N+1)$ quitando una $5$ y añadiendo dos $3$ 's. Y si usamos al menos tres $3$ para formar $P(N)$ , entonces podemos formar $P(N+1)$ quitando tres $3$ y añadiendo dos $5$ 's. Así que, de cualquier manera, podemos formar $P(N+1)$

Tu método utiliza la inducción fuerte, y por supuesto es una prueba matemática perfectamente buena también ... pero tal vez tu profesor había insistido en que usaras la inducción débil?

Answer 3

Si la propiedad es verdadera para todos los $k$ tal que $$8\le k\le n,$$ donde $10\le n$ , entonces es cierto para $n-2$ y es cierto para $n+1$ y para todos $k$ tal que

$$8\le k\le n+1.$$

Answer 4

Olvídate de la inducción por un segundo.

Digamos que $P(K)$ se mantiene si existe $c,d \geq 0$ tal que $K=3c+5d$ . Su objetivo es demostrar que $P(K)$ es válida para todos los $K \geq 8$ .

Si sólo quisieras probar $P(8)$ (por ejemplo), entonces puedes escribir una prueba para eso ( $8=3+5$ ). Sin embargo, no se puede escribir una prueba para $P(K)$ para todos $K \geq 8$ porque simplemente no hay tiempo suficiente para hacerlo. Lo que se puede hacer en su lugar es escribir un programa informático (algoritmo) que consiga $K \geq 8$ como entrada y produce una prueba para $P(K)$ . Más concretamente, en la entrada $K$ produce dos números $c,d$ tal que $K=3c+5d$ . De hecho, su pregunta ya contiene un programa de este tipo $A$ :

• si $K = 8$ entonces la salida $(1,1)$
• si $K = 9$ entonces la salida $(3,0)$
• si $K = 10$ entonces la salida $(0,2)$
• si $K > 10$ entonces calcula $(c,d) = A(K-3)$ y la salida $(c + 1, d)$

Ahora, tenemos que argumentar que $A$ funciona correctamente. Para los tres casos básicos esto es obvio. Para el caso recursivo argumentamos lo siguiente. Sea $K > 10$ y que $(c,d) = A(K-3)$ . El algoritmo $A$ es correcto para la entrada $K$ si $$ K = 3(c+1) + 5d $$

Como ya ha observado: si $A(K-3)$ es correcto, es decir $K-3 = 3c+5d$ entonces lo anterior también es válido. Por lo tanto, hemos reducido la demostración de que $A(K)$ es correcto para demostrar que $A(K-3)$ es correcto. Observe que $K-3 > 7$ porque de lo contrario contradiría nuestra suposición $K > 10$ . Si $K-3 \leq 10$ entonces la corrección se deduce de los casos base. En caso contrario ( $K-3>10$ ), podemos aplicar el mismo argumento para ver que: $A(K-3)$ es correcto si $A(K-6)$ es correcto. Si $K-6$ sigue siendo mayor que 10 podemos aplicar el mismo argumento y comprobar si $A(K-9)$ es correcto y así sucesivamente... no es difícil argumentar que finalmente se llega a un caso base. Por lo tanto, $A$ funciona correctamente.

Lo que quiero decir es que el principio de inducción no es una técnica de prueba misteriosa, sino que se deriva naturalmente de la perspectiva algorítmica anterior. Esencialmente, una prueba por inducción es una representación compacta de un algoritmo recursivo que genera las pruebas y una prueba de corrección de ese algoritmo. El mensaje que hay que extraer es: si haces una prueba por inducción y no estás seguro de que sea correcta, intenta articular el algoritmo recursivo que produce las pruebas, prueba el algoritmo para algunos casos y luego demuestra su corrección (no olvides argumentar que al final siempre se alcanza un caso base).

Answer 5

Tengo curiosidad por saber cuál es la solución aprobada por el profesor por "inducción débil". Porque la prueba obvia es errónea:

N=8: 8=3+5.

Paso de inducción: Supongamos que $N=3a + 5b$ . Entonces $N+1 = 3(a+2) + 5(b-1)$ .

Dado que el enunciado pide una "suma" de 3's y 5's parece claro que debemos mostrar $N=3a + 5b$ para algunos $a\ge0$ y $b\ge0$ . Si es así, el simple argumento anterior es erróneo; si $N=3a + 5b$ con $b=0$ entonces $b-1<0$ .

Una versión correcta es un poco más complicada:

Paso de inducción: Supongamos que $N=3a+5b$ . Si $b>0$ entonces $N+1=3(a+2)+5(b-1)$ .

Si $b=0$ : Desde $N\ge8$ debemos tener $a\ge3$ . Así que podemos escribir $N+1=3(a-2)+5$ .