Inducción matemática
La inducción matemática es una técnica de prueba matemática . Se utiliza esencialmente para probar que una afirmación P ( n ) se cumple para todo número natural n = 0, 1, 2, 3, ... ; es decir, el enunciado general es una secuencia de infinitos casos P (0), P (1), P (2), P (3), ... . Las metáforas informales ayudan a explicar esta técnica, como caer fichas de dominó o subir una escalera:
La inducción matemática demuestra que podemos subir tan alto como queramos en una escalera, demostrando que podemos subir al peldaño inferior (la base ) y que de cada peldaño podemos subir al siguiente (el peldaño ).
Una demostración por inducción consta de dos casos. El primero, el caso base (o base ), prueba el enunciado para n = 0 sin asumir ningún conocimiento de otros casos. El segundo caso, el paso de inducción , prueba que si el enunciado se cumple para cualquier caso dado n = k , entonces también se debe cumplir para el siguiente caso n = k + 1. Estos dos pasos establecen que el enunciado se cumple para todo número natural n . El caso base no necesariamente comienza con n = 0, pero a menudo con n = 1, y posiblemente con cualquier número natural fijo n = N , estableciendo la verdad del enunciado para todos los números naturales n ≥ N .
El método se puede extender para probar declaraciones sobre estructuras bien fundamentadas más generales , como árboles ; esta generalización, conocida como inducción estructural , se utiliza en lógica matemática e informática . La inducción matemática en este sentido amplio está estrechamente relacionada con la recursividad . La inducción matemática es una regla de inferencia utilizada en pruebas formales y es la base de la mayoría de las pruebas de corrección para programas de computadora. [3]
Aunque su nombre pueda sugerir lo contrario, la inducción matemática no debe confundirse con el razonamiento inductivo tal como se usa en filosofía (ver Problema de la inducción ). El método matemático examina un número infinito de casos para probar un enunciado general, pero lo hace mediante una cadena finita de razonamiento deductivo que involucra a la variable n , que puede tomar un número infinito de valores. [4]
En 370 aC, el Parménides de Platón puede haber contenido un ejemplo temprano de una prueba inductiva implícita. [5] Una técnica iterativa opuesta, contando hacia abajo en lugar de hacia arriba, se encuentra en la paradoja de sorites , donde se argumentó que si 1,000,000 de granos de arena formaban un montón, y al quitar un grano de un montón, quedaba un montón, entonces un solo grano de arena (o incluso ningún grano) forma un montón. [6]
