Inducción matemática

La inducción matemática es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones.

El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación.

Los números naturales se definen de manera inductiva. Es decir, incluso hablando muy informalmente, al describir los números naturales no podemos nombrar a todos los números naturales puesto que son infinitos, lo que hacemos normalmente es decir algo como “1 es un número natural, también 2 y 3 y 4 y así te sigues, si le sumas 1 a un número natural te da otro número natural”.

Base Inducción Matemática

Analogía de los Dominós

Si ponemos todos nuestros dominós parados en una fila, necesitamos sólo asegurarnos de dos cosas para que se caigan:

a) Que exista al menos un dominó que se caiga.

b) Que si un dominó cae, empuja al siguiente. 

 

Para la primera parte, no tiene que ser el primer dominó. Si tiramos el primero, queremos que se caigan todos; pero si tiramos el segundo o el tercero o el quinto, queremos que se caigan todos después el que tiramos.

 

Para la segunda parte tenemos que asegurarnos que la distancia entre cada dos dominós no sea demasiada o que estén en el ángulo correcto, porque si uno solo no empuja al que sigue, entonces no se van a caer todos.  

Los números naturales son como un conjunto infinito pero ordenado de dominós, donde cada dominó tiene escrito un número. Las pruebas por inducción son como ordenar nuestros dominós parados en una fila y ver si es posible empujar alguno para que se caigan todos.

 

a) El caso base es asegurarse de que exista un primer dominó que se caiga.  

b) El paso inductivo es suponer que si cumple para algún entero, cumple para el siguiente. Como sabemos que cumple para el caso base, entonces cumple para el siguiente; como cumple para el siguiente, cumple a su vez para su siguiente y así sucesivamente cumplen todos los enteros a partir del caso base.

Ejemplo: 

Comprobamos con 1

1 + 1 = 1

2 = 1

 

Comprobar con k

K + 1 = k

 

Comprobar con k + 1

K + 1 + 1 = k + 1

 

Inducción Matemática

 

K + k + 1 + 1

2k + 2

Ejercicio: 

Formula

2n = n(n + 1)

Comprobar con 1

 

2(1) = 1 (1 + 1)

2 = 2

 

Comprobar con k

2k = k (k + 1)

 

Comprobar con k + 1

2 (k + 1) = k + 1 (k + 1 + 1)

2 (k + 1) = (k + 1) (k + 2)

 

Inducción Matemática

 

2  (k + 1) + k (k + 1)

(k + 1) (k + 2)