Comprobar los primeros cien casos de una secuencia todavía no demuestra que el caso ciento uno funcione.
La inducción permite justificar una propiedad para todos los valores de una secuencia cuando puedes establecer un inicio y demostrar que cada paso válido conduce al siguiente. La recursión usa una idea paralela para definir objetos o procesos a partir de versiones más pequeñas de sí mismos.
📷 Antes de comenzar
Quieres justificar una propiedad P(n) para todos los enteros n a partir de 1. ¿Qué dos piezas forman la estructura básica de una prueba por inducción?
Objetivo didáctico
Al terminar esta lección podrás aplicar inducción matemática y definiciones recursivas para formalizar y verificar procesos repetitivos, distinguiendo el caso base, la hipótesis inductiva, el paso inductivo y la condición que hace terminar una definición recursiva.
Introducción
En la lección anterior aprendiste que una colección de ejemplos no sustituye una prueba general. Ahora aparece una pregunta natural: ¿cómo demostrar una afirmación que depende de un número de pasos, como el tamaño de una secuencia, la profundidad de una estructura o el número de iteraciones de un proceso?
La inducción matemática responde cuando los casos pueden organizarse de forma ordenada y el paso de un caso al siguiente conserva una propiedad. Su lógica se parece a una cadena: necesitas un primer eslabón firme y una regla que garantice la conexión entre eslabones consecutivos.
La recursión, en cambio, es una forma de definir: especifica uno o más casos base y describe los casos restantes en términos de casos más pequeños. En computación esta idea aparece en algoritmos y estructuras, pero en esta asignatura inicial se trabajará primero con expresiones y secuencias sencillas para no cargar la notación.
Desarrollo del tema
Inducción: base, hipótesis y paso
Una prueba por inducción empieza con una propiedad P(n). El caso base demuestra que la propiedad es cierta para el primer valor del dominio, por ejemplo n=1. Este paso no es ceremonial: si la cadena no comienza, el mecanismo de transmisión no demuestra nada sobre los casos posteriores.
Después se plantea la hipótesis inductiva: supones que P(k) es verdadera para un k permitido. Esa suposición es temporal y tiene un propósito concreto: usarla para demostrar P(k+1). No estás afirmando que la propiedad ya sea cierta para todos los valores.
El paso inductivo muestra la transición. Debe indicar de forma explícita dónde se usa P(k). Si la demostración de P(k+1) no utiliza la hipótesis inductiva, revisa el argumento: quizá existe una prueba directa independiente o quizá falta el vínculo que hace funcionar la inducción.
💡 Hipótesis inductiva
Suposición temporal de que P(k) es verdadera para un valor permitido k. Se usa para justificar el siguiente caso, no como conclusión general.
📚 Tres ideas que no conviene mezclar
Verifica el primer caso.
Usa la hipótesis para obtener el siguiente caso.
La propiedad se propaga desde la base.
Figura 1. Secuencia lógica de una prueba por inducción.
Prueba tú: para la afirmación “1+2+…+n = n(n+1)/2”, escribe solo el caso base y la hipótesis inductiva. Después señala qué expresión deberías transformar en el paso k+1. No completes la prueba hasta tener claras esas tres piezas.
Recursión: definir desde casos más pequeños
Una definición recursiva necesita al menos dos elementos: un caso base cuyo valor se conoce directamente y una regla recursiva que exprese un caso en términos de otro más pequeño. Por ejemplo, una suma acumulada puede definirse con S(1)=1 y S(n)=n+S(n−1) para valores posteriores.
La reducción debe acercarse al caso base. Si una regla llama a un caso del mismo tamaño o mayor sin una condición adicional, puede no terminar. En un programa eso se manifiesta como llamadas que continúan sin alcanzar una salida; en matemáticas, como una definición que no determina de forma efectiva los valores esperados.
Recursión e inducción se relacionan porque ambas aprovechan una estructura por etapas. La recursión define o construye; la inducción demuestra una propiedad sobre los objetos o procesos organizados de esa manera. No son sinónimos.
🔀 Escenario ramificado
Quieres definir una función recursiva que calcule la suma de los enteros desde 1 hasta n. ¿Qué decisión tomas primero?
Decide: toma un proceso sencillo de tu caso de E1 que pueda repetirse. Especifica qué información bastaría para detenerlo y qué parte del problema se reduce en cada paso.
Conectar inducción y recursión sin confundirlas
Supón que defines recursivamente el número de operaciones de un proceso y luego quieres demostrar una fórmula cerrada para ese número. La definición recursiva describe cómo obtener el siguiente valor; la inducción puede utilizar esa estructura para probar que la fórmula propuesta coincide con todos los valores generados.
La conexión funciona porque ambos razonamientos comparten una noción de progreso: existe un punto de inicio y un mecanismo que relaciona etapas. Sin embargo, sus preguntas son distintas. Para recursión preguntas “¿cómo obtengo este caso a partir de uno menor?”. Para inducción preguntas “si la propiedad vale en una etapa, ¿por qué debe valer en la siguiente?”.
En el trabajo computacional conviene escribir ambas piezas por separado. Primero documenta la regla que ejecutaría o describiría el proceso. Después, si necesitas garantizar una propiedad general —por ejemplo, que el número de pasos satisface una expresión— formula esa propiedad y construye la prueba inductiva.
📷 Control de comprensión
Una definición recursiva tiene un caso base correcto, pero cada caso n se define usando el caso n+1. ¿Cuál es el problema principal?
Aplica: revisa el proceso repetitivo de tu proyecto. Escribe una versión recursiva básica y, por separado, una propiedad sobre ese proceso que podría demostrarse por inducción. Si ambas frases son idénticas, probablemente estás mezclando definición y demostración.
Conclusión
La inducción convierte una transición local en una garantía general siempre que exista un caso base y un paso inductivo válido. La recursión define objetos o procesos mediante casos más pequeños y necesita una ruta clara hacia la base. Comprender la diferencia evita dos errores frecuentes: creer que una larga lista de ejemplos prueba una propiedad y escribir definiciones recursivas que nunca alcanzan una condición de salida.
En la siguiente lección cambiaremos de pregunta. En vez de centrarnos en cómo avanza un proceso, aprenderemos a organizar sus objetos mediante conjuntos y a representar correspondencias entre ellos mediante funciones.
🔭 Para seguir aprendiendo
- En el proceso que elegiste, ¿qué información permanece igual en cada repetición y qué información cambia? Esa separación te ayudará a decidir qué convertir en conjuntos y funciones.
Actividad de aprendizaje autónoma
Etapa 2 · Formaliza un proceso del caso mediante inducción o recursión. Retoma el caso y la afirmación de E1. No cambies de problema: identifica dentro de ese mismo caso un proceso repetitivo o una cantidad que dependa de etapas sucesivas.
- De dónde vienes. Resume el caso, la afirmación y el método de prueba usados en E1; señala una decisión que mantienes y una que corregirías si encontraste una debilidad.
- Define el proceso. Establece un caso base y una regla recursiva, o formula una propiedad P(n) que describa su comportamiento.
- Aplica el método. Si elegiste inducción, escribe caso base, hipótesis y paso inductivo. Si elegiste recursión, especifica base, regla y cómo cada llamada o dependencia se acerca a la base.
- Qué decides. Justifica por qué inducción, recursión o una combinación de ambas representa mejor el proceso seleccionado.
- Qué documentas. Registra fuentes y cualquier consulta a inteligencia artificial, indicando qué aceptaste, qué descartaste y cómo verificaste el razonamiento.
🗂 Planifica tu etapa
✔ Evidencia de logro
- Referencia explícita a la entrega E1 y revisión de al menos una decisión previa.
- Caso base claramente identificado.
- Paso inductivo o regla recursiva con condiciones de aplicación.
- Justificación de la estrategia elegida y comprobación de que el proceso progresa correctamente.
- Registro de fuentes y contraste de cualquier consulta a sistemas de inteligencia artificial.
Si tu procedimiento produce correctamente los primeros diez resultados, ¿qué argumento adicional necesitas para sostener que seguirá comportándose como esperas en una etapa arbitraria?
Referencias bibliográficas
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). The MIT Press.
- Grimaldi, R. P. (2025). Discrete and combinatorial mathematics: An applied introduction (5th ed., Global ed.). Pearson.
- Lehman, E., Leighton, F. T., & Meyer, A. R. (s. f.). Mathematics for computer science. Massachusetts Institute of Technology OpenCourseWare.
- Rosen, K. H. (2019). Discrete mathematics and its applications (8th ed.). McGraw Hill.