Inducción

De Departamento de Informatica
Saltar a: navegación, buscar

Definicion Matemática

La induccion es un razonamiento que permite demostrar una infinidad de proposiciones.

Premisa mayor: El número entero a\, tiene la propiedad P\,.
Premisa menor: El hecho de que cualquier número entero n\, tenga la propiedad P\, implica que n+1\, también la tiene (que se anota n \Rightarrow n + 1).
Conclusión: Todos los números enteros a partir de a\, tienen la propiedad P\,.

Demostraciones por inducción

Llamemos P_n\, a la proposición, donde n\, es el rango.

Caso base: Demostrar que P_0\, con n=1\, es cierta.
Hipótesis: Suponemos P_n\, como cierta y le damos el valor de hipótesis inductiva.
Demostración: Demostrar que para P_{n+1}\, también es cierta, utilizando la hipótesis inductiva.
Conclusión: Si P_0\, es cierto y P_{n+1}\, tambien es cierto, podemos concluir que P_n\, es cierto para todo natural n\,.

Ejemplo

Demostrar 1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} \le \frac{n}{2}+1\,

\forall n \in \mathbb{N}; n \geq 1\,

Solucion:

  • Caso Base: Para P_0\, es válido pues 1 \leq \frac{1}{2} + 1\,
  • Hipótesis: Asumimos como hipótesis de inducción que efectivamente se cumple 1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} \le \frac{n}{2}+1\,
  • Demostración: Debemos demostrar para P_{n+1}\,
1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1} \leq \frac{n+1}{2} + 1\,
Pero, aplicando la hipótesis de inducción:
1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1} \leq \frac{n}{2} + 1 + \frac{1}{n+1}\,
Y dado que 1 \leq n\,, sumando n^2 + n + 1\,
en ambos lados de la desigualdad tenemos:
n^2 + n + 2 \leq n^2 + 2n + 1\,
\Rightarrow n^2 + n + 2 \leq (n+1)^2\,
\Rightarrow \displaystyle { \frac{n(n+1)+2}{2(n+1)} \leq \frac {n+1}{2} }\,
\Rightarrow \displaystyle { \frac{n}{2} + 1 + \frac{1}{n+1} \leq \frac {n+1}{2} + 1 }\,
y esto implica que
\displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}  + \frac{1}{n+1} \leq \frac{n}{2} + 1 + \frac{1}{n+1} \leq \frac {n+1}{2} + 1} .\,
Por lo tanto se demuestra la tesis.
  • Conclusión: Como P_0\, es cierto y P_{n+1}\, también es cierto, podemos concluir que la proposición es valida \forall n \in \mathbb{N}; n \geq 1\,
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas