Hoy vamos a conducir por ciudad. Subimos al coche y enseguida nos encontramos el primer semáforo. Está en rojo. Poco después llegamos al segundo semáforo. También está en rojo. Seguimos conduciendo y llegamos al tercer semáforo. ¡Maldición! Otro más en rojo.

¿Significa eso que todos los semáforos que te encuentres estarán en rojo?

Por suerte no (aunque habrá días peores que otros) 😉 Sería verdad si se cumpliera esta ley de Murphy:

 Si te encuentras con un semáforo en rojo, el siguiente también estará en rojo.

En ese caso, como el primero estaba en rojo, el segundo también lo estaría. Como el segundo lo estaba, el tercero también lo estaría y así, uno detrás de otro, nos encontraríamos todos los semáforos en rojo…

Ahora vienen las matemáticas, pero que nadie se asuste, que hoy sólo vamos a usar números naturales.

Primer ejemplo:

• Empezamos por el número (1), para el que se cumple que (1^2<1cdot 10) (un semáforo en rojo).
• Después llegamos al número (2) y vemos que también cumple que (2^2<2cdot 10) (dos semáforos en rojo).
• Seguimos con el (3) y resulta que también (3^2<3cdot 10) (tres semáforos en rojo).

¿Significa eso que para cualquier número natural (n) se va a cumplir que (n^2<ncdot 10) (que todos los semáforos van a estar en rojo)?

Pues no, porque para (10) tenemos que (10^2) no es menor que (10cdot 10) (después de (9) semáforos, el siguiente ya no está en rojo).

Lo que pasa aquí (igual que con los semáforos) es que no es cierta la correspondiente ley de Murphy, que en este caso diría

Si para un número (k) se cumple que (k^2<kcdot 10) (un semáforo estaba en rojo) entonces para el siguiente número, (k+1), también se cumple que ((k+1)^2<(k+1)cdot 10) (el siguiente semáforo también estará en rojo).

y que, como hemos visto, falla para (k=9).

Segundo ejemplo:

• Empezamos por el número (1), para el que se cumple que (4^1 -1) es múltiplo de (3) (un semáforo en rojo).
• Después llegamos al número (2) y vemos que también cumple que (4^2 -1) es múltiplo de (3) (dos semáforos en rojo).
• Seguimos con el (3) y resulta que también (4^3 -1) es múltiplo de (3) (tres semáforos en rojo).

¿Significa eso que para cualquier número natural (n) se va a cumplir que (4^n -1) es divisible por (3) (que todos los semáforos van a estar en rojo)?

Puedes probar con unos cuantos números más y comprobarás que para todos se cumple… pero eso no garantiza nada porque ¿quién te dice que no falla justo alguno de los que no has comprobado?

Así que hemos llegado a un punto en el que estamos más o menos convencidos de que la propiedad es cierta, pero no podemos probar con toooodos los números (porque hay infinitos). Entonces es momento de preguntarse si se cumple la correspondiente ley de Murphy, que en este caso diría

Si para un número (k) se cumple que (4^k -1) es divisible por (3) (un semáforo estaba en rojo) entonces para el siguiente número, (k+1), también se cumple que (4^{k+1} -1) es divisible por (3) (el siguiente semáforo también estará en rojo).

Como hemos visto que el primer semáforo estaba en rojo, si además se cumple esta ley de Murphy entonces podremos estar seguros de que todos los semáforos estarán en rojo. Es decir, que la propiedad se cumplirá para cualquier número natural.

Pues venga, vamos a ver entonces que esta ley de Murphy sí se cumple.

Queremos ver que (4^{k+1} -1) es divisible por (3)  sabiendo que (4^k -1) es divisible por (3):

• Para ello el truco es escribir (4^{k+1}-1) de manera que aparezca (4^k -1), que es para el que sabemos algo, así que podemos ponerlo como:

(4^{k+1}-1= 4cdot 4^k -1 =4cdot 4^k -4 +3 = 4cdot (4^k -1) +3).

• Ahora vamos a ver que los dos sumandos de la derecha son divisibles por (3):
  • Por un lado, sabemos que (4^k -1) es divisible por (3) (el semáforo que ya estaba en rojo), así que el primer sumando es divisible por (3).
  • Por otro lado, el segundo sumando también es divisible por (3) porque de hecho es igual a (3).

• Entonces la suma de la derecha, que era igual al (4^{k+1}-1) que teníamos a la izquierda (el siguiente semáforo), es suma de dos cosas divisibles por (3), así que también es divisible por (3) (el siguiente semáforo también estará en rojo). Y esto era lo que queríamos ver.

Así que puedes probar con todos los números naturales (n) que quieras y no encontrarás ninguno para el que no se cumpla que (4^n -1) sea divisible por (3), te lo garantizan las matemáticas. 🙂

Para saber más:

En matemáticas esta técnica se llama inducción (sí, como la de las cocinas) y es una de las técnicas que se usan para poder garantizar que una propiedad se cumple. Es decir, para demostrar esa propiedad.

Algunas de las propiedades que pueden demostrarse usando inducción son, por ejemplo:

• Que la suma de los números desde (1) hasta (n) es (frac{ncdot(n+1)}{2}).
• Que la suma de los ángulos interiores de un polígono convexo de (n) lados es ( (n-2)cdot 180) grados.

Pero aquí tienes muchas más. Si te animas a hacer tu propia demostración usando inducción, cuéntanoslo en los comentarios.

También puede usarse inducción para determinar el número de movimientos necesarios para resolver el rompecabezas de las torres de Hanoi.

Por último, es interesante saber que hay una variante de la inducción llamada inducción fuerte, con la que se pueden demostrar otro tipo de propiedades. Por ejemplo, que cualquier número natural puede descomponerse como producto de números primos (pero eso lo dejaremos para otro día).

Imágenes: Sarah Jane en Flickr y aussiegall en Wikimedia Commons.

Nota 1: Permitidme dedicar esta entrada a la memoria de mi compañero de departamento y comidas, José Antonio Malpica Velasco, al que ayer se le apagaron los semáforos.

Nota 2: Esta entrada  se pudo votar en Menéame.

Puedes seguirnos en Twitter, Facebook y Google +.