Capı́tulo 1

Relaciones de recurrencia

1.1. Definiciones básicas y ejemplos

Una sucesión de números reales es una lista infinita ordenada de reales: a0 , a1 , a2 , ...
Para cada entero no negativo n, se denota an el n-ésimo término de la sucesión, an−1 es el
término anterior a an , an+1 es el siguiente, etc. La notación {an } se refiere a la sucesión
cuyo término n-ésimo es an .
En ocasiones la sucesión comienza con a1 (no existe el término a0 ).
Ejemplo 1. Se conocen los primeros términos de una sucesión, y son: a0 = 3, a1 = 6,
a2 = 9, a3 = 12, ... Se puede inferir que el término n-ésimo es an = 3(n + 1). De otro
modo, se puede construir la sucesión observando que cada término se obtiene multiplicando
por 3 el anterior. Esto se expresa: an = 3an−1 .
Ejemplo 2. Se tiene una sucesión que comienza con los términos a0 = 1, a1 = 1/2,
a2 = 1/4, a3 = 1/8, ... El término n-ésimo es an = 1/2n . También puede verse que cada
término es la mitad del anterior, es decir, an = an−1 /2.
Ejemplo 3. Otro ejemplo es la sucesión cuyos primeros términos son a0 = 17/2, a1 =
17/2, a2 = 17/2, a3 = 17/2. Es decir, cada término es igual al anterior, entonces an =
an−1 , o an = 17/2.
Ejemplo 4. La sucesión cuyos primeros términos son a0 = 7, a1 = 9, a2 = 11, a3 = 13
satisface la condición que cada término es 2 más que el anterior, an = an−1 + 2. No es
difı́cil obtener el término general explı́citamente, que es an = 7 + 2n.
Ejemplo 5. Considere la sucesión cuyos primeros términos son a0 = 1, a1 = 1, a2 = 2,
a3 = 3, a4 = 5, a5 = 8. Analizando estos primeros términos, podemos darnos cuenta de que
a partir de a2 , cada término es la suma de los dos anteriores, es decir, an = an−1 + an−2 ,
para n > 2. O, equivalentemente, an+1 = an + an−1 , para n > 1.
Ejemplo 6. Las bacterias se reproducen por duplicación. Sabiendo que en una colonia de
bacterias, al cabo de una hora todas se duplican, siendo an la cantidad de bacterias en la
hora n, se puede plantear que an es el doble de la cantidad de bacterias en la hora n − 1;
es decir: an = 2an−1 .

1
 1.1. Definiciones básicas y ejemplos

Ejemplo 7. Un banco ofrece una tasa de interés mensual p. Si en el mes n, el dinero

acumulado en una cuenta es Cn , ese monto es la suma del dinero en el mes anterior (Cn−1 )
más el interés generado en ese mes (p·Cn−1 ). Es decir, Cn = Cn−1 +p·Cn−1 = (1+p)·Cn−1 .
En los ejemplos anteriores se logra describir sucesiones en forma explı́cita, dando una
fórmula para el término n-ésimo que depende sólo de su posición n: an = F (n). También
se obtienen expresiones para an que dependen de los términos anteriores, se definen en
forma recurrente. Dada una sucesión, una relación de recurrencia (o simplemente
recurrencia) para esa sucesión es una igualdad que relaciona un término de una sucesión
con ciertos términos anteriores. Especı́ficamente, una relación de recurrencia se puede
escribir de la forma:
an = f (an−1 , an−2 , ..., an−k )
válida para n > k. El orden de una relación de recurrencia es la cantidad de términos
anteriores que intervienen. En el caso general expuesto antes, el orden es k.
En los ejemplos anteriores han aparecido las relaciones de recurrencia: an = 3an−1 ,
an = an−1 /2, an = an−1 , an = an−1 + 2, an = 2an−1 , Cn = (1 + p) · Cn−1 , todas éstas de
orden 1. Y la relación de recurrencia an = an−1 + an−2 es de orden 2.
Ejemplo 8. La relación de recurrencia an = 2an−1 + 1 tiene grado 1. La recurrencia
an = an−1 . an−3 tiene grado 3.
Notar que la primer recurrencia también se puede escribir: an+1 = 2an + 1, ya que
expresa lo mismo: un término se obtiene multiplicando el anterior por dos y sumando 1
al resultado. El término anterior de an+1 es an .
Y la segunda recurrencia también puede escribirse an+1 = an . an−2 . A pesar de es-
cribirla de otra forma, la recurrencia sigue siendo de orden 3: se necesitan 3 términos
anteriores (an , an−1 y an−2 ) para definir el término an+1 .
Una solución de la relación de recurrencia es una sucesión {an } que
verifica la recurrencia. Existen infinitas soluciones de una recurrencia. Por ejemplo, en
el ejemplo 4 se llegó a la recurrencia an = an−1 + 2. La sucesión 2, 4, 6, 8, ... satisface
la misma recurrencia, ya que cada término se obtiene sumando 2 al anterior. La misma
recurrencia también es satisfecha por la sucesión -5/3, 1/3, 7/3, 13/3,... Sin embargo, si
especificamos el primer término, la solución es única.
En el ejemplo 5 se obtiene la recurrencia an = an−1 + an−2 para la sucesión 1, 1, 2, 3, 5,
8, ... . Esa recurrencia también describe la sucesión 1, 0, 1, 0, 1, ..., y también la sucesión 1,
-1, 0, -1, -1, -2, -3, ... . En estas dos nuevas sucesiones, cada término (a partir del tercero) es
igual a la suma de los dos términos anteriores. Además, en este caso, todas empiezan con
1. Por ser una recurrencia de orden dos, se necesita especificar los dos primeros términos
para que la solución sea única.
En la relación de recurrencia general, an = f (an−1 , an−2 , ..., an−k ), especificando los
primeros k términos, la solución es única. Es decir, existe una sola sucesión que verifica
an = f (an−1 , an−2 , ..., an−k ) n > k
a0 = A0
a1 = A1
...
ak−1 = Ak−1

2
 1. Relaciones de recurrencia

donde Ai son números reales dados. Las k igualdades ai = Ai se denominan condiciones

iniciales.
Nos ocuparemos en la sección siguiente de conocer métodos para resolver relaciones de
recurrencia con condiciones iniciales. Veremos primero cómo resolver algunos ejemplos, y
luego generalizaremos un método para un tipo especial de recurrencias.
Ejemplo 9. Considere la recurrencia an = (an−1 )2 + 1, para n > 1, con condición inicial
a0 = −1. La recurrencia indica que cada término es el cuadrado del anterior más 1.
Entonces,
para n = 1, a1 = a20 + 1 = (−1)2 + 1 = 2
para n = 2, a2 = a21 + 1 = 22 + 1 = 5
para n = 3, a3 = a22 + 1 = 52 + 1 = 26
para n = 4, a4 = a23 + 1 = 262 + 1 = 677
...
Ejemplo 10. Considere la recurrencia de grado 2 que indica que cada término es el
anterior menos el anterior del anterior: an = an−1 − an−2 , para n > 2, con condiciones
iniciales a0 = 0, a1 = 1. Entonces,
para n = 2, a2 = a1 − a0 = 1 − 0 = 1
para n = 3, a3 = a2 − a1 = 1 − 1 = 0
para n = 4, a4 = a3 − a2 = 0 − 1 = −1
para n = 5, a5 = a4 − a3 = −1 − 0 = −1
para n = 6, a6 = a5 − a4 = −1 − (−1) = 0
para n = 7, a7 = a6 − a5 = 0 − (−1) = 1
...
Aparentemente, en la sucesión se alternan repeticiones dobles de 1 y -1, intercaladas con
repeticiones simples de 0.
Ejemplo 11. Sea {an } una sucesión donde cada término an es el producto de su posición
n por el término anterior an−1 . Es decir, satisface la recurrencia an = nan−1 , n > 1 con
condición inicial a0 = 1. Los primeros términos son:
para n = 1, a1 = 1a0 = 1
para n = 2, a2 = 2a1 = 2· 1 = 2
para n = 3, a3 = 3a2 = 3· 2· 1 = 6
para n = 4, a4 = 4a3 = 4· 3· 2· 1 = 24
para n = 5, a5 = 5a4 = 5· 4· 3· 2· 1 = 120

Puede inferirse que la solución es an = n!, n > 0.

Ejemplo 12. Dada la recurrencia an = 2an−1 , n > 1, con condición inicial a0 = −1/3,
tenemos:
para n = 1, a1 = 2a0 = −2/3
para n = 2, a2 = 2a1 = −4/3
para n = 3, a3 = 2a2 = −8/3
para n = 4, a4 = 2a3 = −16/3
para n = 5, a5 = 2a4 = −32/3

3
 1.2. Resolución de recurrencias lineales homogéneas

Se infiere que la solución es an = − 13 2n , para todo n.

Ejemplo 13. En el problema de la inversión en el banco, Cn = (1 + p) · Cn−1 . Si el

depósito inicial es de 1000, es decir, C0 = 1000,
en el primer mes C1 = (1 + p) · C0 = (1 + p) · 1000
en el segundo mes C2 = (1 + p) · C1 = (1 + p)2 · 1000
en el tercer mes C3 = (1 + p) · C2 = (1 + p)3 · 1000
en el cuarto mes C4 = (1 + p) · C3 = (1 + p)4 · 1000
Ası́, la solución genérica puede expresarse: Cn = (1 + p)n · C0 .

Una recurrencia lineal es de la forma

an = c1 an−1 + c2 an−2 + ... + ck an−k + g(n)

donde ci son constantes, y g(n) es una función que puede depender de n, pero no de los
an . Si g(n) = 0, la recurrencia es homogénea.

Ejemplo 14. De las recurrencias vistas en los ejemplos anteriores, las que no son lineales
son: an = n·an−1 porque el coeficiente que multiplica al término n−1 no es constante; an =
an−1 . an−3 porque aparecen dos términos de la sucesión multiplicándose; an = (an−1 )2 + 1
porque aparece un término de la sucesión al cuadrado. Todas las demás son lineales.

1.2. Resolución de recurrencias lineales homogéneas

1.2.1. Primer orden
La recurrencia lineal homogénea de primer orden es de la forma

an = c · an−1 , n > 1

siendo c una constante dada. La solución general es de la forma an = α ·cn , donde α es una
constante a determinar con la condición inicial. Especı́ficamente, si la condición inicial es
a0 = A, debe cumplirse que a0 = α · c0 = α = A. Por lo tanto, la solución de la recurrencia
con la condición inicial dada es an = A · cn . Los ejemplos 12 y 13 se muestran soluciones
de este tipo.

Ejemplo 15. Considere la recurrencia 10an + 4an−1 = 0, n > 1 con condición inicial
a0 = 3. Despejando an de la igualdad anterior, resulta an = −(4/10) · an−1 . Luego, la
solución general es an = α · (−4/10)n . El coeficiente α se obtiene haciendo cumplir la
condición inicial para n=0: a0 = α · (−4/10)0 = 3. De aquı́ surge que α = 3.
La solución es an = 3(−4/10)n = 3(−1)n 4n /10n .
El término a4 es a4 = 3(−4/10)4 = 3 · 256/10000 = 0,0768.

Si la sucesión comienza desde a1 , la recurrencia puede estar dada de la siguiente forma:

an = c · an−1 , n > 2, con condición inicial a1 = A, la solución tiene la misma forma,
an = α · cn y debe cumplirse: a1 = α · c1 = α · c = A, entonces α = A/c. Por lo tanto, la
solución general es an = (A/c) · cn = A · cn−1 .

4
 1. Relaciones de recurrencia

Ejemplo 16. Sea la recurrencia 9an = an−1 para n > 2, con condición inicial a1 =
−1. Despejando an resulta an = (1/9)an−1 . Entonces la solución tiene la forma an =
α(1/9)n = α/9n .
Debe cumplirse la condición inicial dada para n=1, ası́ que: a1 = α/91 = −1. De
aquı́ surge que α = −9. Finalmente, la solución general es an = −9/9n = −1/9n−1 .
Debe notarse que la recurrencia también puede estar dada en la forma an+1 = c · an .
Ejemplo 17. Suponga que se tiene la recurrencia an+1 = (3/5)an para n > 0, con
condición inicial a0 = 1/5. La solución general puede plantearse: an = α(3/5)n . La
condición inicial indica que a0 = α(3/5)0 = 1/5, de donde α = 1/5. La solución es:
an = (1/5)(3/5)n = 3n /5n+1 .
La recurrencia dada expresa el término n + 1 en función de un término anterior. No es
correcto despejar an , llegar a an = (5/3)an+1 y dar la solución de la forma an = α · (5/3)n .
Ejemplo 18. Se realiza una experimentación sobre el tiempo que demora un determinado
algoritmo en resolver un problema, conociendo el tamaño de la entrada (por ejemplo, si la
entrada es un vector de datos, el tamaño es la cantidad de datos, la dimensión del vector).
Si el tamaño de la entrada es 4, el algoritmo tarda 3 segundos, y si el tamaño es 5, consume
4.5 segundos. Además, se sabe que el tiempo an que consume con una entrada n satisface
una relación de recurrencia linead homogénea de primer orden. Se desea predecir an para
cualquier n.
La recurrencia que rige la sucesión de tiempos es an = c · an−1 . Según la experimenta-
ción, para n = 5, a5 = c · a4 , es decir, 4,5 = c · 3. Ası́ surge que c = 1,5.
¿Cuánto tiempo consume el algoritmo si el tamaño de la entrada es 2? Se puede calcu-
lar, retrocediendo desde los datos, ya que se conoce la recurrencia: a4 = 1,5 · a3 , de donde
surge que a3 = 2. Luego, siendo a3 = 1,5 · a2 , se deduce que a2 = 4/3.
La solución general es an = A · cn = A · 1,5n .
A debe ser a0 , pero no se conoce. Sin embargo, haciendo n = 4, resulta a4 = 3 = A·1,54 ,
y A = 3 · 1,5(−4) . Ası́, an = 3 · 1,5n−4 es el tiempo que tarda el algoritmo para una entrada
de tamaño n.

1.2.2. Segundo orden

La recurrencia lineal homogénea de segundo orden es de la forma
an = c1 an−1 + c2 an−2 , n > 2
siendo c1 y c2 dos constantes dadas. Basados en lo que sucede en recurrencias de primer
orden, se intuye que tiene soluciones de la forma an = rn , para algún número r. ¿Existen
valores r tal que ésta sea la solución de la recurrencia de segundo orden? Si es ası́, an−1 =
rn−1 y an−2 = rn−2 . Reemplazando en la recurrencia:

an = c1 an−1 + c2 an−2
rn = c1 rn−1 + c2 rn−2
Dividiendo ambos miembros por rn−2 queda:
r2 = c1 r + c2

5
 1.2. Resolución de recurrencias lineales homogéneas

La igualdad resultante es una ecuación cuadrática, llamada ecuación caracterı́stica

de la recurrencia. De acuerdo al tipo de solución de la ecuación caracterı́stica, se obtienen
las soluciones de la recurrencia.

Raı́ces distintas. Si la ecuación cuadrática tiene dos raı́ces distintas, sean r1 y r2 ,

la recurrencia tiene una solución de la forma:

an = α1 r1n + α2 r2n

Los coeficientes α1 y α2 se obtienen usando las condiciones iniciales.

Si las condiciones iniciales son a0 = A y a1 = B, entonces debe cumplirse:

a0 = α1 r10 + α2 r20 = A
a1 = α1 r11 + α2 r21 = B

Resolviendo ese sistema de dos ecuaciones lineales con 2 incógnitas (α1 y α2 ), se obtienen
los valores de éstas. Veámoslo en ejemplos.
Ejemplo 19. Resolvamos la recurrencia an = 3an−1 − 2an−2 , n > 2, con condiciones
iniciales a0 = 1; a1 = 0. Antes de hallar la solución general, veamos los siguientes términos
de la sucesión:
para n=2, a2 = 3a1 − 2a0 = 3 · 0 − 2 · 1 = −2
para n=3, a3 = 3a2 − 2a1 = 3 · (−2) − 2 · 0 = −6
para n=4, a4 = 3a3 − 2a2 = 3 · (−6) − 2 · (−2) = −14
para n=5, a5 = 3a4 − 2a3 = 3 · (−14) − 2 · (−6) = −30
...
Veamos ahora la solución general. La ecuación caracterı́stica es r2 = 3r − 2. Las
soluciones son r1 = 2 y r2 = 1. La solución general es

an = α1 2n + α2 1n

Para hacer cumplir las condiciones iniciales, debe satisfacerse:

a0 = α1 20 + α2 10 = 1
a1 = α1 21 + α2 11 = 0

La solución del sistema es α1 = −1 y α2 = 2. Entonces, la solución es

an = −1 · 2n + 2 · 1n
= −2n + 2

Para verificar, nótese que, por ejemplo, a5 = −25 + 2 = −32 + 2 = −30, que coincide con
el valor obtenido antes.
Ejemplo 20. Dada la recurrencia de segundo orden √ an = (4/3)an−2
√ , la ecuación carac-
terı́stica es r2 = 4/3, que tiene soluciones r1 = 2/ 3 y r2 = −2/ 3. La solución puede
plantearse ( ) ( )
2 n −2 n
an = α1 √ + α2 √
3 3

6
 1. Relaciones de recurrencia

Si las condiciones iniciales son a0 = −2 y a1 = 0, los coeficientes se hallan resolviendo

el sistema ( )0 ( )0
−2
a0 = α1 √23 + α2 √ = α1 + α2 = −2
( )1 ( 3 )1
−2
a1 = α1 √23 + α2 √ 3
= α1 √23 − α2 √23 = 0
cuya solución es α1 = −1 y α2 = −1.
Entonces la solución de la recurrencia con las condiciones iniciales dadas es
( ) ( )
2 n −2 n
an = − √ − √
3 3
La sucesión comienza con los términos a0 = −2, a1 = 0, a2 = −8/3, a3 = 0, a4 =
−32/9, a5 = 0. Puede observarse que cuando n es impar, an = 0, y para n par de la forma
( )j
n = 2j, an = −2 43
Ejemplo 21. Resolvamos la recurrencia 2an + an−1 = an−2 , n > 3 con condiciones
iniciales a1 = 2, a2 = 1. Nótese que esta recurrencia describe una sucesión a partir de
a1 (no de a0 ). Despejando an , la recurrencia se puede escribir an = − 12 an−1 + 12 an−2 . La
ecuación caracterı́stica es r2 = − 12 r + 21 , o equivalentemente 2r2 + r − 1 = 0. Las raı́ces
de la ecuación caracterı́stica son r1 = −1 y r2 = 21 . La solución está dada entonces por
( )n
n 1
an = α1 (−1) + α2
2
Los coeficientes se determinan con las condiciones iniciales para n = 1 y n = 2,

a1 = α1 (−1)1 + α2 ( 12 )1 = −α1 + α2 /2 = 2
a2 = α1 (−1)2 + α2 ( 12 )2 = α1 + α2 /4 = 1

De aquı́ surgen los valores α1 = 0 y α2 = 4. Entonces, la solución de la recurrencia es

( )n
1 4
an = 4 = n
2 2
Ejemplo 22. Consideremos la recurrencia an+2 = 2an+1 + 4an , n > 0 con condiciones
iniciales a0 = 21 , a1 = 21 . La igualdad de la recurrencia dice: cada término (an+2 ) es igual
al doble del término anterior (an+1 ) más cuatro veces el anterior al anterior (an ). La
recurrencia es equivalente a

an = 2an−1 + 4an−2 n > 2

2 = 2r + 4, o equivalentemente r 2 − 2r − 4 = 0. Las raı́ces
La ecuación caracterı́stica es r√ √
de esta ecuación son r1 = 1 + 5 y r2 = 1 − 5. La solución está dada entonces por
√ √
an = α1 (1 + 5)n + α2 (1 − 5)n

Los coeficientes se determinan con las condiciones iniciales,

√ √
a0 = α1 (1 + √5)0 + α2 (1 − √5)0 = √α1 + α2 √ = 1
2
a1 = α1 (1 + 5)1 + α2 (1 − 5)1 = α1 (1 + 5) + α2 (1 − 5) = 1
2

7
 1.2. Resolución de recurrencias lineales homogéneas

1
De aquı́ surgen los valores α1 = 4 y α2 = 14 . Entonces, la solución de la recurrencia es

1 √ 1 √
an = (1 + 5)n + (1 − 5)n
4 4
Ejemplo 23. Se sabe que los primeros términos de una sucesión son a1 = 1, a2 = 2, a3 =
1,2, a4 = 1,28. También se sabe que la sucesión verifica una relación de recurrencia lineal
homogénea de orden 2. Se quiere hallar una expresión explı́cita para todos los términos de
la sucesión.
La recurrencia es de la forma an = c1 an−1 + c2 an−2 . Haciendo n = 3 y n = 4, se llega
a
a3 = c1 a2 + c2 a1 → 1,2 = 2c1 + c2
a4 = c1 a3 + c2 a2 → 1,28 = 1,2c1 + 2c2
Estas dos ecuaciones nos permiten obtener los valores de los coeficientes de la recurrencia,
c1 = 0,4, c2 = 0,4.
Para hallar la solución explı́cita de la recurrencia an = 0,4an−1 + 0,4an−2 se calculan
√
ecuación caracterı́stica r2 = 0,4r + 0,4. Las raı́ces son r1 = 0,2 + 0,2 11
las raı́ces de la √
y r1 = 0,2 − 0,2 11. √ √
Se llega a que la solución es an = α1 (0,2+0,2 11)n +α2 (0,2−0,2 11)n . Los coeficientes
α1 y α2 se pueden calcular reemplazando n por 1 y por 2 en la solución general:
√ √
a1 = 1 = α1 (0,2 + 0,2√11)1 + α2 (0,2 − 0,2√11)1
a2 = 2 = α1 (0,2 + 0,2 11)2 + α2 (0,2 − 0,2 11)2

Los valores de los coeficientes (aproximándolos con 4 cifras decimales) son α1 = 2,1508
y α2 = 1,8492.
Los términos de la sucesión,
√ √ expresados en función de n son an = 2,1508 · (0,2 +
0,2 11) + 1,8492 · (0,2 − 0,2 11) , para n > 1.
n n

Ejemplo 24. Se sabe que a1 = 1, a2 = −1, a3 = 1/3, a5 = 1/9 son términos de una
sucesión que satisface una recurrencia lineal de segundo orden homogénea de la forma
an = c1 an−1 + c2 an−2 .
Podrı́amos calcular c1 y c2 como en el ejemplo anterior. Pero en este caso no conocemos
a4 , ası́ que hay que hacer algunas cuentas más.
Reemplazando n por 3, por 4 y por 5, se llega a:

a3 = c1 a2 + c2 a1 → 1/3 = −c1 + c2
a4 = c1 a3 + c2 a2 → a4 = (1/3)c1 − c2
a5 = c1 a4 + c2 a3 → 1/9 = a4 c1 + (1/3)c2

Reemplazando a4 en la última ecuación, resulta el sistema de ecuaciones

1/3 = −c1 + c2
1/9 = (c1 /3 − c2 )c1 + c2 /3

De la primera ecuación surge que c2 = 1/3 + c1 , y reemplazando en la segunda: 1/9 =

(c1 /3 − (1/3 + c1 ))c1 + 1/3(1/3 + c1 ) = 1/9 − 2c21 /3
De aquı́, c1 = 0 y c2 = 1/3. Luego, la recurrencia es an = (1/3)an−2 .

8
 1. Relaciones de recurrencia

En caso de que las raı́ces sean complejas conjugadas, digamos r1 = a + ib y r2 = a − ib,

la solución tiene la misma forma:

an = α1 r1n + α2 r2n = α1 (a + ib)n + α2 (a − ib)n

Ejemplo 25. Resolvamos la recurrencia 4an + an−2 = 0, que es equivalente a an =

− 14 an−2 ; con condiciones iniciales a0 = −1, a1 = 1.
La ecuación caracterı́stica es r2 = − 14 , que tiene raı́ces r1 = 2i y r2 = − 2i .
La solución de la recurrencia es
( )n ( )n
i i
an = α1 + α2 −
2 2
los coeficientes α1 y α2 se calculan con las condiciones iniciales,
( )0 ( )0
a0 = α1 2i + α2 − 2i = α1 + α2 = −1
( i )1 ( i )1
a1 = α1 2 + α2 − 2 = i α21 − i α22 = 1

de donde surge que α1 = − 1+2i

2 y α2 = − 1−2i
2 . Finalmente, la solución de la recurrencia
es ( ) ( )n
1 + 2i i n 1 − 2i i
an = − − −
2 2 2 2
Si estamos interesados, por ejemplo, en el término a6 de la sucesión, se calcula de la
siguiente manera,
( i )6 1−2i ( i )6
a6 = − 1+2i
2 ( 2 ) − 2 (− 2 )
−1 1−2i −1
= − 1+2i
2 64 − 2 64
1
= 64

Ejemplo 26. La recurrencia del ejemplo 10 es an = an−1 − an−2 , que tiene ecuación√
caracterı́stica r2 − r + 1 = 0, cuyas raı́ces son complejas conjugadas: r1 = 12 + i 23 y
√
r2 = 1
2 −i 3
2 . Por lo tanto, la solución tiene la forma
( √ )n ( √ )n
1 3 1 3
an = α1 +i + α2 −i
2 2 2 2

Imponiendo las condiciones iniciales dadas en el ejemplo 10, se llega al sistema de ecua-
ciones para α1 y α2
( √ )0 ( √ )0
a0 = α1 1
2 +i 2
3
+ α2 1
2 −i 2
3

= α1 + α2 = 0
( √ )1 ( √ )1
a1 = α1 12 + i 23 + α2 12 − i 23
( √ ) ( √ )
= α1 12 + i 23 + α2 12 − i 23 = 1

9
 1.2. Resolución de recurrencias lineales homogéneas

de donde surgen los valores α1 = − √i3 y α2 = √i3 . Luego, la solución de la recurrencia

con las condiciones iniciales dadas es
( √ )n ( √ )n
i 1 3 i 1 3
an = − √ +i +√ −i
3 2 2 3 2 2

Verifiquemos que esta fórmula explı́cita nos da los valores de la sucesión correcta:
( √ )0 ( √ )0
a0 = − √i3 1
2 +i 2
3
+ √i 1
2 −i 2
3
=0
( √ )1
3
( √ )1
a1 = − √i3 1
2 + i 23 + √i 1
2 − i 23 = − 2√i 3 + 12 + 2√i 3 + 12 = 1
( √ )2
3
( √ )2 (( √ ) ( √ ))
−1
a2 = − √i3 1
2 + i 23 + √i 1
2 − i 23 = − √i3 2 +i 2
3
− −1 2 −i 2
3
=1
( √ )3
3
( √ )3
a3 = − √i3 1
2 + i 23 + √i 1
2 − i 23 = − √i3 (−1 − (−1)) = 0
( √ )4
3
( √ )4 (( √ ) ( √ ))
−1 −1
a4 = − √i3 1
2 + i 23 + √i
3
1
2 − i 23 = − √i3 2 − i 2
3
− 2 + i 2
3
= −1
...
Los valores hallados coinciden con los de la sucesión del ejemplo 10.

Raı́ces iguales. Si la ecuación cuadrática tiene dos raı́ces iguales, llamémosla r1 , la

recurrencia tiene una solución de la forma:
an = α1 · r1n + n · α2 · r1n
Los coeficientes α1 y α2 se obtienen usando las condiciones iniciales.
Si las condiciones iniciales son a0 = A y a1 = B, entonces debe cumplirse:
a0 = α1 · r10 + 0 · α2 · r10 = A
a1 = α1 · r11 + 1 · α2 · r11 = B
Resolviendo ese sistema de dos ecuaciones lineales con 2 incógnitas (α1 y α2 ), se obtienen
los valores de éstas.
Ejemplo 27. Dada la recurrencia an = 6an−1 − 9an−2 , n > 2, la ecuación caracterı́stica
correspondiente es r2 − 6r + 9 = 0, que tiene una raı́z doble r1 = 3. La solución es
an = α1 · 3n + n · α2 · 3n .
Teniendo condiciones iniciales a0 = − 15 y a1 = 53 , los coeficientes se encuentran
resolviendo el sistema:
a0 = α1 · 30 + 0 · α2 · 30 = α1 = − 15
a1 = α1 · 31 + 1 · α2 · 31 = 3α1 + 3α2 = 35
De allı́ surge que α1 = − 15 y α1 = 25 , y la solución de la recurrencia es an =
− 51 · 3n + 25 · n · 3n . Los primeros términos de la sucesión son:

a0 = − 15 · 30 + 2
5 · 0 · 30 = − 51
a1 = − 15 · 31 + 2
5 · 1 · 31 = − 53 + 6
5 = 5
3

a2 = − 15 · 32 + 2
5 · 2 · 32 = − 59 + 36
5 = 5
27

a3 = − 15 · 33 + 2
5 · 3 · 33 = − 27 162
5 + 5 = 5
135
= 27;

10
 1. Relaciones de recurrencia

Ejemplo 28. Dada la recurrencia 2an+2 −4an+1 = −2an , n > 0 la ecuación caracterı́stica
correspondiente es 2r2 − 4r + 2 = 0, o equivalentemente r2 − 2r + 1 = 0 que tiene una raı́z
doble r1 = 1. La solución es

an = α1 · 1n + n · α2 · 1n = α1 + n · α2

Teniendo condiciones iniciales a0 = 11 y a1 = 7, los coeficientes se encuentran resol-

viendo el sistema:
a0 = α1 + 0 · α2 = 11
a1 = α1 + 1 · α2 = 7
De allı́ surge que α1 = 11 y α1 = −4, y la solución de la recurrencia es an = 11 − 4n.
Los primeros términos de la sucesión son a0 = 11, a1 = 11 − 4 = 7, a2 = 11 − 4 · 2 = 3,
a3 = 11 − 4 · 2 = −1, a4 = 11 − 4 · 4 = −5, etc.

1.2.3. Orden superior

Una recurrencia lineal homogénea de orden k tiene la forma an = c1 an−1 +c2 an−2 +...+
ck an−k . Las soluciones serán una combinación lineal de soluciones del tipo rn , donde r es
raı́z de la ecuación caracterı́stica rk = c1 rk−1 +c2 rk−2 +...+ck . Si la ecuación caracterı́stica
tiene k raı́ces distintas r1 , r2 , ..., rk , la solución es

an = α1 r1n + α2 r2n + ... + αk rkn

donde los coeficientes αi se obtienen de k condiciones iniciales: a0 = A0 , a1 = A1 , ...,

ak−1 = Ak−1 .
Si una raı́z r tiene multiplicidad m, mayor que 1, en la solución se considera rn multi-
plicado por un polinomio de n, de orden m − 1.

1.3. Resolución de recurrencias lineales no homogéneas

Dada la recurrencia lineal no homogénea

an = c1 an−1 + c2 an−2 + ... + ck an−k + g(n)

la recurrencia homogénea asociada es

an = c1 an−1 + c2 an−2 + ... + ck an−k

es decir, la recurrencia homogénea que se obtiene de eliminar el término no homogéneo

g(n).
La solución de la recurrencia no homogénea es la suma de una solución particular apn
más una solución de la recurrencia homogénea asociada ahn . La solución queda entonces

an = ahn + apn

Ya hemos visto antes cómo obtener soluciones de recurrencias lineales, ahora nos cen-
traremos en hallar una solución particular de la recurrencia lineal no homogénea.

11
 1.3. Resolución de recurrencias lineales no homogéneas

Como solución particular se propone una sucesión apn que cumple la recurrencia. En
general, esta solución particular tiene la misma forma funcional que el término no ho-
mogéneo. Es decir, si el término no homogéneo es en , la solución particular tiene la misma
forma, apn = A en , donde A es una constante a determinar. En la siguiente tabla se mues-
tra la correspondencia entre el término no homogéneo y la solución particular para ciertos
casos1 .
g(n) apn
constante constante
n An + B
n2 An2 + Bn + C
sen n A sen n + B cos n
tn Atn
Ejemplo 29. Sea la recurrencia an = 2an−1 + 1, n > 1, a0 = 0. El término no homogéneo
es 1. Entonces se propone una solución particular constante, apn = A . La solución parti-
cular debe satisfacer la recurrencia. Como apn−1 = A, remplazando en la recurrencia:

apn = 2apn−1 + 1
A = 2A + 1

de donde surge A = −1.

La solución de la recurrencia homogénea asociada es ahn = α 2n . Luego, la solución es
an = ahn + apn = α2n − 1. Con la condición inicial, a0 = α20 − 1 = 0, entonces α = 1, por
lo que
an = 2n − 1
Ejemplo 30. Sea la recurrencia lineal no homogénea an + 2an−1 = 5 · 3n , n > 1, con
condición inicial a0 = −1. El término no homogéneo es 5 · 3n . La recurrencia homogénea
asociada es an + 2an−1 = 0. La solución de ésta es ahn = α · (−2)n .
Dado que el término no homogéneo tiene forma de potencia de 3, se propone apn =
A · 3n como solución particular. El coeficiente A se calcula de tal modo que se cumpla la
recurrencia. Entonces, se reemplaza la solución particular en la recurrencia, notando que
apn−1 = A · 3n−1 . Entonces, debe ser:

apn + 2apn−1 = 5 · 3n
A · 3 + 2A · 3
n n−1 = 5 · 3n

Dividiendo por 3n−1 , resulta: 3A + 2A = 5 · 3, de donde surge que A = 3. La solución

particular queda apn = 3 · 3n = 3n+1 .
Entonces, la solución de la recurrencia no homogénea dada es an = ahn + apn = α ·
(−2)n + 3n+1 . El coeficiente α se calcula con la condición inicial.
a0 = ah0 + ap0 = α · (−2)0 + 31 = α + 3 = −1, entonces α = −4. La solución resulta

an = −4(−2)n + 3n+1
1
La última fila de la tabla vale en el caso que t no sea raı́z de la ecuación caracterı́stica. En otro caso,
si t es raı́z de la ecuación caracterı́stica con multiplicidad m, la solución particular propuesta debe ser un
polinomio de n de grado m − 1

12
 1. Relaciones de recurrencia

Ejemplo 31. Considere la recurrencia lineal de segundo orden no homogénea

an = 4an−1 − an−1 + 2n

La recurrencia homogénea asociada es an = 4an−1 √ − an−1 , que √

tiene ecuación carac-
terı́stica r2 = 4r − 1, cuyas soluciones √
son r1 = 2 + √ 3 y r2 = 2 − 3. La solución de la
recurrencia homogénea es ahn = α1 (2 + 3)n + α2 (2 − 3)n .
El término no homogéneo es 2n. Por lo tanto, se propone una solución particular de la
forma apn = An + B. Entonces, apn−1 = A(n − 1) + B y apn−2 = A(n − 2) + B. Reemplazando
en la recurrencia:

apn = 4apn−1 − apn−2 + 2n

An + B = 4(A(n − 1) + B) − (A(n − 2) + B) + 2n
0 = (2A + 2)n − 2A + 2B

