Problemas

Recurrencias

1. Dada la sucesión \(a_0=0\), \(a_{n+1}=2a_n+1\) para \(n \geq 0\):

   • Calcula algunos términos y conjetura una fórmula para \(a_k\)
   • Escribe la función generatriz y halla su fórmula usando la definición recursiva
   • Haz la descomposición en fracciones parciales para demostrar tu fórmula

2. Dada la sucesión \(a_0=1\), \(a_{n+1}=2a_n + n\) para \(n \geq 0\), halla una fórmula para \(a_k\) siguiendo los mismos pasos del problema anterior.

3. La sucesión de Lucas \(L_n\) viene dada por la misma recurrencia que la de Fibonacci, pero con condiciones iniciales distintas: \(L_0 = 2\) y \(L_1 = 1\). Halla su función generatriz.

4. Los números de Catalan vienen dados por la recurrencia \(C_0 = 1\), \(C_n = \sum_{k=0}^n C_k C_{n-k}\). Halla su función generatriz.

   Pista

   Si \(C(x)\) es la función generatriz, ¿qué forma tiene \(C(x)^2\)?

5. Halla la función generatriz para la fila \(n\) del triángulo de Pascal.

Combinatoria

1. Hala el número de maneras de llenar una bolsa de frutas satisfaciendo las siguientes condiciones:

   1. El número de manzanas es par
   2. El número de plátanos es múltiplo de 5
   3. Como mucho cuatro naranjas
   4. Como mucho una fresa
   Solución

   1. Número de manzanas par:

      \[ \begin{align*} M(x) &= 1 + x^2 + x^4 + x^6 + \cdots \\ &= \frac{1}{1-x^2} \end{align*} \]

   2. Número de plátanos múltiplo de 5:

      \[ \begin{align*} P(x) &= 1 + x^5 + x^{10} + x^{15} + \cdots \\ &= \frac{1}{1-x^5} \end{align*} \]

   3. Número de naranjas menor o igual a 4:

      \[ \begin{align*} N(x) &= 1 + x + x^2 + x^3 + x^4 \\ &= \frac{1-x^5}{1-x} \end{align*} \]

   4. Número de fresas menor o igual a 1:

      \[ \begin{align*} F(x) &= 1 + x \\ &= \frac{1-x^2}{1-x} \end{align*} \]

   Multiplicando todas las funciones:

   \[ M(x) P(x) N(x) F(x) = \frac{1}{\cancel{1-x^2}} \frac{1}{\cancel{1-x^5}} \frac{\cancel{1-x^5}}{1-x} \frac{\cancel{1-x^2}}{1-x} = \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots \]

   Por lo tanto, hay \(n+1\) maneras de llenar la bolsa con \(n\) piezas de fruta.

Concursos

1. (CHMMC 2010) Zacarías lanza cinco dados tetraédricos, todos con caras numeradas del 1 al 4. Calcula la probabilidad de que la suma de los valores de los dados lanzados sea divisible entre 3.

2. (Putnam 2018 B6) Sea \(S\) el conjunto de sucesiones de longitud \(2018\) cuyos términos están en el conjunto \(\{1,2,3,4,5,6,10\}\) y su suma es \(3860\). Demuestra que la cardinalidad de \(S\) cumple

   \[ |S| \leq 2^{3860} \left(\frac{2018}{2048}\right)^{2018} \]

3. (Putnam 2020 A2) Sea \(k\) un entero no negativo. Calcula

   \[ \sum_{j=0}^k 2^{k-j} {{k+j} \choose j} \]

4. (Putnam 2020 B1) Para un entero positivo \(n\), se define \(d(n)\) como la suma de los dígitos de \(n\) escrito en binario. Por ejemplo, \(d(13) = 1 + 1 + 0 + 1 = 3\). Sea

   \[ S = \sum_{k=1}^{2020} (-1)^{d(k)} k^3 \]

   Determinar \(S \mod 2020\).