Tarea 5, Matemáticas discretas

Fecha de entrega: 4 de marzo

Problema 1

¿Cuántos subconjuntos de {1, 2, 3, ..., n} no contienen dos enteros consecutivos?

Problema 2

1. Muestra que $latex F_{3n}$ es par.


2. Muestra que $latex F_{5n}$ es divisible entre 5.

Problema 3

Muestra las siguientes identidades.

1. $latex F_1 + F_3 + \ldots + F_{2n-1} = F_{2n}$


2. $latex F_0^2 + F_1^2 + F_2^2 + \ldots + F_n^2 = F_n\cdot F_{n+1}$


3. $latex \displaystyle \binom{n}{0}F_0 + \binom{n}{1}F_1 + \binom{n}{2}F_2 + \ldots + \binom{n}{n}F_n = F_{2n}$


4. $latex \displaystyle \binom{n}{0}F_1 + \binom{n}{1}F_2 + \binom{n}{2}F_3 + \ldots + \binom{n}{n}F_{n+1} = F_{2n+1}$

Problema 4

Los números de Lucas $latex L_0, L_1, L_2, L_3, \ldots$ satisfacen la ecuación de recurrencia

$latex L_n = L_{n-1} + L_{n-2}$

con términos iniciales $latex L_0 = 2, L_1 = 1$.

1. Muestra que $latex L_n = F_{n-1} + F_{n+1}$ para $latex n\ge1$.


2. Encuentra una fórmula explícita para $latex L_n$.

Problema 5

Resuelve las siguientes ecuaciones de recurrencia.

1. $latex x_n = x_{n-1} + 9x_{n-2} - 9x_{n-3},\quad n\ge3;\qquad x_0=0, x_1 = 1, x_2 = 2$


2. $latex x_n = 3x_{n-1} + 2,\quad n\ge1;\qquad x_0 = 1$


3. $latex x_n = 3x_{n-1} - 2,\quad n\ge1;\qquad x_0 = 1$


4. $latex x_n = 6x_{n-1} - 9x_{n-2} + 2n,\quad n\ge2; \qquad x_0 = 1, x_1 = 0$


5. $latex x_n = 4x_{n-1} + 4^n,\quad n\ge1; \qquad x_0 = 3$