4.3: Generando funciones y relaciones de recurrencia

Última actualización
Guardar como PDF

Page ID: 112574

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Recordemos que una relación de recurrencia para una secuencia se$a_{n}$ expresa$a_{n}$ en términos de valores$a_{i}$ para$i < n$. Por ejemplo, la ecuación$a_{i} = 3a_{i}−1+2^{i}$ es una recurrencia de coeficiente constante lineal de primer orden.

4.3.1: Cómo son relevantes las funciones generadoras

Las manipulaciones algebraicas con funciones generadoras a veces pueden revelar las soluciones a una relación de recurrencia.

$\bullet$ Exercise $211$

Supongamos que$a_i = 3a_{i−1} + 3^i$.

a. Multiplica ambos lados por$x^i$ y suma tanto el lado izquierdo como el derecho desde$i = 1$ el infinito. En el lado izquierdo, use el hecho de que

\[\sum_{i=1}^{\infty}a_ix^i = \left( \sum_{i=0}^{\infty} x^i \right) - a_0 \]

y en el lado derecho, use el hecho de que

\[\sum_{i=1}^{\infty}a_{i-1}x^i = x \sum_{i=1}^{\infty}a_ix^{i-1} = x \sum_{j=0}^{\infty} a_j x^j = x \sum_{i=0}^{\infty} a_ix^i \]

(donde sustituimos$j$$i−1$ para ver explícitamente cómo cambiar los límites de la suma, un truco sorprendentemente útil) para reescribir la ecuación en términos de la serie de potencia$\sum^{∞}_{i=0} a_ix^i$. Resuelve la ecuación resultante para la serie de potencias$\sum^{∞}_{i=0} a_ix^i$. Puedes ahorrar mucha escritura usando una variable como y para representar la serie power.

b. utilice la parte anterior para obtener una fórmula para$a_i$ en términos de$a_0$.

c. Ahora supongamos eso$a_i = 3a_{i−1} + 2^i$. Repita los dos pasos anteriores para esta relación de recurrencia. (Hay una manera de hacer esta parte usando lo que ya sabes. Posteriormente introduciremos otra forma más de lidiar con el tipo de función generadora que aquí surge). (Pista).

$\circ$ Exercise $212$

Supongamos que depositamos$$5000$ en un certificado de ahorro que paga diez por ciento de intereses y además participamos en un programa$$1000$ para agregar al certificado al final de cada año (a partir del final del primer año en adelante) que sigue (también sujeto a intereses.) Suponiendo que hagamos el$$5000$ depósito al final del año$0$, y dejando$a_i$ ser la cantidad de dinero en la cuenta al final del año$i$, escribir una recurrencia por la cantidad de dinero que vale el certificado al final del año$n$. Resolver esta recurrencia. ¿Cuánto dinero tenemos en la cuenta (después de nuestro depósito de fin de año) al final de diez años? ¿Al final de los$20$ años?

4.3.2: Números de Fibonacci

La secuencia de problemas que sigue (culminando en el Problema 222) describe una serie de hipótesis que podríamos hacer sobre una población ficticia de conejos. Usamos el ejemplo de una población de conejos por razones históricas; nuestro objetivo es una secuencia clásica de números llamada números de Fibonacci. Cuando Fibonacci ¹ los presentó, lo hizo con una población ficticia de conejos.

4.3.3: Relaciones de recurrencia lineal de segundo orden

$\bullet$ Exercise $213$

Supongamos que comenzamos (a fin de mes$0$) con$10$ parejas de conejos bebés, y que después de que los conejos crías maduran por un mes comiencen a reproducirse, con cada pareja produciendo dos nuevas parejas al final de cada mes posterior. Supongamos además que a lo largo del tiempo observamos a los conejos, ninguno muere. $a_n$Sea el número de conejos que tenemos a fin de mes$n$. $a_n = a_{n−1}+2a_{n−2}$Demuéstralo. Este es un ejemplo de una recurrencia lineal de segundo orden con coeficientes constantes. Usando un método similar al del Problema 211, mostrar que

\[\sum_{i=0}^{\infty} a_i x^i = \dfrac{10}{1-x-2x^2} \]

Esto nos da la función generadora para la secuencia$a_i$ dando a la población en mes$i$; en breve veremos un método para convertirlo en una solución a la recurrencia.

$\bullet$ Exercise $214$

En el problema original de Fibonacci, cada par de conejos maduros produce un nuevo par al final de cada mes, pero por lo demás la situación es la misma que en el Problema 213. Suponiendo que empezamos con un par de conejos bebés (al final del mes$0$), encontramos la función generadora para el número de parejas de conejos que tenemos al final de los$n$ meses. (Pista).

$\rightarrow$ Exercise $215$

Encontrar la función generadora para las soluciones a la recurrencia$a_i = 5a_{i−1} − 6a_{i−2} + 2^i$.

Las relaciones de recurrencia que hemos visto en esta sección se llaman segundo orden porque especifican ai en términos de$a_{i−1}$ y$a_{i−2}$, se llaman lineales porque$a_{i−1}$ y$a_{i−2}$ cada una aparece a la primera potencia, y se les llama coeficiente constante recurrencias porque los coeficientes delante de$a_{i−1}$ y$a_{i−2}$ son constantes.

4.3.4: Fracciones Parciales

Todas las funciones generadoras que encontraste en la sección anterior se pueden expresar en términos del recíproco de un polinomio cuadrático. Sin embargo, sin una representación de series de potencia, la función generadora no nos dice cuál es la secuencia. Resulta que siempre que se puede factorizar un polinomio en factores lineales (y sobre los números complejos tal factorización siempre existe) se puede utilizar esa factorización para expresar lo recíproco en términos de series de poder.