Esa igualdad debe cumplirse para todo n > 2, entonces debe ser 2A + 2 = 0 y −2A +
2B = 0 , de donde se llega a que A = −1, B = −1. Ası́, la solución particular es
apn = −n − 1.
La solución general es
√ √
an = ahn + apn = α1 (2 + 3)n + α2 (2 − 3)n − n − 1

Si las condiciones iniciales son a0 = −1 y a1 = 1, debe cumplirse:

√ √
a0 = α1 (2 + √3)0 + α2 (2 − √3)0 − 0 − 1 = α1 + α2√− 1 = −1 √
a1 = α1 (2 + 3)1 + α2 (2 − 3)1 − 1 − 1 = α1 (2 + 3) + α2 (2 − 3) − 2 = 1
√ √
La solución de este sistema de ecuaciones es α1 = 3/2 y α2 = − 3/2. La solución
de la recurrencia, con las condiciones iniciales dadas es
√ √
3 √ n 3 √
an = (2 + 3) − (2 − 3)n − n − 1
2 2

1.4. Problemas modelados con recurrencias

1.4.1. Modelos de crecimiento
Considere que se quiere estudiar la evolución de la cantidad de cuentas abiertas en una
red social. Después de estudios estadı́sticos se sabe que cada año, el número de cuentas en
la red crece un 12 % respecto del año anterior.
Si an denota el número de cuentas en el año n, el dato es que an = an−1 + 0, 12an−1 =
1, 12an−1 .
La solución de esta recurrencia es de la forma an = α · (1,12)n . Si en el año 1 hay A
cuentas abiertas, a1 = A = α · (1,12)1 , de donde α = A/1, 12. (Nótese que en este caso no
tiene sentido pensar en a0 , ya que se considera que la red comienza a funcionar en el año
1). Luego, an = A · (1, 12)n−1 .

13
 1.4. Problemas modelados con recurrencias

Si se quiere determinar cuándo la red superará los mil usuarios, dado que el primer
año tiene 96, se debe determinar n tal que an > 1000, siendo A = 96. Entonces:

96(1,12)n−1 > 1000

1000
(1,12)n−1 >
96
( )
1000
(n − 1) ln (1,12) > ln
96
( )
1000
n > ln / ln (1,12) + 1
96

Por lo tanto, n debe ser mayor que 21.678. Esto indica que durante el año 21, el número
de usuarios superará los 1000.
Este es el resultado matemático. Sin embargo, se podrı́a cuestionar si la predicción de
crecimiento será válida luego de tanto tiempo, y si la recurrencia sigue valiendo para esos
n. Pero eso es otro tema.
El modelo anterior predice que a medida que pasa el tiempo, la cantidad de cuentas
crece y crece sin lı́mite (es decir, tiende a ∞ cuando n tiende a ∞), situación que no puede
ser real.
Otro modelo de crecimiento de poblaciones es el conocido como modelo logı́stico. Éste
supone que existe un máximo posible para el tamaño de la población (dado por limitaciones
de espacio o recursos). Ası́, en cada etapa, la población an será en cierta forma proporcional
a la población en la etapa anterior (an−1 ) pero también proporcional a lo que falte para
alcanzar el máximo (M − an−1 ), donde M es el máximo que puede alcanzar la población.
El modelo puede escribirse
an = b · an−1 · (M − an−1 )
o, equivalentemente, an = b · M · an−1 − b · a2n−1 . Esta es una recurrencia no lineal, ya que
un término de la serie está elevado al cuadrado.

1.4.2. Préstamo con pagos parciales

Suponga que se recibe un préstamo de $C, que debe ser devuelto en cuotas fijas men-
suales con una tasa de interés mensual de I. Las cuotas son de $P.
Si an es el dinero adeudado al finalizar el mes n, este monto es igual a lo adeudado el
mes anterior, más los intereses generados, menos el pago realizado. Es decir:

an = an−1 + I · an−1 − P
= (1 + I) · an−1 − P
Se obtiene una relación de recurrencia lineal no homogénea de primer orden. La solución
es an = ahn + apn , donde ahn es la solución de la recurrencia homogénea asociada an =
(1 + I) · an−1 , y apn es una solución particular. En este caso, como el término no homogéneo
es constante, se propone una solución particular constante.
Entonces ahn = α · (1 + I)n y apn = A. Debe cumplirse la recurrencia para la solución
particular,

14
 1. Relaciones de recurrencia

apn = (1 + I) · apn−1 − P
A = (1 + I) · A − P
P
de donde surge que A = I. Luego,

P
an = α · (1 + I)n +
I
Usando la condición inicial a0 = C (porque al inicio de la inversión lo adeudado es el
monto del préstamo), tenemos que a0 = C = α · (1 + I)0 + PI . Despejando, α = C − PI , y
la solución queda ( )
P P
an = C − (1 + I)n +
I I
¿En cuántos meses (quedará) saldada la deuda? Nos preguntamos hasta qué n la deuda
será positiva, es decir, C − PI (1 + I)n + PI > 0.
( )
P P
C− (1 + I)n + > 0
I I
( )
P P
> − C (1 + I)n
I I
P 1
· (P ) > (1 + I)n
I − C
( I
)
P
ln > n · ln (1 + I)
P −I ·C
( )
P
ln / ln (1 + I) > n
P −I ·C

Si C=1000, P =70, I = 0,05, la desigualdad anterior es 25,67 > n. Entonces, al mes 26

la deuda queda saldada.
Observe que debe cumplirse que P − I · C > 0 y que I > 0. ¿Qué sucede si estas
desigualdades no se cumplen?

1.4.3. Operaciones necesarias en ordenamiento por burbuja

Un algoritmo muy conocido para ordenar una lista L de n números es

para i=1 a n-1

para j=n a i+1
si L(j)<L(j-1)
aux=L(j-1)
L(j-1)=L(j)
L(j)=aux
fin si
fin para
fin para

15
 1.4. Problemas modelados con recurrencias

El algoritmo consta de dos bucles. En el bucle para interno se comparan, comenzando

desde el último, un término de la lista con el anterior. Si el anterior es mayor, se inter-
cambian sus valores. En el primer paso del bucle exterior, el menor número de la lista
”sube”(como una burbuja ascendiendo en un fluı́do) hasta la primera posición. En el se-
gundo paso del ciclo exterior, el segundo menor número sube hasta la segunda posición, y
ası́ sucesivamente.
Estamos interesados en contar la cantidad de comparaciones que debe realizar el al-
goritmo para ordenar una lista de n números. Ésta es una medida de la complejidad
del algoritmo. Denotemos an la cantidad de comparaciones que realiza el algoritmo para
ordenar n números. Se puede observar que en el primer bucle para se realizan (n − 1) com-
paraciones, y con ésto, el menor número toma su posición. Después el algoritmo ordena
los restantes números, que son (n − 1) números. Para ésto, realiza an−1 comparaciones.
Entonces, se deduce que debe cumplirse

an = an−1 + n − 1, n > 2

Si la lista tiene 1 elemento, el algoritmo la ordena en a1 = 0 comparaciones. Los primeros

