Autor Tema: Ayuda con funciones recursivas o recurrentes

0 Usuarios y 1 Visitante están viendo este tema.

10 Junio, 2009, 06:39 am
Leído 1781 veces

RonnyVicent

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
Hola necesito ayuda en lo siguientes, es de álgebra, Primero si me pueden ayudar a definir que es una función recursiva se lo agradezco, que por lo que he leido es igual a funcución recurrente. El profesor nos asigno el siguiente problema:
\( \forall{n\in{N}} \):
\( L(n) = \left \{ \begin{matrix} 0 & \mbox{si }n\mbox{ = 1}\\ L\left [ \displaystyle\frac{n}{2}\right ] +1 & \mbox{si }n\mbox{ es mayor a 1}\end{matrix}\right. \),
donde \( \left [ \displaystyle\frac{n}{2}\right ]  \) es la parte entera de \( \displaystyle\frac{n}{2} \)
Luego dijo: ahora bien Sea L(n)=  x  demuestre que \( 2^x\leq{n} \) y use este resultado para concluir \( L(n)=\left [ Log_2 n \right ] \)

10 Junio, 2009, 01:15 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Función recursiva y función recurrente es lo mismo: son funciones con valores enteros suyo valor sobre un número se definie a partir de los valroes sobre números inferiores.

 Puedes probar lo que te piden por inducción:

 - Para \( n=1 \), \( 2^{L(1)}=1\leq 1 \).

 - Suponemos ciertos para valores menores que \( n \) y lo probamos para \( n>1 \). Se tiene:

\(  x=L(n)=L\left[\dfrac{n}{2}\right]+1\quad \Rightarrow{}\quad  L\left[\dfrac{n}{2}\right]=x-1 \)

 Por hipóteis de inducción:

\(  2^{x-1}\leq \left[\dfrac{n}{2}\right] \)

 pero:

\(  2^{x-1}\leq \left[\dfrac{n}{2}\right]\leq \dfrac{n}{2}\quad \Rightarrow{}\quad  2^x\leq n \)

 Intenta tu la segunda parte. Ten en cuenta que:

\(  [Log_2(n)]=x\quad \Leftrightarrow{}\quad x\in Z \) y \( \color{red}Log_2(n)-1<x\leq Log_2(n)\color{black}\quad \Leftrightarrow{}\quad  x\in Z \) y \( \color{red}n/2< 2^x\leq n\color{black} \).

CORREGIDO.

Saludos.

10 Junio, 2009, 10:11 pm
Respuesta #2

RonnyVicent

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
Hola gracias por tu oportuna respuesta me ayudo bastante pero aun tengo una duda con respecto a lo que esta al final por lo siguiente que no consigo como demostrar; es decir si tenemos que
L(n)=x\( \Longrightarrow{2^x\leq{n} \)
por lo que se demostro previamente y aplicando logatitmo de base 2 a ambos lados nos queda:
\( x\leq{Log_2(n)} \) y luego sumando el 1 en el miembro derecho nos queda la desigualdad estricta. Ahora la cuetion es que se debe probar lo contrario que \( Log_2(n)\leq{x} \)
No veo eso claro si puedes orientar te lo agradezco

11 Junio, 2009, 08:43 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Tenía una errata en la interepretación de la parte entera del logaritmo que ya corregí.

 Ahora te falta probar que si \( x=L(n) \) entonces \( n/2<2^x  \) (o equivalentemente \( n<2^{x+1} \)).

 De nuevo por inducción. Inténtalo (imita los pasos de la demostración anterior).

Spoiler
Quizá te pueda ser interesante distinguir el caso n par y n impar. También tener en cuenta que para números enteros:

\(  2^x>k\quad \Rightarrow{}\quad 2^x\geq k+1\quad \Rightarrow{}\quad  2^{x+1}\geq 2k+2\quad \Rightarrow{}\quad 2^{x+1}>2k+1 \)
[cerrar]

Saludos.

13 Junio, 2009, 01:31 am
Respuesta #4

RonnyVicent

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
hola gracias por la ayura el_maco me servió bastante