9.9: Ejercicios

1. Escribe cada una de las siguientes ecuaciones de recurrencia como ecuaciones de operador de avance.

a.\(r_{n+2} = r_{n+1} +2r_n\)

b.\(r_{n+4} = 3r_{n+3} - r_{n+2} + 2r_n\)

c.\(g_{n+3} = 5g_{n+1} - g_n + 3^n\)

d.\(h_n = h_{n-1} - 2h_{n-2} + h_{n-3}\)

e.\(r_n = 4r_{n-1} + r_{n-3} - 3r_{n-5} + (-1)^n\)

f.\(b_n = b_{n-1} + 3b_{n-2} + 2^{n+1} - n^2\)

2. Resolver la ecuación de recurrencia\(r_{n+2}=r_{n+1}+2r_n\) si\(r_0=1\) y\(r_2=3\) (Sí, especificamos un valor para\(r_2\) pero no para\(r_1\)).

3. Encuentra la solución general de la ecuación de recurrencia\(g_{n+2} = 3g_{n+1} - 2g_n\).

4. Resolver la ecuación de recurrencia\(h_{n+3}=6h_{n+2}−11h_{n+1}+6h_n\) si\(h_0=3\)\(h_1=2\),, y\(h_2=4\).

5. Encuentra una fórmula explícita para el número de\(n^{th}\) Fibonacci\(f_n\). (Véase la subsección 9.1.1.)

6. Para cada ecuación de operador de avance a continuación, dé su solución general.

a.\((A-2)(A+10)f = 0\)

b.\((A^2 - 36)f = 0\)

c.\((A^2 - 2A - 5)f = 0\)

d.\((A^3 - 4A^2 - 20A + 48)f = 0\)

e.\((A^3 + A^2 - 5A + 3)f = 0\)

f.\((A^3 + 3A^2 + 3A + 1)f = 0\)

7. Resolver la ecuación del operador de avance\((A^2+3A−10)f=0\) si\(f(0)=2\) y\(f(1)=10\).

8. Dar la solución general a cada ecuación de operador de avance a continuación.

a.\((A-4)^3(A+1)(A-7)^4(A-1)^2f = 0\)

b.\((A+2)^4(A-3)^2(A-4)(A+7)(A-5)^3g = 0\)

c.\((A-5)^2(A+3)^3(A-1)^3(A^2-1)(A-4)^3h = 0\)

9. Para cada ecuación de operador de avance no homogénea, encuentre su solución general.

a.\((A-5)(A+2)f = 3^n\)

b.\((A^2 + 3A - 1)g = 2^n + (-1)^n\)

c.\((A-3)^3f = 3n + 1\)

d.\((A^2 + 3A - 1)g = 2n\)

e.\((A-2)(A-4)f = 3n^2 + 9^n\)

f.\((A+2)(A-5)(A-1)f = 5^n\)

g.\((A-3)^2(A+1)g = 2 \cdot 3^n\)

h.\((A-2)(A+3)f = 5n2^n\)

i.\((A-2)^2(A-1)g = 3n^22^n + 2^n\)

j.\((A+1)^2(A-3)f = 3^n +2n^2\)

10. Buscar y resolver una ecuación de recurrencia para el número\(g_n\) de cadenas ternarias de longitud\(n\) que no contienen 102 como subcadena.

11. Hay un famoso rompecabezas llamado las Torres de Hanoi que consta de tres clavijas y discos\(n\) circulares, todos de diferentes tamaños. Los discos comienzan en la clavija más a la izquierda, con el disco más grande en la parte inferior, el segundo más grande en la parte superior, y así sucesivamente, hasta el disco más pequeño en la parte superior. El objetivo es mover los discos para que queden apilados en este mismo orden en la clavija más a la derecha. Sin embargo, se le permite mover solo un disco a la vez, y nunca podrá colocar un disco más grande encima de un disco más pequeño. Dejar\(t_n\) denotar la menor cantidad de movimientos (siendo un movimiento tomar un disco de una clavija y colocarlo sobre otro) en el que puedas lograr el objetivo. Determinar una fórmula explícita para\(t_n\).

12. Un identificador de base de datos válido de longitud se\(n\) puede construir de tres maneras:

• Comenzando con\(A\) y seguido de cualquier identificador válido de longitud\(n-1\).
• Comenzando con una de las cadenas de dos caracteres\(1A, 1B, 1C, 1D, 1E\), o\(1F\) y seguido de cualquier identificador válido de longitud\(n-2\).
• tarting con 0 y seguido de cualquier cadena ternaria (\(\{0,1,2\}\)) de longitud\(n−1\).

Encuentre una recurrencia para el número\(g(n)\) de identificadores de base de datos de longitud\(n\) y luego resuelva su recurrencia para obtener una fórmula explícita para\(g(n)\). (Puede considerar la cadena vacía de longitud 0 un identificador de base de datos válido, haciendo\(g(0)=1\). Esto simplificará la aritmética.)

13. Dejar\(t_n\) ser el número de formas de teselas de un\(2 \times n\) rectángulo usando\(1 \times 1\) mosaicos y\(L\) -tiles. Un\(L\) -tile es un\(2 \times 2\) mosaico con el\(1 \times 1\) cuadrado superior derecho eliminado. (Un\(L\) mosaico puede ser girado para que el cuadrado “faltante” aparezca en cualquiera de las cuatro posiciones.) Encuentre una fórmula recursiva para\(t_n\) junto con suficientes condiciones iniciales para comenzar la recursión. Utilice esta fórmula recursiva para encontrar una fórmula cerrada para\(t_n\).

14. Probar Lemma 9.22 sobre ecuaciones de operador de avance con raíces repetidas.

15. Utilice funciones generadoras para resolver la ecuación de recurrencia\(r_n=r_{n−1}+6r_{n−2}\) para\(n \geq 2\) con\(r_0=1\) y\(r_1=3\).

16. Vamos\(a_0=0, a_1=2\), y\(a_2=5\). Utilice funciones generadoras para resolver la ecuación de recurrencia\(a_{n+3}=5a_{n+2}−7a_{n+1}+3a_n+2^n\) para\(n \geq 0\).

17. Vamos\(b_0=1, b_2=1\), y\(b_3=4\). Utilice funciones generadoras para resolver la ecuación de recurrencia\(b_{n+3}=4b_{n+2}−b_{n+1}−6b_n+3^n\) para\(n \geq 0\).

18. Usa funciones generadoras para encontrar una fórmula cerrada para los números de Fibonacci\(f_n\).

19. ¿Cuántos árboles enraizados, sin etiquetar, binarios, ordenados (RuBots) con 6 hojas hay? Dibuja 6 RuBots distintos con 6 hojas.

20. En este capítulo, desarrollamos una función generadora para los números catalanes. Primero nos encontramos con los números catalanes en el capítulo 2, donde aprendimos que cuentan ciertos caminos de celosía. Desarrollar una recurrencia para el número ln de trayectorias de celosía similar a la recurrencia

\(c_n = \displaystyle \sum_{k=0}^n c_kc_{n-k}\)para\(n \geq 2\)

para RuBots al pensar en formas de romper un camino de celosía de (0,0) a\((n,n)\) eso no cruza la diagonal\(y=x\) en dos caminos de celosía más pequeños de este tipo.