términos de la sucesión ası́ descrita son:
a1 = 0
a2 = 0 + (2 − 1) = 1
a3 = 1 + (3 − 1) = 1 + 2 = 3
a4 = 3 + (4 − 1) = 1 + 2 + 3 = 6
a5 = 6 + (5 − 1) = 1 + 2 + 3 + 4 = 10
...
an = 1 + 2 + 3 + ... + (n − 1) = n(n − 1)/2

Entonces, an = (n2 − n)/2. Luego, para ordenar, por ejemplo, una lista de 10 números se
realizan a10 = (102 − 10)/2 = 90/2 = 45 comparaciones.
Esta medida de complejidad del algoritmo nos dice que requiere una cantidad de com-
paraciones del orden del cuadrado del tamaño de la entrada. Esto se denota O(n2 ).
Nótese que lo analizado anteriormente es independiente del orden de los números en
la lista dada. Es decir, en una lista de 10 números, el algoritmo realiza 45 comparaciones
en cualquier caso, aún si los 10 números son dados en forma ordenada.

1.4.4. Construcciones geométricas recursivas (fractales)

Conjunto de Cantor
Considere un proceso geométrico tal que, a partir de un segmento, realiza una operación
recursivamente. La operación considerada es la siguiente: a cada segmento resultante en
la etapa anterior, se lo divide en tres partes de igual longitud y se elimina la parte central.
Si el proceso comienza con un segmento de longitud 1, luego del primer paso se tienen
dos segmentos cuyas longitudes suman 2/3 (véase figura 1.1).
En la etapa siguiente (etapa 2) se aplica la operación a los dos segmentos resultantes,
se eliminan de cada uno su tercio central, es decir, se eliminan dos segmentos de longitud
1/9 cada uno. La suma de las longitudes de los segmentos que quedan es 2/3-2/9 = 4/9.

16
 1. Relaciones de recurrencia

Etapa 0

Etapa 1

Etapa 2

Etapa 3

Figura 1.1: Construcciones geométricas recursivas: Conjunto de Cantor

Si en la etapa n la suma de las longitudes de los segmentos es an , la transformación

siguiente elimina 1/3 de cada segmento, entonces an+1 = an − 13 an = 23 an . Si se comienza
con un segmento de longitud( 2 )n 1 (a0 = 1), entonces, en la etapa n se tienen segmentos con
una longitud total an = 3 .
Puede observarse que cuando n tiene a ∞, la longitud total tiende a cero.
Después de infinitas etapas, se obtiene un conjunto de puntos, conocido como conjunto
de Cantor. Este conjunto tiene asombrosas propiedades. Por un lado, existen infinitos
puntos en el conjunto de Cantor. Obsérvese que los puntos 0, 1/3, 2/3, 1/9, 2/9, etc.
nunca son eliminados, por lo tanto, después de infinitas operaciones, estos puntos siguen
estando en el conjunto. Pero como ya se dijo, la longitud de este conjunto es 0. Por lo
tanto, no contiene ningún segmento. Sin embargo, tiene tantos puntos como el conjunto
de números reales.
Por otro lado, tiene la propiedad de autosimilitud: si miramos con lupa una parte del
conjunto, será similar al conjunto entero. Es decir, una parte es similar al todo.
Otra caracterı́stica interesante de mencionar es su dimensión. Se sabe que un segmento
tiene dimensión 1, un punto tiene dimensión 0. El conjunto de Cantor no es un segmento
(ni un conjunto de segmentos)y no es un punto (ni un conjunto finito de ellos). Entonces
su dimensión no es 1 ni es 0. La dimensión 2 del conjunto de Cantor es ln ln 3 ≈ 0,6309.
2

Las propiedades de autosimilitud y dimensión fraccionaria son caracterı́sticas de los

fractales. Éstos son objetos geométricos que escapan de la geometrı́a euclidiana.

Curva de Koch
Consideremos otro proceso geométrico similar. Se realiza en cada paso la siguiente
transformación: a cada uno de los segmentos, se lo divide en tres segmentos de igual
longitud, y el segmento central se lo reemplaza por dos segmentos de igual longitud,
formando una carpa (figura 1.2).
2
El concepto de dimensión que se aplica a estos objetos geométricos es la dimensión de Hausdorff

17
 1.4. Problemas modelados con recurrencias

Etapa 0

Etapa 1

Etapa 2

Etapa 3

Etapa 4

Figura 1.2: Construcciones geométricas recursivas: Curva de Koch

Aquı́, de un segmento de una determinada longitud, luego de la transformación, quedan

4 segmentos de igual longitud, que es 1/3 de la longitud del segmento que los originó.
Entonces, siendo an la suma de las longitudes de todos los segmentos en la etapa n, se
cumple la recurrencia an+1 = 43 an . Comenzando
( )n con un segmento de longitud 1 (es decir,
a0 = 1), se obtiene la solución an = 43 , que indica la longitud de la curva resultante en
el paso n.
Cuando n tiende a ∞, la longitud de la curva tiende a ∞. La curva resultante en
el lı́mite se conoce con el nombre de curva de Koch. Es una curva acotada de longitud
infinita. Ésta tiene la particularidad de ser una curva continua pero ninguno de sus puntos
admite una tangente (no es suave en ningún punto).
La dimensión fractal de la curva de Koch es ln ln 3 ≈ 1,2619. Intuitivamente, esto indica
4

que cubre más que una curva, pero menos que una superficie.
Nótese que este objeto geométrico también tiene la propiedad de autosimilitud y di-
mensión fraccionaria.

1.4.5. Expresiones aritméticas válidas

Considere que se quiere contar la cantidad de expresiones aritméticas válidas que usan
n sı́mbolos (dı́gitos o signos de operación). Para simplificar el análisis, consideremos que
se tienen 10 dı́gitos (del 0 al 9) y dos signos de operación, + y *. Expresiones válidas son

18
 1. Relaciones de recurrencia

45+2*3, 1+0+9*4+1; mientras que no son válidas las expresiones *87+1, 12*+9, etc.
Sea an el número de expresiones aritméticas válidas con n sı́mbolos. Claramente a1 =
10, ya que las expresiones válidas de un sı́mbolo son los dı́gitos de 0 a 9. a2 = 100, ya que
las expresiones de dos sı́mbolos son 00, 01, ..., 10, 11, ...98, 99 3 .
Analicemos las cadenas de tres sı́mbolos. Si los dos últimos sı́mbolos en una cadena de
tres son dos dı́gitos, entonces tal expresión puede formarse a partir de una expresión de
dos sı́mbolos, agregándole un dı́gito de 0 a 9. El total de estas expresiones es 10 a2 . Si los
dos últimos dı́gitos de una expresión aritmética de tres sı́mbolos es un signo y un dı́gito,
tal expresión puede obtenerse de una expresión de un sı́mbolo, agregándole un signo (+,*)
y un dı́gito (0,1,...,9). Entonces, la candidad de estas expresiones es 20 a1 . Finalmente,
hemos obtenido que a3 = 10 a2 + 20 a1 = 10 · 100 + 20 · 10 = 1200.
El análisis recién expuesto se puede extender al caso general de expresiones de n sı́mbo-
los. Las expresiones de n sı́mbolos que terminan en dos dı́gitos se pueden contar notando
que se pueden obtener agregando un dı́gito a las expresiones de n − 1 sı́mbolos. Y las ex-
presiones de n sı́mbolos que terminan en un signo y un dı́gito se pueden obtener agregando
un signo y un dı́gito a las expresiones de n − 2 sı́mbolos. Luego, an = 10an−1 + 20an−2 , y
esto vale para n > 3.
Resolvamos la recurrencia.
√ La ecuación
√ caracterı́stica es r2 − 10r − 20 = 0, cuyas
raı́ces son
√ r1 = 5 + 3 5 √ y r2 = 5 − 3 5. Por lo tanto, la solución tiene la forma an =
α1 (5 + 3 5)n + α2 (5 − 3 5)n . Los coeficientes se obtienen con las condiciones iniciales
para n = 1 y n = 2:
√ √
a1 = α1 (5 +√3 5) + α2 (5 − 3√ 5) = 10
a2 = α1 (5 + 3 5)2 + α2 (5 − 3 5)2 = 100
√ √
De aquı́ surge que α1 = 5/3 y α2 = − 5/3. Por lo tanto, el número de expresiones
aritméticas válidas de n sı́mbolos es
√ √
5 √ n 5 √
an = (5 + 3 5) − (5 − 3 5)n
3 3
(Sı́, aunque parezca difı́cil de creer, para cada n esa expresión es un número natural)

