[daniiy]

Hola. En este ejercicio, sé hacer el primer apartado (y lo entiendo vaya). El segundo apartado tengo la solución y lo entiendo, pero no sé que hacer para llegar a la solución (aunque igual si me tiro 1 hora pensando lo saco, pero me figuro que algunas pautas se seguirán para llegar a la solución, la pongo aquí:
Si n PAR \( (n=2p) \Rightarrow{} b_{2p} = 2b_p + 1, p\geq{1} \)
Si n IMPAR \( (n=2p-1)\Rightarrow{} b_{2p-1} = b_p + b_{p-1} + 1, p\geq{1} \)
El tercer apartado no sé cómo hacerlo, y el cuarto, creo que hay que demostrarlo por inducción, (es fácil demostrar el primer caso, en el caso de que n valga 1), pero no sé como demostrarlo para n+1.

[luis]

creo que llegan a esa recurrencia mirando directamente en el algoritmo. observa que cuando n > 1, la cantidad de multiplicaciones realizadas son

* la realizada en la última línea del algoritmo, más
* las que corresponden a la primera invocación recursiva (exp1 (a,m)), más
* las que corresponden a la segunda invocación recursiva (exp1 (a,n-m)).

es decir,

\( b_n := 1 + b_m + b_{n-m} \)

donde \( m = \lfloor \frac n2 \rfloor \).

las dos ecuaciones que pones aparecen al considerar que n puede ser par o impar, y eliminar la m.

saludos

[daniiy]

Perfecto, entendido, muchas gracias. Y respecto a los dos últimos apartados?

Saludos.

[Luis Fuentes]

Hola

Perfecto, entendido, muchas gracias. Y respecto a los dos últimos apartados?

Saludos.

Para el tercero si llamas \( a_k=b_{2^k} \) la relación de recurrencia:

\( b_{2p}=2b_p+1 \)

se traduce en:

\( a_{k+1}=2a_k+1 \)

con condición inicial \( a_0=b_1=0 \). Es una ecuación lineal en recurrencias que no debes de tener problema en resolver.

Para el tercero simplemente comprueba que la solución propuesta:

\( b_n=n-1 \)

cumple las relaciones de recurrencia:

\( b_n=2b_{n/2}+1 \) si \( n \) par

\( b_n=b_{(n+1)/2}+b_{(n-1)/2}+1 \) si \( n \) impar

Por ejemplo si \( n \) es par:

\( b_n=n-1 \)

\( 2b_{(n/2)}+1=2(\dfrac{n}{2}-1)+1=n-2+1=n-1 \)

Saludos.

[luis]

lo que quieres es ver qué pasa cuando tenés \( b_{2^k} \). para que resulte más fácil escribir, sugiero definir

\( c_k := b_{2^k} \)

ahora, escribí la recurrencia c a partir de los valores para b

* \( c_0 := ... \)
* \( c_{k+1} := ... \)

te tiene que quedar una definición que, seguramente, ya conoces.

el último apartado lo puedes hacer por inducción. pero para que te salga sencillo, en lugar de usar el principio de inducción habitual (si \( P(1) \) y \( (\forall n : P(n) : P(n+1)) \), entonces \( (\forall n :: P(n)) \)) usa el que dice

* si \( (\forall m: (\forall n : n<m : P(n)) : P(m)) \), entonces \( (\forall n :: P(n)) \)

saludos

[daniiy]

El primer ejercicio queda entendido, y..respecto al último.... cómo se haría por el primer método de inducción que muestra luis?

Muchas gracias, saludos

[Luis Fuentes]

Hola

El primer ejercicio queda entendido, y..respecto al último.... cómo se haría por el primer método de inducción que muestra luis?

Yo no lo haría por inducción: si te mandan probar que una sucesión dada es solución a una recurrencia, lo más natural, obvio y directo es verificar que esa sucesión cumple la ecuación.

En el fondo las cuentas implicadas en la inducción son las mismas, pero se complica ligeramente la escritura de manera innecesaria.

Por inducción sería:

- Para \( n=1,2 \) el resultado es cierto ya que \( b_1=0=1-1, \quad b_2=1=2-1 \).

- Dado \( n>2 \), supongamos cierto para todo \( k<n \) es decir que \( b_k=k-1 \) para \( k\leq n \) y probémoslo para \( n \).

 -- Si \( n \) es par sabemos que:

\(  b_n=2b_{n/2}+1 \)

 Por hipótesis de inducción dado que \( n/2<n \) se tiene que \( b_{n/2}=n/2-1 \) y así:

\(  b_n=2b_{n/2}+1=2(n/2-1)+1=n-1 \)

-- Si \( n \) impar sabemos que:

\( b_n=b_{(n+1)/2}+b_{(n-1)/2}+1 \)

 Continúa...

Saludos.

[daniiy]

Buf, no pensé que fuera tan difícil, es mejor tu primera forma, cierto, muchas gracias.

Respecto al primer ejercicio he intentado hacer la solución y me ha salido de solución de la ec. homogénea una constante A, y de la particular Bk. Luego me quedó B=1, A=0. Y por lo tanto \( a_k = k \)

[Luis Fuentes]

Hola

Buf, no pensé que fuera tan difícil, es mejor tu primera forma, cierto, muchas gracias.

No puede ser que la demostración por inducción anterior te parezca difícil. Y no lo digo en plan "profesor que ha visto cien veces sus problemas y todos los tacha de fáciles"; es una típica demostración por inducción; no tiene nada. Es más, como te comenté, la única diferencia con "mi primera forma" es que hay que añadir más literatura, mas explicaciones, para respetar el esquema de la demostración por inducción pero esencialmente se hacen exactamente las mismas cuentas.

Respecto al primer ejercicio he intentado hacer la solución y me ha salido de solución de la ec. homogénea una constante A, y de la particular Bk. Luego me quedó B=1, A=0. Y por lo tanto \( a_k = k \)

Pero si la ecuación es:

\( a_{k+1}=2a_k+1 \)

la homogénea asociada es:

\( a_{k+1}-2a_k=0 \)

El polinomio característico \( x-2=0 \). Su raíz \( x_1=2 \). Por tanto la solución general es de la forma \( a_k=A\cdot 2^k \), con \( A \) constante.

Continúa desde aquí...

Saludos.

P.D. Por curiosidad, ¿en qué paso te habías equivocado en la resolución de esa ecuación?.

CORREGIDO

[luis]

lo que agregaría  a lo que dice el_manco a cómo probar que b_n = n-1 es que resulta necesario recordar que las ecuaciones de recurrencia usadas definen una única sucesión b. si eso es conocido, entonces la respuesta de el_manco es la más breve y elegante.

me queda en el tintero algo acerca de recursión, pero en este momento tengo un hijo a los saltos que tengo que intentar domesticar.

saludos