Inducció forta

La inducció forta o inducció completa és un método de demostració matemàtica similar a l'inducció matemàtica comuna, pero diferix en el raonament de lo que volem demostrar. Es pren un número fix i es pren com hipòtesis que és cert per a un atre número fix major que este i per a tots els que estan entre ells. Aixina, l'afirmació és certa només si també es complix per al successor d'este últim número.

Existix també un método de inducció dèbil o inducció desplaçada, que usa un raonament en cert modo invers a est, ya que pren com a base l'hipòtesis de que és certa per a l'antecessor del que es vol demostrar.

El procediment és vàlit considerant que els elements de lo que volem demostrar pertanyen a un conjunt inductivo. És dir, el conjunt de totes les afirmacions és un conjunt inductivo.

Enunciat

Podem enunciar el principi d'inducció forta tal i com es mostra a continuació:

Siga P(n) una afirmació que depén del paràmetro n sancer, i suponent que es demostra lo següent,

• 1) $P(n_0)$ és certa per a un cert $n_0$ sancer
• 2) Sempre que $P(k)$ és cert i que $P(m)$ és cert per a qualsevol sancer $n_0<m<k$, es tindrà que $P(k+1)$ és cert,

llavors l'afirmació $P(n)$ serà certa para tot sancer $n\ge n_0$.

Sol ser més complicat i no trivial solucionar els problemes comuns d'inducció en este método, pero pot ser ventajós.

Eixemple

Prova d'una de les propietats de la successió de Fibonacci.

Siga $\{F_n{\}}_{n\in \mathbb{N}}$ la successió de Fibonacci i $F_n$ el n-ésimo número de Fibonacci $\Rightarrow \mathrm{\forall }n\in \mathbb{N},F_n\le 2^n$

Demostració

Usant el principi d'inducció forta:

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

$F_0=0\le 2^0=1$

$F_1=1\le 2^1=2$

• ii) Iterando suponem que l'hipòtesis inductiva val per a $1,2,\mathrm{...},n\in \mathbb{N}$ en $n>2$

$\Rightarrow F_k\le 2^k$ en $k=1,2,\mathrm{...},n\in \mathbb{N}$

• iii) Per demostrar que $\mathrm{\forall }n+1\in \mathbb{N},F_{n+1}\le 2^{n+1}$

Com $n+1\ge 3$

$F_{n+1}:=F_n+F_{n-1}$

Usant l'hipòtesis d'inducció $F_n\le 2^n,F_{n-1}\le 2^{n-1}$

$\Rightarrow F_n+F_{n-1}=F_{n+1}\le 2^n+2^{n-1}$ i com $2^n+2^{n-1}\le 2^n+2^n=2^{n+1}$, per transitividad de la desigualtat es té

$F_{n+1}\le 2^{n+1}$

■

Vore també

• Principi d'inducció

Bibliografia

• H. Cárdenas, E. Lluis, F. Raggi i F. Tomás, Àlgebra Superior, Mèxic, Trillas, 1978. ISBN 968-24-3783-0.