1.4.6. Conteo de cadenas binarias

Suponga que se quiere contar la cantidad de cadenas de 0 y 1 de longitud n que no
tienen dos 1 consecutivos. Sea an la cantidad de tales cadenas.
Claramente a1 = 2 (las cadenas de longitud 1 que no tiene dos 1 consecutivos son: 0 y
1); y a2 = 3 (las cadenas de longitud 2 que no tienen dos 1 consecutivos son: 00, 01, 10).
Pensemos ahora cómo generar las cadenas de longitud 3 con la condición establecida.
¿Cómo se pueden obtener a partir de cadenas de menor longitud? Note que dada una
cadena de longitud 2, podemos obtener cadenas de longitud 3 agregando un 0 ó un 1 al
final. Al hacer eso, quedarı́an las cadenas: 000, 001, 010, 011, 100, 101. Pero la cadena 011
3
Para ser rigurosos, habrı́a que decir que no es válida una expresión de dos dı́gitos que comience con 0.
Sin embargo, acá las contamos como válidas, ya que en otro caso la recurrencia serı́a de orden mayor, y el
análisis para su deducción más complicado

19
 1.4. Problemas modelados con recurrencias

no es admitida. ¿Por qué? Porque la cadena de longitud 2 que la genera termina con 1,
al agregarle un 1 al final, aparecen dos 1 seguidos, lo que no es admitido. Entonces, las
cadenas de longitud 3 que no tienen dos 1 seguidos se generan agregando un 0 ó un 1 a
cadenas de longitud 2 que no terminen en 1, y agregando un 0 a las cadenas de longitud 2
(0)
que terminan en 1. ¿Cuántas son? Llamando a2 a las cadenas de longitud 2 que terminan
(1) (0) (1)
en 0, y a2 a las cadenas de longitud 2 que terminan en 1, resulta a3 = 2a2 + a2 . Dado
(0) (1) (0)
que a2 = a2 + a2 , entonces a3 = a2 + a2 . Las cadenas de longitud 2 que terminan en 0
pueden obtenerse a partir de una cadena de longitud 1, agregando un 0 al final. Entonces,
(0)
a2 = a1 . Luego, a3 = a1 + a2 .
Con un razonamiento similar para cadenas de longitud n, se obtiene que an = an−1 +
an−2 para n > 3. √
La ecuación caracterı́stica es r2 − r − 1 = 0, que tiene por solución r1 = 1+2 5 y
√ ( √ )n ( √ )n
r2 = 1−2 5 . La solución de la recurrencia tiene la forma an = α1 1+2 5 + α2 1−2 5 .
√
5+3 5
Con las condiciones iniciales a1 = 2 y a2 = 3 se obtienen los valores α1 = y
√ 10
5−3 5
α2 = 10 , por lo tanto
( √ )( √ )n ( √ )( √ )n
5+3 5 1+ 5 5−3 5 1− 5
an = +
10 2 10 2

Haciendo los cálculos necesarios de acuerdo a la expresión obtenida, obtenemos que

a3 = 5, a4 = 8, a5 = 13, a6 = 21, etc.

1.4.7. Complejidad de un algoritmo recursivo

La sucesión de Fibonacci se define de la siguiente forma:
•F0 = 0, F1 = 1
•Fn = Fn−1 + Fn−2 para n > 2

La recurrencia que la define es igual a la recurrencia que aparece en el modelo anterior,

pero cambian las condiciones iniciales.
Una función recursiva para calcular el término n-ésimo de la sucesión de Fibonacci es:
función fib(n)
si n=0, fib=0;
si n=1, fib=1;
si n>=2; fib=fib(n-1)+fib(n-2);
fin
Se quiere medir la complejidad de este algoritmo contando la cantidad de sumas ne-
cesarias para calcular f ib(n). Sea an dicha cantidad. Si n = 0, no realiza suma alguna,
entonces a0 = 0. Si n = 1, igualmente, no realiza suma, a1 = 0. Para n mayores la función
se llama ası́ misma con los parámetros n − 1 y n − 2, y suma los resultados obtenidos. En-
tonces, la cantidad de sumas que realiza es la cantidad de sumas necesarias para calcular
f ib(n − 1), que son an−1 , más la cantidad de sumas que ejecuta para calcular f ib(n − 2),
que son an−2 , más 1.

20
 1. Relaciones de recurrencia

Luego, an = an−1 + an−2 + 1. Es una relación de recurrencia de segundo orden li-

neal no homogénea. La( recurrencia
√ )n
homogénea
( √ )n asociada es como la del modelo anterior,
1+ 5
h
por lo tanto an = α1 2 + α2 1−2 5 . El término no homogéneo es constante,
ası́ que se propone una solución particular constante: apn = A. Como ésta debe satisfacer
la recurrencia, debe ser A = A + A + 1, de donde ( surge
√ )n
A=(−1. √ )
n
La solución tiene la forma an = ahn +apn = α1 1+2 5 +α2 1−2 5 −1. Los coeficientes
se obtienen con las condiciones iniciales a0 = 0 y a1 = 0, dando lugar a la solución
( √ )( √ )n ( √ )( √ )n
1+ 5 1+ 5 1− 5 1− 5
an = √ − √ −1
2 5 2 2 5 2
( √ ) ( √ )n
Notar que cuando n se hace grande, an es parecido a 1+ √ 5
2 5
1+ 5
2 , ya que el segundo
término tiende a 0. Es decir, que la cantidad de sumas es proporcional a una potencia
n-ésima
(( √de)nuna) constante. Esto se expresa diciendo que la complejidad del algoritmo es
O 1+ 5
2 . La complejidad exponencial de este algoritmo no lo hace muy atractivo
en la práctica. De hecho, un algoritmo iterativo para calcular los términos de la serie de
Fibonacci es mucho más eficiente, exhibiendo complejidad lineal (O(n)).

21