$\bullet$ Exercise $216$

Expresar$\dfrac{1}{x−3} + \dfrac{2}{x−2}$ como una sola fracción.

$\circ$ Exercise $217$

En Problema 216 se ve que cuando agregamos múltiplos numéricos de los recíprocos de polinomios de primer grado conseguimos una fracción en la que el denominador es un polinomio cuadrático. Esto siempre sucederá a menos que los dos denominadores sean múltiplos el uno del otro, porque su múltiplo menos común será simplemente su producto, un polinomio cuadrático. Esto nos lleva a preguntarnos si una fracción cuyo denominador es un polinomio cuadrático siempre puede expresarse como una suma de fracciones cuyos denominadores son polinomios de primer grado. Encuentra números$c$ y$d$ para que

\[\dfrac{5x + 1}{(x − 3)(x + 5)} = \dfrac{c}{x − 3} + \dfrac{d}{x + 5} .\](Pista).

$\bullet$ Exercise $218$

En el Problema 217 es posible que simplemente hayas adivinado valores de$c$ y$d$, o puedes haber resuelto un sistema de ecuaciones en las dos incógnitas$c$ y$d$. Dadas las constantes$a$$b$,$r_1$,, y$r_2$ (con$r_1 \neq r_2$), anotar un sistema de ecuaciones que podemos resolver$d$ para$c$ y escribir

\[\dfrac{ax + b}{(x − r_1)(x − r_2)} = \dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\](Pista).

Anotar las ecuaciones en el Problema 218 y resolverlas se llama método de fracciones parciales. Este método te permitirá encontrar expansiones de series de potencia para generar funciones del tipo que encontraste en Problemas 213 a Problema 215. No obstante, hay que ser capaz de factorizar los polinomios cuadráticos que están en los denominadores de sus funciones generadoras.

$\bullet$ Exercise $219$

Utiliza el método de fracciones parciales para convertir la función generadora de Problema 213 en la forma\[\dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\] Utiliza esto para encontrar una fórmula para$a_n$.

$\bullet$ Exercise $220$

Use la fórmula cuadrática para encontrar las soluciones y use esa información para factorizar$x^2 + x − 1$.$x^2 +x−1 = 0$

$\bullet$ Exercise $221$

Usa los factores que encontraste en Problema 220 para escribir\[\dfrac{1}{x^2 + x − 1}\] en el formulario\[\dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\] (Pista).

$\bullet$ Exercise $222$

a. usa la descomposición parcial de fracciones que encontraste en Problema 220 para escribir la función generadora que encontraste en Problema 214 en la forma\[\sum^{∞}_{n=0} a_n x^i\] y usa esta para dar una fórmula explícita para$a_n$. (Pista).

b. Cuando tenemos$a_0 = 1$ y$a_1 = 1$, es decir, cuando empezamos con un par de conejos bebés, los números$a_n$ se llaman Números Fibonacci. Utilice ya sea la recurrencia o su fórmula final para encontrar a$a_2$ través de$a_8$. ¿Te sorprende que tu fórmula general produzca números enteros, o para el caso produce números racionales? ¿Por qué la ecuación de recurrencia te dice que los números de Fibonacci son todos enteros?

c. Explique por qué existe un número real$b$ tal que, para valores grandes de$n$, el valor del número de$n^{\text{th}}$ Fibonacci sea casi exactamente (pero no del todo) algunos tiempos constantes$b^n$. (Encontrar$b$ y la constante.)

d. Encontrar una explicación algebraica (no usando la ecuación de recurrencia) de lo que sucede para hacer desaparecer las raíces cuadradas de cinco. (Pista).

e. Como desafío (que el autor aún no ha hecho), vea si puede encontrar una manera de mostrar algebraicamente (no usando la relación de recurrencia, sino la fórmula que obtiene al eliminar las raíces cuadradas de cinco) que la fórmula para los números de Fibonacci produce números enteros.

Ejercicio$223$

Resolver la recurrencia$a_n = 4a_{n−1} − 4a_{n−2}$.

4.3.5: Números Catalanes

$\rightarrow$ Exercise $224$

a. Utilizando ya sea caminos de celosía o caminos de celosía diagonales, explicar por qué el Número Catalán$c_n$ satisface la recurrencia\[C_n = \sum^{n−1}_{i=1} C_{i−1}C_{n−i}.\] (Pista).

b. Demostrar que si usamos$y$ para representar la serie de potencia$\sum^{∞}_{n=0} c_n x^n$, entonces podemos encontrar$y$ resolviendo una ecuación cuadrática. Encuentra$y$. (Pista).

c. El teorema de Taylor a partir del cálculo nos dice que el teorema binomial extendido se\[ (1 + x)^r = \sum^{∞}_{i=0} \binom{r}{i}x^i \] mantiene para cualquier número número real$r$, donde$ \binom{r}{i} $ se define para ser\[\dfrac{r^{\underline{i}}}{i!} = \dfrac{r(r − 1)···(r − i + 1)}{i!}.\] Use esto y su solución para$y$ (tenga en cuenta que de los dos valores posibles para$y$ que se obtiene de la cuadrática fórmula, sólo uno da una serie de potencia real) para obtener una fórmula para los números catalanes. (Pista).

Notas

1. Al parecer a Leanardo de Pisa se le dio el nombre de Fibonacci póstumamente. Se trata de un acortamiento de “hijo de Bonacci” en italiano.