Estás mezclando dos "estilos" de principios de inducción. Uno de ellos dice lo siguiente:
Para probar que [texx](\forall n) P(n)[/texx] basta probar que:
1. [texx]P(0)[/texx], y
2. [texx](\forall n) (P(n) \to P(n+1))[/texx]
En este caso, tu propiedad sería:
[texx]P(n) := fib (n+3) \text{ es par}[/texx]
Luego, probarías el caso baso como lo hiciste, y el caso inductivo no podrías probarlo. Observa que tienes que probar que fib(n+4) es par suponiendo que fib(n+3) lo es, pero no puedes usar como hipótesis que fib(n+2) también sea par.
Así que, en realidad, usas el siguiente "estilo" de prinbcipio de inducción.
Para probar que [texx](\forall n) P(n)[/texx] basta probar que:
1. [texx]P(0)[/texx], y
2. [texx](\forall m) ((\forall n < m) P(n) \to P(m))[/texx]
Ahora, al probar la propiedad te encuentras con la siguiente situación: supongamos que m > 1, y por lo tanto sabes que vale tanto P(m-1) como P(m-2). La prueba sigue como tú la hiciste.
Lamentablemente, hay que probar el renglón dos para todos los m; en particular, si m<=1.
Observemos que si m = 1 queremos probar que fib (4) es par, y podemos usar que fib(3) es par; ahora bien, fib(4) = fib(3)+fib(2), y esa suma es impar. En no considerar todos los m reside el error de la prueba dada.
saludos
luis
Buenas, la sentencia dice lo siguiente:
para todo numero entero n: si n es mayor o igual a tres entonces la función de fibonacci([texx]fib(n)[/texx]) es par.
Primero prueba el caso base n=3 fib(3)=2 y define a fib(n) recursivamente como:
fib(n)=fib(n-1)+fib(n-2)
ahora la hipótesis inductiva, esto es: que fib(m) sea par es cierto para todo m[texx]\leq{}[/texx]n
lo probamos para fib(n+1):
fib(n+1)=fib(n)+fib(n-1)
como fib(n) y fib(n-1) son pares y la suma de dos numeros pares es un numero par la propiedad es verdadera para todo n[texx]\geq{}[/texx]3
¿donde se encuentra el error?
