Hola
¿Cómo pasas del \( T(2^{k-1}) \) a \( (k-1) \)?
Entiendo que la pregunta está relacionada con esta otra: ¿Es correcta esta resolución de una recurrencia?, pero deberías aclarar cuál es la fórmula general de \( T(n) \), aunque parecer ser que es:
\( T(n)=\dfrac{3(n-1)}{2}. \)
Hola, es otro ejercicio distinto, lo que busco, más allá de la resolución de la recurrencia en si, es como pasa de \( T(2^k) = 3T(2^{k-1}+2^k \) a \( t(k) = 3t(k-1) +2^k \)
Hoka
Llevo una hora mirando esta sustitución y no soy capaz de entender como hace el cambio, ¿alguna ayuda?
\( T(2^k) = 3 T(2^{k-1}) +2^k \)
Sustituye \( T(2^k) \) por \( t(k) \)
\( t(k) = 3 + (k-1) + 2^k \)
¿Cómo pasas del \( T(2^{k-1}) \) a \( (k-1) \)
Es que está mal. Sería:
\( t(k)=3t(k-1)+2^k \)
Una solución particular de esa ecuación es de la forma \( t(k)=a\cdot 2^k \). Sustituyendo se ve que es \( t(k)=-2^{k+1} \).
La solución de la homogénea asociada \( t(k)=3(k-1) \) es \( t(k)=b3^k \).
Por tanto la solución general de la ecuación es:
\( t(k)=b\cdot 3^k-2^{k+1} \)
Con una condición inicial puede fijarse el valor de \( b \).
Entiendo que la pregunta está relacionada con esta otra: ¿Es correcta esta resolución de una recurrencia?, pero deberías aclarar cuál es la fórmula general de \( T(n) \), aunque parecer ser que es:
\( T(n)=\dfrac{3(n-1)}{2}. \)
Ojo, porque no es la misma relación de recurrencia en un ejercicio que en otro.
Saludos.
Cierto, se me paso poner la T.
Entiendo que hace un cambio de \( T(2^k) \) por \( t(k) \) pero no termino de ver, porqué se pone \( (k-1) \)
Tienes \( (2^{k-1}) \) dentro de la T inicial
Sabemos que \( t(k) = T(2^k) \) pero no tenemos una relación entre \( t(k) \) con \( T(2^{k-1}) \).
No entiendo como logra ese cambio. Si en vez de \( T(2^{k-1}) \) tuviera \( T(2^{k}) \) si lo veo, porque tenemos la relación de \( t(k) = T(2^k) \), pero con \( t(k) = T(2^{k-1}) \) no tenemos una relación para poder aplicar el cambio, o mejor dicho, no veo la relación (seguramente la haya)
