_relaciones_de_recurrencia

Vista previa del material en texto

UNSL MATEMATICA DISCRETA 2018
TRABAJO PRACTICO
Relaciones de Recurrencia
1. En cada caso, encuentre una relación de recurrencia y condiciones iniciales que generen una sucesión
que comience con los términos dados.
(a) 3, 7, 11, 15, . . . .
(b) 3, 6, 9, 15, 24, 39, . . . .
(c) 1, 1, 2, 4, 16, 128, 4096, . . . .
2. Suponga que una persona invierte $2000 cada año a un interés anual compuesto del 10%. Sea An
la cantidad de dinero al final de n años.
(a) Encuentre una relación de recurrencia para la sucesión A0, A1, A2, . . ..
(b) Encuentre una condición inicial para la sucesión A0, A1, A2, . . ..
(c) Encuentre A1 y A2.
(d) ¿Cuánto dinero recupera esta persona si al finalizar el tercer año decide retirarlo y no volver
a invertir?
(e) Encuentre una fórmula expĺıcita para An.
3. Suponga que una persona invierte $3000 al 12% de interés anual compuesto en un plazo fijo que se
renueva cada trimestre. Sea An la cantidad de dinero al final de n años.
(a) Encuentre una relación de recurrencia para la sucesión A0, A1, A2, . . . .
(b) Encuentre una condición inicial para la sucesión A0, A1, A2, . . . .
(c) Encuentre A1, A2 y A3.
(d) Encuentre una fórmula expĺıcita para An.
(e) ¿Cuánto tiempo tomará que esta persona duplique su inversión inicial?
4. Sea Pn el número de permutaciones de n objetos diferentes.
(a) Encuentre una relación de recurrencia y una condición inicial para la sucesión P1, P2, . . . .
(b) Encuentre una fórmula expĺıcita para Pn.
5. Suponga que tiene n pesos y que, mientras le alcance el dinero, cada d́ıa compra una de las siguientes
bebidas: jugo ($1), leche ($2) o cerveza ($2). Si Gn denota el número de maneras de gastar todo el
dinero, argumente la validez de la siguiente relación de recurrencia para n ¥ 1:
Gn � Gn�1 � 2Gn�2.
Tomar en cuenta el orden. Por ejemplo, hay 11 maneras de gastar $4: LC, CL, JJL, JJC, JLJ,
JCJ, LJJ, CJJ, JJJJ, LL, CC
6. Sea Sn el número de cadenas de n bits que no contienen el patrón 010. Encuentre una relación de
recurrencia y condiciones iniciales para la sucesión tSnu.
7. Sea Sn el número de cadenas de n bits que no contienen el patrón 000. Encuentre una relación de
recurrencia y condiciones iniciales para la sucesión tSnu.
8. Sea Sn el número de cadenas de n bits que no contienen el patrón 00. Encuentre una relación de
recurrencia y condiciones iniciales para la sucesión tSnu. Muestre que Sn � Fn�2, donde Fn es el
n-ésimo término de la sucesión de Fibonacci.
1
UNSL MATEMATICA DISCRETA 2018
9. El n-ésimo número de Catalan Cn es igual al número de rutas de la esquina inferior izquierda de
una rejilla cuadrada de n � n a la esquina superior derecha si estamos restringidos a viajar sólo a
la derecha o hacia arriba y si se permite tocar pero no pasar arriba de la diagonal entre la esquina
inferior izquierda y la superior derecha. Tal ruta recibe el nombre de ruta buena. Mostrar que los
números de Catalan verifican la relación de recurrencia
Cn �
ņ
k�1
Ck�1Cn�k
10. Considere la sucesión g1, g2, . . . definida por la relación de recurrencia
gn � gn�1 � gn�2 � 1 para n ¥ 3,
y las condiciones iniciales
g1 � 1, g2 � 3.
Utilizando inducción matemática o de otra manera, demuestre que
gn � 2fn�1 � 1 para n ¥ 1,
donde f1, f2, . . . es la sucesión de Fibonacci.
11. Inspeccionando con valores pequeños de n, proponga una relación de recurrencia para Cpn, kq, el
número de subconjuntos de k elementos de un conjunto de n elementos.
12. Para cada una de las siguientes relaciones de recurrencia diga si es homogénea lineal con coeficientes
constantes y, en caso de serlo, indique su orden.
(a) an � �3an�1.
(b) an � 2nan�1.
(c) an � an�1 � n.
(d) an � 7an�2 � 6an�3.
(e) an � an�1 � 1� 2n�1.
(f) an � plogp2qan�1 � πan�2.
(g) an � �an�1 � an�2.
(h) an � 5an�1an�2 � 3an�3.
13. En cada caso, resuelva la relación indicada para las condiciones iniciales que se señalan.
(a) Ejercicio 1 (a); a0 � 2.
(b) Ejercicio 1 (b); a0 � 1.
(c) Ejercicio 1 (c); a0 � 0.
(d) an � 2nan�1, n ¡ 0; a0 � 1.
(e) an � 6an�1 � 8an�2; a0 � 1, a1 � 0.
(f) 9an � 6an�1 � an�2; a0 � 6, a1 � 5.
14. Resuelva la relación de recurrencia obtenida en en el ejercicio 5.
15. La población de Utoṕıa aumenta en un 5% cada año. En el año 2000 la población era de 10,000.
¿Cuál era la población en 1970?
16. Algunas veces, una relación de recurrencia que no es una ecuación lineal homogénea con coeficientes
constantes se puede transformar en una ecuación de este tipo. En cada uno de los siguientes
casos, realice la sustitución que se indica y resuelva la relación de recurrencia resultante. Después,
encuentre la solución de la relación de recurrencia original.
(a)
?
an � ?an�1�2?an�2, con condiciones iniciales a0 � a1 � 1. Haga la sustitución bn � ?an.
2
UNSL MATEMATICA DISCRETA 2018
(b) an �
b
an�2
an�1
, con condiciones iniciales a0 � 8, a1 � 1{p2
?
2q . Tome logaritmos en ambos
lados y haga la sustitución bn � logpanq.
17. Demuestre que
fn�1 ¥
�
1�?5
2
n�1
para n ¥ 1,
donde f denota la sucesión de Fibonacci.
18. La ecuación
an � c1an�1 � c2an�2 � fpnq
se llama relación de recurrencia lineal no homogénea de segundo orden con coeficientes constantes.
Demuestre que si gpnq es una solución de dicha relación, cualquier otra solución U de la misma es
de la forma
Un � Vn � gpnq,
donde V es una solución de la ecuación homogénea an � c1an�1 � c2an�2.
19. La ecuación
an � fpnqan�1 � gpnqan�2
se llama relación de recurrencia lineal homogénea de segundo orden. Demuestre que si S y T son
soluciones de dicha relación, entonces bS � dT , con b y d constantes, también lo es.
20. Dé una demostración alternativa del Teorema 7.2.14 utilizando inducción matemática.
3