Solución de Recurrencias

Dr. Ivan Olmos Pineda

Contenido

Introducción a la Solución de RecurrenciasTécnicas para la Solución de Recurrencias

Por sustituciónRecurrencias homogéneasRecurrencias no homogéneasCambio de variableTransformación de Intervalo

Introducción a la Solución de Recurrencias

Determinar el orden de un algoritmo recursivo requiere de un análisis más minucioso

int fact(int n)

{ if (n == 0)

return 1;

else

return(n * fact(n-1));

}

−=

=otherwisenfnnif

nf)1(*

01)(

Técnicas para la Solución de Recurrencias

Existen diversas técnicas para la solución de recurrencias

IntuitivasBasadas en ecuaciones características

Para la mayoría de los casos, utilizando la técnica adecuada es posible solucionar una recurrencia

Método de Sustitución

Sustitución

El método más simple y sencilloSe va evaluando la recurrencia para ciertos valoresSe deduce, a partir del comportamiento mostrado, una ecuación que represente el comportamiento de la recurrenciaSe demuestra que la ecuación, efectivamente, resuelve a la recurrencia

Ejemplo

Considere la siguiente recurrencia:

¿Cómo resolverla?Primera idea, construir una tabulación de los valores que toma la recurrencia para diferentes valores de nTIP: note que la recurrencia solo queda definida para n potencias de 2, es decir, para n = 2k, donde k es un entero positivo

>+=

=1)2/(3

11)(

nsinnTnsi

nT

Ejemplo

3T(1)+2 = 3x1+23T(2)+22 = 3[3x1+2]+22 = 32x1 + 3x2 + 22

3T(4)+23 = 3[32x1 + 3x2 + 22] + 23 = 33x1 + 32x2 + 31x22 + 23

3T(8)+24 = 3[33x1 + 32x2 + 31x22 + 23]+24 = 34x1+33x2+32x22+3x23+24

21

22

23

24

T(n)n

∑=

−− =+++=k

i

iikkkkkT0

0110 2323...2323)2(

Ejemplo

En la expresión anterior, notemos que T queda en términos de una sumatoria, por lo que se requiere manipulación algebraica para dejarla en términos exclusivamente del argumento:

Para resolver esta fórmula se utilizó la serie:a, ar, ar2, ar3, …, arn

sn = a(1-rn)/(1-r)

11

0 023)3/2(323 ++

= =

− −==∑ ∑ kkk

i

k

i

ikiik

Ejemplo

Por tanto:T(2k) = 3k+1-2k+1

Como sabemos que n = 2k log2n = k, con lo cual se obtiene una T en términos de n:

T(n) = 3log n +1 – 2log n +1

Recurrencias Homogéneas

Introducción

Las recurrencias homogéneas tienen la forma:

a0tn + a1tn-1 + … + aktn-k = 0 (1)

Por ejemplo, la sucesión de Fibonacci tiene la forma de una recurrencia homogénea:

fn = fn-1 + fn-2

Polinomio Característico

Si consideramos que tn = xn y sustituimos en (1), tendremos:

a0xn + a1xn-1 + … + akxn-k = 0Esta ecuación se satisface si:

p(x) = a0xk + a1xk-1 + … + ak = 0A este polinomio se le conoce como ecuación característica de las recurrencias lineales

Solución del Polinomio Característico

Por teorema fundamental del álgebra, todo polinomio p(x) de grado “k” tiene “k” raices (reales o complejas), por lo que p(x) se puede factorizar como:

∏=

−=k

iirxxp

1

)()(

Solución del Polinomio Característico

De la factorización, se concluye que:x = ri es solución de la ecuación característicari

n es una solución de la recurrenciaDado que toda combinación lineal de soluciones es también una solución, se concluye que toda solución de una recurrencia tn (sin raíces múltiples) tiene la siguiente forma:

∑=

=k

i

niin rct

1

Ejemplo 1

Consideremos la sucesión de Fibonacci:

Esta recurrencia tiene la forma: fn – fn.1 – fn-2 = 0Polinomio característico:

x2 – x – 1 = 0k = 2, a0 = 1, a1 = -1, a2 = -1

+==

=−− casootroff

nnsinf

nnn

21

1,0

Ejemplo 1

Raíces del polinomio:

Solución general de la recurrencia (sin raíces múltiples):

Para encontrar el valor de las constantes c1 y c2, es necesario evaluar el valor de la recurrencia fn en sus casos base

251,

251

21−

=+

= rr

nnn rcrcf 2211 +=

Ejemplo 1

10

2211

21

=+=+

crcrcc

51,

51

21 −== cc

Resolviendo el sistema de ecuaciones:

Por tanto, se concluye lo siguiente:

−−

+=

nn

nf 251

251

51

Ejemplo 2

Considere la recurrencia:

Polinomio característico:x2 + 3x + - 4 = 0

Raíces: r1 = -1, r2 = 4Solución general: tn = c1(-1)n + c24n

+==

=

−− casootrottnsinsi

t

nn

n

21 431500

Ejemplo 2

De lo anterior y utilizando los casos base, se forma el sistema de ecuaciones siguiente:

Donde c1 = -1, c2 = 1. Por tanto:

tn = 4n – (-1)n

15400

21

21

==+−==+

nccncc

Solución de Recurrencias con Raíces Múltiples

Si la recurrencia a solucionar tiene raíces múltiples, entonces la solución varía por lo siguiente:

p(x) = a0xk + … + ak pol. característico de la recurrenciaSea r una raíz de multiplicidad 2, entonces p(x) se puede reescribir como p(x) = (x-r)2q(x), donde q(x) es de grado k-2

Solución de Recurrencias con Raíces Múltiples

Considere los siguientes polinomios de grado “n”:

un(x) = a0xn + a1xn-1 + … + akxn-k

vn(x) = a0 n xn + a1 (n-1) xn-1 + … + ak (n-k) xn-k

vn(x) = x u’(x)un(x) se puede reescribir de la siguiente forma:

un(x) = xn-k p(x) y como p(x) = (x-r)2q(x) entoncesun(x) = (x-r)2 [xn-k q(x)]

Solución de Recurrencias con Raíces Múltiples

Derivando un(x) con respecto a “x” se tiene:u’n(x) = 2(x-r) [xn-k q(x)] + (x-r)2 [xn-k q(x)]’Por tanto, u’n(r) = 0, lo cual implica que r u’n(r) = 0, por lo que se concluye quea0 n rn + a1 (n-1) rn-1 + … + ak (n-k) rn-k = 0

Con lo anterior, se tiene que tn = n rn es una solución de la recurrencia

Solución de Recurrencias con Raíces Múltiples

En general, si “r” es una raiz de multiplicidad “m”, se tiene que:

tn = rn, tn = n rn, tn = n2 rn, …, tn = nm-1 rn son soluciones de la recurrencia tn

En resumenr1, …, rs raices distintasm1, …, ms sus multiplicidades respectivamente, entonces:

∑∑=

−

=

=s

i

m

j

ni

jijn

i

rnct1

1

0

Ejemplo

Considere la recurrencia:

Su polinomio característico es:tn – 5tn-1 + 8tn-2 – 4tn-3 = 0

El polinomio característico es:p(x) = x3 – 5x2 + 8x – 4 = 0

Por lo tanto:r1 = 1, m1 = 1r2 = 2, m2 = 2

+−===

=−−− casootrottt

nnnsint

nnnn

321 4852,1,0

Ejemplo

De lo anterior, se concluye que para esta recurrencia, su expresión general es:

tn = c11n + c22n + c3n2n

De las condiciones iniciales se obtiene lo siguiente:

Resolviendo el Sist. de Ec., se tiene que: c1 = -2, c2= 2, c3 = -1/2, por lo que:

tn = 2n+1 – n2n-2 - 2

2284112200

321

321

21

==++==++==+

ncccncccncc

Recurrencias No Homogéneas

Recurrencias No Homogéneas

Estructura general recurrencia no homogénea:a0tn + a1tn-1 + … + aktn-k = bn p(n)“b” es una constantep(n) un polinomio de grado “d”

Estrategia generalTransformar la recurrencia a una expresión homogéneaResolver la expresión, tomando en cuenta que la expresión homogénea no es idéntica a la expresión original

Ejemplo 1

Considere la recurrencia:tn – 2tn-1 = 3n

b = 3, p(n) = 1Para transformar la recurrencia, se sigue el siguiente proceso:

3(tn – 2tn-1 = 3n) 3tn – 6tn-1 = 3n+1

Sustituyendo n n – 1 se tiene3tn-1 – 6tn-2 = 3n

Ejemplo 1

Se restan las recurrencias encontradas:tn – 2tn-1 = 3n *3tn-1 – 6tn-2 = 3n **

Resultado: tn – 5tn-1 + 6tn-2 = 0Ecuación característica: x2 - 5x + 6 = 0Raíces: r1 = 2, r2 = 3Por tanto, la solución es: tn = c12n + c23n

-

Ejemplo 1

Dado que (*) y (**) no son la misma recurrencia (no tienen los mismos caso base), para encontrar los valores de las constantes, se toma en cuenta que de la recurrencia original, t1 = 2t0 + 3

Resolviendo el sistema, se concluye que:c1 = t0 – 3, c2 = 3

Por tantotn = (t0 - 3)2n + 3n+1

132320

021

021

=+=+==+

ntccntcc

Ejemplo 2

Considere la recurrencia:tn – 2tn-1 = (n+5)3n

Dado que se desea una combinación lineal de esta igualdad que sumadas den cero, se observa lo siguiente:

(n+5)3n, -2 (3/3) (n+5)3n, (32/32) (n+5)3n

De lo anterior se obtienen las siguientes recurrencias, las cuales son sumadas:

Ejemplo 2

Sumando las recurrencias, obtenemos una recurrencia homogénea:

tn – 8tn-1 + 21tn-2 – 18tn-3 = 0El polinomio característico es:

x3 – 8x2 + 21x – 18 = 0

232

121

1

3)3(91893)4(6126

3)5(2

−−−

−−−

−

+=−+−=+−+=−

nnn

nnn

nnn

nttntt

ntt

Ejemplo 2

Con un poco de manipulación algebraica, se deduce que:

x3 – 8x2 + 21x – 18 = (x-2)(x-3)2

tn = c12n + c23n + c(n)3n

De esta recurrencia, se deduce que:t0 = c1 + c2

De tn – 2tn-1 = (n+5)3n tn = 2tn-1 + (n+5)3n

t1 = 2t0 + 18t2 = 2t1 + (2+5)32 = 4t0 + 99

Ejemplo 2

De lo anterior, se deduce que:c1 = t0 – 9, c2 = 9, c3 = 3

Por tanto:tn = (t0 - 9)2n + (n+3)3n+1

2994189411823320

0321

0321

021

=+=++=+=++==+

ntcccntcccntcc

Generalización

De los ejemplos anteriores, se puede concluir que el polinomio característico de una recurrencia no homogénea a0tn + a1tn-1 + … + aktn-k = bn p(n) es:

(a0xk + a1xk-1 + … + ak)(x-b)d+1

Recuerde que:“b” es una constante“d” grado del polinomio p(n)

Ejemplo 3

Considere el problema de las torres de Hanoi:

La recurrencia se expresa como:tn – 2tn-1 = 1

Observemos que b = 1 y p(n) = 1 (polinomio de grado 0). Por tanto, el polinomio característico es:

(x-2)(x-1)Por tanto, la recurrencia queda de la forma:

tn = c11n + c22n

+=

=− contrariocasot

nsit

nn 12

00

1

Ejemplo 3

Demuestre que después de despejar el sistema, se obtiene la recurrencia:

tn = 2n -1

Cambio de Variable

Ejemplo

Transformar una recurrencia complicada en una más simple

Consideremos que n = 2i

La recurrencia resultante ahora queda en términos de “i”Por tanto, ti = T(2i)

>+=

=2,1)2/(3

11)(

depotenciansinnTnsi

nT

Ejemplo

ti = T(2i) = 3T(2i-1) + 2i = 3ti-1 + 2i

Reescribiendoti – 3ti-1 = 2i

Para este caso, b = 2, d = 0, por lo que el polinomio característico es:

p(x) = (x-3)(x-2)De este polinomio se determina que:

ti = c13i + c22i

Dado que T(2i) = ti y n = 2i, entoncesT(n) = c13lg n + c22lg n = c1nlg 3 + c2n

Otras Técnicas para Resolución de Recurrencias

Transformación de IntervaloRecurrencias Asintóticas

En estas técnicas, básicamente se utiliza un cambio de variable, así como equivalencias que permitan transformar a la recurrencia en una expresión de la forma lineal