Foros de matemática
27/04/2017, 01:53:40 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Error en el proceso de inducción  (Leído 177 veces)
0 Usuarios y 1 Visitante están viendo este tema.
fafafa
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 31


Ver Perfil
« : 17/02/2017, 03:07:39 pm »

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?
En línea
sugata
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.233


Ver Perfil
« Respuesta #1 : 17/02/2017, 03:26:06 pm »

La hipótesis es que [texx]fib(n)[/texx] es par, pero no sabemos nada de [texx]fib(n-1)[/texx].
Creo que ese es el fallo. Aunque no estoy muy seguro.
En línea
fafafa
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 31


Ver Perfil
« Respuesta #2 : 17/02/2017, 04:18:07 pm »

Pero cuando se supone la hipotesis inductiva p(m), ¿no se supone verdadera para todo m[texx]\leq{}[/texx]n?
En línea
Juan Pablo
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.809


Ver Perfil
« Respuesta #3 : 17/02/2017, 05:24:01 pm »

Como la sucesión depende de dos términos anteriores entonces deberías probar que se cumple para los casos bases [texx]fib(3)[/texx] y [texx]fib(4)[/texx] como pare este último no se cumple entonces tenemos el error.

Por favor fafafa usa el [texx]\LaTeX[/texx] para las expresiones matemáticas.

Pero cuando se supone la hipotesis inductiva p(m), ¿no se supone verdadera para todo m[texx]\leq{}[/texx]n?

No siempre depende del ejercicio.
En línea
luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 288


Ver Perfil
« Respuesta #4 : 21/02/2017, 01:53:48 pm »


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?
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!