Usuario:CRISTIAN GARCIA INFORMATICA:Heuristica

EJERCICIO

Qué nos dan?

nos dan las siguientes definiciones

$fact(n)=1*2*3*...*(n-1)*n$

$n!=n*(n-1)!$

$fact(n)=n!$

Qué nos piden?

Nos piden demostrar que las dos definiciones son iguales, tanto como la recursiva como la iterativa.

Còmo relacionamos lo que nos dan con los que nos piden?

Por el metodo de inducción, el cual consta de dos pasos: el primero:

Demostrar que se cumple para el primero de los casos

Primera definición

$fact(1)=1$

$1=1$

Segunda definición

$1!=1*(1-1)!$

$1!=1*0!$

$1!=1*1$ (por definición el factorial de "cero" es 1)

$1!=1$

$1=1$

Comprobamos que se cumple para las dos definiciones y llegamos a una equivalencia.

El segundo paso es suponer que esta igualdad se cumple para cualquier numero (k), y a partir de esa suposicion (la cual va ser la hipotesis de induccion) se debe demostrar que la igualdad es valida para el termino k+1.

Desde la hipotesis de induccion se debe llegar a $fact(k+1)=1*2*3*...*k*(k+1)=(k+1)!=(k+1)*(k)!$

Tomamos la hipótesis de inducción:

$fact(k)=1*2*3*4*...*k=k*(k-1)!=k!$

$1*2*3*...*k=k!$

y como toca para demostrarlo para el siguiente número de la serie le multiplicamos k+1 a cada lado para que no se altere la igualdad:

$1*2*3*...*k*(k+1)=k!(k+1)$

y por propiedades de factorial podemos decir que

$1*2*3*...*k*(k+1)=(k+1)!$

y ahi queda demostrado que:

$fact(k+1)=1*2*3*...*k*(k+1)=(k+1)!=(k+1)*(k)!$

Cómo se que la relacion es cierta?

Por construccion y por que se hizo por medio de una demostración.