Duda matemática... Lo siento por consultarla aquí.

Buenas, es muy temprano y tengo esto un poco olvidado, pero veamos:

f(n) = f(n-1) * 2 + n

Por tanto:

f(n-1) = f(n-2) * 2 + (n-1)

Así que sustituyendo en la función f(n) quedaría:

f(n) = [f(n-2) * 2 + (n-1)] * 2 + n = 2 * 2 * f(n-2) + 2 * (n-1) + n

Seguimos:

f(n-2) = f(n-3) * 2 + (n-2)

Sustituyendo nuevamente y operando un poco:

f(n) = 2 * 2 * [f(n-3) * 2 + (n-2)] + 2 * (n-1) + n =
= 2 ^ 3 * f (n-3) + 2 ^ 2 * (n-2) + 2 * (n-1) + n =

La primera parte de la función se ve que va a ser 2 ^ n * f(0) y como f(0) = 1, pues quedará 2 ^ n

Falta la segunda parte de la función. hacemos una iteración más (sólo de esta parte que se ve más o menos cómo va a ser) y vamos a separar las n's de los términos independientes:
2^3 * (n-3) + 2^2 * (n-2) + 2 * (n-1) + n = (2^3*n + 2^2 * n + 2 * n + n) - (3*2^3 + 2*2^2 + 1*2^1) = (sacando factor común a n en el primer sumando) =
(2^3 + 2^2 + 2^1 + 2^0)*n - (3*2^3 + 2*2^2 + 1*2^1)

Y esta parte sólo se me ocurre sacarl a fórmula general con sumatorios. Sería:
n * (sumatorio desde i=0 hasta i=n) de 2^i
-
(sumatorio de i=1 hasta i=n) de i*2^i

No sé si está claro o no, pero como he dicho, es muy temprano... Espero haberte ayudado (y que esté bien hecho...). Un saludete

Edito: he corregido un error que he visto...

ascoli_arzela escribió:Buenas, es muy temprano y tengo esto un poco olvidado, pero veamos:

f(n) = f(n-1) * 2 + n

Por tanto:

f(n-1) = f(n-2) * 2 + (n-1)

Así que sustituyendo en la función f(n) quedaría:

f(n) = [f(n-2) * 2 + (n-1)] * 2 + n = 2 * 2 * f(n-2) + 2 * (n-1) + n

Seguimos:

f(n-2) = f(n-3) * 2 + (n-2)

Sustituyendo nuevamente y operando un poco:

f(n) = 2 * 2 * [f(n-3) * 2 + (n-2)] + 2 * (n-1) + n =
= 2 ^ 3 * f (n-3) + 2 ^ 2 * (n-2) + 2 * (n-1) + n =

La primera parte de la función se ve que va a ser 2 ^ n * f(0) y como f(0) = 1, pues quedará 2 ^ n

Falta la segunda parte de la función. hacemos una iteración más (sólo de esta parte que se ve más o menos cómo va a ser) y vamos a separar las n's de los términos independientes:
2^3 * (n-3) + 2^2 * (n-2) + 2 * (n-1) + n = (2^3*n + 2^2 * n + 2 * n + n) - (3*2^3 + 2*2^2 + 1*2^1) = (sacando factor común a n en el primer sumando) =
(2^3 + 2^2 + 2^1 + 2^0)*n - (3*2^3 + 2*2^2 + 1*2^1)

Y esta parte sólo se me ocurre sacarl a fórmula general con sumatorios. Sería:
n * (sumatorio desde i=0 hasta i=n) de 2^i
-
(sumatorio de i=1 hasta i=n) de i*2^i

No sé si está claro o no, pero como he dicho, es muy temprano... Espero haberte ayudado (y que esté bien hecho...). Un saludete

Edito: he corregido un error que he visto...

Si, me viene bien, lo pulo un poco y ya está, supongo que me servirá.

Muchas gracias

de nada hombre. Si hay alguna cosa mal, pues lo siento, jejejeje, era muy temprano. Pero bueno, la idea creo que puede ser esa.

Por cierto, en caso de que tuvieras que demostrarlo, utiliza el método de inducción. Creo que con ello se podrá demostrar.

Un saludo!!!!!

ascoli_arzela escribió:de nada hombre. Si hay alguna cosa mal, pues lo siento, jejejeje, era muy temprano. Pero bueno, la idea creo que puede ser esa.

Por cierto, en caso de que tuvieras que demostrarlo, utiliza el método de inducción. Creo que con ello se podrá demostrar.

Un saludo!!!!!

No creo que haga falta que me meta a demostrarlo, es un subapartado de un ejercicio de teoria de la computabilidad (tampoco hace falta que hagamos aqui ahora una tesis del apartado)... y vamos, el profesor espera que lo hagamos haciendo conjeturas sobre valores de f(n), es decir, calcular f(5) f(4) f(3) f(2) f(1) f(0) y asi, a ojo, debería ser suficiente para deducir el valor... pero yo que soy mu cazurro mejor lo hago guiandome con tus indicaciones.

Salu2

ok. Es que tampoco sabía lo que estudiabas ni hasta que punto te pedían que fuera más o menos estricto.

Un saludete!!!!