Inducción fuerte

La inducción fuerte o inducción completa es un método de demostración matemática similar a la inducción matemática común, pero difiere en el razonamiento de lo que queremos demostrar. Se toma un número fijo y se toma como hipótesis que es cierto para otro número fijo mayor que éste y para todos los que están entre ellos. Así, la afirmación es cierta sólo si también se cumple para el sucesor de este último número.

Existe también un método de inducción débil o inducción desplazada, que usa un razonamiento en cierto modo inverso a este, ya que toma como base la hipótesis de que es cierta para el antecesor del que se quiere demostrar.

El procedimiento es válido considerando que los elementos de lo que queremos demostrar pertenecen a un conjunto inductivo. Es decir, el conjunto de todas las afirmaciones es un conjunto inductivo.

Podemos enunciar el principio de inducción fuerte tal y como se muestra a continuación:

Sea P(n) una afirmación que depende del parámetro n entero, y suponiendo que se demuestra lo siguiente,

• 1) ${\displaystyle P(n_{0})\,\!}$ es cierta para un cierto ${\displaystyle n_{0}\,\!}$ entero
• 2) Siempre que ${\displaystyle P(k)\,\!}$ es cierto y que ${\displaystyle P(m)\,\!}$ es cierto para cualquier entero ${\displaystyle n_{0}<m<k\,\!}$, se tendrá que ${\displaystyle P(k+1)\,\!}$ es cierto,

entonces la afirmación ${\displaystyle P(n)\,\!}$ será cierta para todo entero ${\displaystyle n\geq n_{0}\,\!}$.

Suele ser más complicado y no trivial solucionar los problemas comunes de inducción con este método, pero puede ser ventajoso.

Prueba de una de las propiedades de la sucesión de Fibonacci.

Sea ${\displaystyle \{F_{n}\}_{n\in \mathbb {N} }}$ la sucesión de Fibonacci y ${\displaystyle F_{n}}$ el n-ésimo número de Fibonacci ${\displaystyle \Rightarrow \forall {n}\in \mathbb {N} ,F_{n}\leq 2^{n}}$

Demostración

Usando el principio de inducción fuerte:

• i) Probar la base inductiva ${\displaystyle n=0,1\in \mathbb {N} }$

${\displaystyle F_{0}=0\leq 2^{0}=1\,\!}$

${\displaystyle F_{1}=1\leq 2^{1}=2\,\!}$

• ii) Iterando suponemos que la hipótesis inductiva vale para ${\displaystyle 1,2,...,n\in \mathbb {N} }$ con ${\displaystyle n>2}$

${\displaystyle \Rightarrow F_{k}\leq 2^{k}}$ con ${\displaystyle k=1,2,...,n\in \mathbb {N} }$

• iii) Por demostrar que ${\displaystyle \forall {n+1}\in \mathbb {N} ,F_{n+1}\leq 2^{n+1}}$

Como ${\displaystyle n+1\geq 3}$

${\displaystyle F_{n+1}:=F_{n}+F_{n-1}\,\!}$

Usando la hipótesis de inducción ${\displaystyle F_{n}\leq 2^{n},F_{n-1}\leq 2^{n-1}}$

${\displaystyle \Rightarrow F_{n}+F_{n-1}=F_{n+1}\leq 2^{n}+2^{n-1}}$ y como ${\displaystyle 2^{n}+2^{n-1}\leq 2^{n}+2^{n}=2^{n+1}}$, por transitividad de la desigualdad se tiene

${\displaystyle F_{n+1}\leq 2^{n+1}}$

■

• Principio de inducción

• H. Cárdenas, E. Lluis, F. Raggi y F. Tomás, Álgebra Superior, México, Trillas, 1978. ISBN 968-24-3783-0.

• Principios de Inducción, Mat. Frank P. Murphy-Hernández