Métodos de demostración. Inducción o cómo pensar para no trabajar.

Nada mejor para explicar matemáticas que explicar cómo se hacen matemáticas. Dejando fuera los cotilleos del mundillo (como las demostraciones en sueños de Ramanujan) las demostraciones se presentan en muchas formas, como la inducción.

La inducción (no la física) se basa en demostrar algo para un número n sabiendo cierto un caso base y demostrando que puede pasarse de un caso al k+1 de forma lógica.

Para que nos entendamos, un ejemplo:

Probar que 1+2+3+\ldots +(n-2)+(n-1)+n =\frac{n(n+1)}{2}  para un n dado.

Podemos ir sumando número a número, aunque si tomamos n=10^{1000} puede que no podamos demostrarlo ni con un ordenador doméstico (que, de hecho, en un principio no podemos sin hacer algún truquillo que implicaría destrozarlo), y mucho menos con una calculadora. Intentemos hacer algo que sabemos, a ver qué pasa, por ejemplo para n=1:

1=\frac{1(1+1)}{2}

Fácil, lo sé, las matemáticas son así. Bueno, ahora probemos que si es cierto para k lo será para k+1:

1+2+3+\ldots+(k-1)+k+(k+1)=[1+2+3+\ldots+(k-1)+k]+(k+1)

Nada del otro mundo, ponemos un paréntesis, sigamos.

[1+2+3+\ldots+(k-1)+k]+(k+1)=[ \frac{k(k+1)}{2} ]+(k+1)

Ésto es lo que hemos supuesto, que era cierto para k, así que aplicamos la formulita (esto se llama hipótesis de inducción, HI). Probemos a sumar a ver qué pasa.

[\frac{k(k+1)}{2}]+\frac{2(k+1)}{2}=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+2)(k+1)}{2}

Donde el último paso se hace sacando factor común k+1. ¿Todo claro? ¡Pues ya está!

QED

¿Por qué? Sencillo. Hemos probado que es cierto para 1; pero también para dos porque podemos hacer el paso de uno a dos (HI de k+1 tomando k=1); pero también para tres pues podemos hacer el paso de dos a tres; y para 4,5,6,…,n-1. Os dejo pensar por qué es cierto para n 😉 .

Esta inducción se llama inducción a secas o inducción débil porque pruebas que suponiendo cierto el caso anterior lo es el posterior. Hay otro tipo que se basa en probar que suponiendo cierto todos los casos anteriores lo es el siguiente, inducción fuerte o completa. Es evidente que usando la fuerte podemos demostrar cualquier cosa que se pueda razonar usando la débil, pues el caso inmediatamente anterior también está en todos los anteriores, aunque el “recíproco no es cierto” (ATENCIÓN, frase de la leche en matemáticas) ya que puede que necesitemos dos, tres, todos los casos anteriores o algún caso que no sea el inmediatamente anterior para demostrar el siguiente, por ejemplo:

Todo número natural no nulo puede escribirse como suma de potencias de dos con exponentes distintos.

Hay 10 tipos de personas, las que conocen el binario y las que no me entienden... Budumtss

Hay 10 tipos de personas, las que conocen el binario y las que no me entienden… Budumtss

En primer lugar, los números naturales son 0,1,2,3,4,5,6,7,8,9,10,11… Y lo que queremos demostrar es que, por ejemplo, 46=2^1+2^2+2^3+2^5

Tiene pinta de que saldrá por inducción, probemos el caso base:

1=2^0

 Si recordamos que cualquier número elevado a cero es uno, es cierto (y si no también).

Probemos por la inducción que conocemos, si es cierto para k, lo será para k+1. Esto es fácil, pues si es cierto para y 1=2^0, entonces solo tenemos que sumar a la forma en que esté k como suma de potencias de dos y sumarle 2^0. ¡Pues no! Porque tenemos que demostrar que es suma de potencias de dos con exponentes distintos. Puede que en su descomposición n-1 use el cero como exponente (si n-1 es impar lo usará seguro), así que no podemos sumar 2^0 pues repetiríamos exponente.

Eso sí, si n-1  es par (con lo que sería impar) sí podemos usar 2^0 para conseguir n (pues en la descomposición de un número par de esta forma no puede aparecer el uno, o 2^0, porque nos saldría impar).¿Y si n es par? Entonces n=2k para algún k pero para un k menor que n. Damas y caballeros, ya está:

Si es cierto para k lo será para n, pues bastaría sumarle uno a cada exponente de (ya que recordemos que a\cdot a^b= a^{b+1}) y como estos ya eran distintos lo seguirán siendo al sumarle uno a cada uno.

QED

Hemos visto que la inducción débil no valía, y la fuerte sí. Podéis meditar la demostración, sé que suena raro que tomes un número que está por la mitad como cierto. Recordad que para llegar a ese k que es la mitad que n hemos usado también los anteriores a k, y para éstos también los anteriores. Hagamos una construcción rápida:

Para 1 es cierto, para dos es cierto porque es par y 2=1\cdot2=2^0\cdot2=2^1, para tres es cierto pues 3=2+1=2^1+2^0, para cuatro razonamos que 4=2\cdot2=2^1\cdot2=2^2, para cinco 5=4+1=2^2+2^0, seis 6=3\cdot2=(2^1+2^0)\cdot2=2^2+2^1, etc.

Una pregunta típica cuando no se conocen mucho las matemáticas (y que no tiene nada de malo hacer si no es con mala baba, pues puedes darte con un canto en los dientes) es ¿Y esto pa’ qué? En este caso acabamos de justificar que el sistema binario se puede sustentar de forma lógica, ya hablaremos de esto en profundidad, pero pensad que si usas un exponente para la descomposición en sumas de potencias de dos lo asignas como un uno (encendido) y si no como un cero (apagado).

Las mates están ahí fuera

Las mates están ahí fuera

Resumiendo, y como a mí me gusta imaginarlo, la inducción es una especie de efecto dominó infinito en el que todas las fichas caen al unísono una vez que empujas la primera.

A propósito, el QED que escribo a veces significa quod erat desmostrandum, que en castellano viene a ser algo parecido a lo que se estraba demostrando. Está medio en desuso y yo lo utilizo por marcar tendencia, soy una fashion victim…

¡No te olvides de seguir a Scire Science en Facebook y Twitter!

Anuncios

Acerca de NullSetCpp

Estudiante de matemáticas e interesado por las ciencias, las artes marciales, la filosofía y el chocolate con leche.
Esta entrada fue publicada en Matemáticas y etiquetada , , , , , , , , , , . Guarda el enlace permanente.

7 respuestas a Métodos de demostración. Inducción o cómo pensar para no trabajar.

  1. Alejandro dijo:

    Alejandro, quise decir justo al reves. Muestra cosas simples para hacer ver la complejidad y la riqueza que hay atrás.

    Me gusta

  2. Alejandro dijo:

    Me gustó. Le da mas importancia al arbol que al bosque.

    Me gusta

  3. Pingback: Bases numéricas y bases americanas: matemáticas letales | Scire Science

  4. Pingback: El intervalo [0,1] es gordo. Muy gordo. | Scire Science

  5. Pingback: Cuando las matemáticas se ponen agresivas: el cañón de Gauss | Scire Science

  6. Pingback: ¿Qué narices es el cero? | Scire Science

  7. Pingback: (I)Métodos de demostración. Inducción o cómo pensar para no trabajar. | Scire Science

¿Alguna duda? ¿Quieres matizar? No dudes, pues, en comentar.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s