2.2: Relaciones de recurrencia

Última actualización
Guardar como PDF

Page ID: 112681

$ \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}}$

Ejercicio$87$

¿Cómo se relaciona el número de subconjuntos de un conjunto de elementos n con el número de subconjuntos de un conjunto de elementos ($n − 1$)? Demuestra que tienes razón. (Pista).

Ejercicio$88$

Explique por qué es que el número de bijecciones de un conjunto de$n$ elementos$n$ -elemento a un conjunto de elementos es igual a$n$ veces el número de bijecciones de un subconjunto de elementos ($n − 1$) a un conjunto de elementos ($n − 1$). ¿Qué tiene que ver esto con el Problema 27?

Podemos resumir estas observaciones de la siguiente manera. Si$s_{n}$ representa el número de subconjuntos de un conjunto$n$ -element, entonces

\[s_{n} = 2s_{n-1} \label{2.2.1}\]

y si$b_{n}$ representa el número de bijecciones de un conjunto de elementos n a un conjunto$n$ de elementos, entonces

\[b_{n} = nb_{n-1} \label{2.2.2}\]

Ecuaciones$\ref{2.2.1}$ y$\ref{2.2.2}$ son ejemplos de ecuaciones de recurrencia o relaciones de recurrencia. Una relación de recurrencia o simplemente una recurrencia es una ecuación que expresa el$n^{\text{th}}$ término de una secuencia$a_{n}$ en términos de valores de$a_{i}$ for$i < n$. Así las ecuaciones$\ref{2.2.1}$ y$\ref{2.2.2}$ son ejemplos de recurrencias.

2.2.1: Ejemplos de relaciones de recurrencia

Otros ejemplos de recurrencias son

\[a_{n} = a_{n}−1 + 7, \label{2.2.3}\]

\[a_{n} = 3a_{n}−1 + 2n, \label{2.2.4}\]

\[a_{n} = a_{n}−1 + 3a_{n}−2, \text{ and} \label{2.2.5}\]

\[a_{n} = a_{1}a_{n−1} + a2a_{n−2} + \dotsi + a_{n−1}a_{1}. \label{2.2.6}\]

Una solución a una relación de recurrencia es una secuencia que satisface la relación de recurrencia. Así, una solución a la recurrencia$\ref{2.2.1}$ es la secuencia dada por$s_{n} = 2^{n}$. Tenga en cuenta que$s_{n} = 17 \cdot 2^{n}$ y también$s_{n} = −13 \cdot 2^{n}$ son soluciones a la Recurrencia$\ref{2.2.1}$. Lo que esto demuestra es que una recurrencia puede tener infinitamente muchas soluciones. En un problema dado, generalmente hay una solución que nos interesa. Por ejemplo, si nos interesa el número de subconjuntos de un conjunto, entonces la solución a Recurrencia$\ref{2.2.1}$ que nos importa es$s_{n} = 2^{n}$. Observe que esta es la única solución que hemos mencionado que satisface$s_{0} = 1$.

Ejercicio$89$

Demostrar que solo hay una solución a la Recurrencia$\ref{2.2.1}$ que satisfaga$s_{0} = 1$.

Ejercicio$90$

Una relación de recurrencia de primer orden es aquella que expresa una en términos de$a_{n−1}$ y otras funciones de$n$, pero que no incluye ninguno de los términos$a_{i}$ para$i < n − 1$ en la ecuación.

¿Cuáles de las recurrencias$\ref{2.2.1}$ a través$\ref{2.2.6}$ son recidivas de primer orden?
Mostrar que hay una y solo una secuencia$a_{n}$ que se define para cada entero no negativo$n$, satisface una recurrencia de primer orden dada y satisface$a_{0} = a$ alguna constante fija$a$. (Pista).

Figura$\PageIndex{1}$: Las Torres de Hanoi Puzzle (Copyright; autor vía fuente)

$\rightarrow$ Exercise $91$

El rompecabezas “Torres de Hanoi” tiene tres varillas que se elevan desde una base rectangular con$n$ anillos de diferentes tamaños apilados en orden decreciente de tamaño en una varilla. Un movimiento legal consiste en mover un anillo de una varilla a otra para que no aterrice sobre un anillo más pequeño. Si$m_{n}$ es el número de movimientos requeridos para mover todos los anillos de la varilla inicial a otra varilla que elijas, dale una recurrencia para$m_{n}$. (Pista).

$\rightarrow$ Exercise $92$

Dibujamos círculos que$n$ se cruzan mutuamente en el plano para que cada uno se cruce uno al otro exactamente dos veces y no tres se crucen en un mismo punto. (Como ejemplos, piense en diagramas de Venn con dos o tres conjuntos que se intersectan mutuamente). Encuentra una recurrencia para el número$r_{n}$ de regiones en las que el plano está dividido por$n$ círculos. (Un círculo divide el plano en dos regiones, la interior y la exterior). Encuentra el número de regiones con$n$ círculos. ¿Para qué valores de$n$ se puede dibujar un diagrama de Venn que muestre todas las intersecciones posibles de$n$ conjuntos usando círculos para representar cada uno de los conjuntos? (Pista).

2.2.2: Serie Aritmética (opcional)

Ejercicio$93$

Un niño guarda dos dólares de su asignación cada semana. Si empieza con veinte dólares, dale una recurrencia por la cantidad$a_n$ de dinero que tiene después de$n$ semanas y averigua cuánto dinero tiene al final de las$n$ semanas.

Ejercicio$94$

Una secuencia que satisface una recurrencia de la forma$a_{n} = a_{n−1} + c$ se llama progresión aritmética. Encuentra una fórmula en términos del valor inicial$a_{0}$ y la diferencia común$c$ para el término an en una progresión aritmética y demuestra que tienes razón.

Ejercicio$95$

Una persona que está ganando$$50,000$ por año recibe un aumento de$$3000$ un año por$n$ años seguidos. Encuentra una recurrencia por la cantidad$a_n$ de dinero que la persona gana a lo largo de$n+1$ los años. ¿Cuál es la cantidad total de dinero que gana la persona a lo largo de un periodo de$n + 1$ años? (En$n + 1$ años, hay$n$ aumentos.)

Ejercicio$96$

Una serie aritmética es una secuencia$s_{n}$ igual a la suma de los términos$a_{0}$ a través$a_n$ de una progresión aritmética. Encontrar una recurrencia para la suma$s_{n}$ de una progresión aritmética con valor inicial$a_{0}$ y diferencia común$c$ (usando el lenguaje del Problema 94). Encuentra una fórmula para término general$s_n$ de series$a_n$ aritméticas.

2.2.3: Recurrencias Lineales de Primer Orden

Las recurrencias como las de Ecuaciones$\ref{2.2.1}$ a través se$\ref{2.2.5}$ denominan recurrencias lineales, al igual que las recurrencias de los Problemas 91 y 92. Una recurrencia lineal es aquella en la que una se expresa como una suma de funciones de valores de$n$ tiempos de (algunos de los términos)$a_{i}$ para$i < n$ más (quizás) otra función (llamada la función de conducción) de$n$. Una ecuación lineal se llama homogénea si la función de conducción es cero (o, en otras palabras, no hay función de conducción). Se denomina recurrencia lineal de coeficiente constante si las funciones que se multiplican por los$a_i$ términos son todas constantes (pero la función de conducción no necesita ser constante).

Ejercicio$97$

Clasificar las recurrencias en Ecuaciones$\ref{2.2.1}$ a través$\ref{2.2.5}$ y Problemas 91 y 92 según si son o no coeficientes constantes, y si son o no homogéneos.

$\bullet$ Exercise $98$

Como se puede ver en el Problema 97 algunas secuencias interesantes satisfacen las recurrencias lineales de primer orden, entre ellas muchas que tienen coeficientes constantes, tienen un plazo de conducción constante, o son homogéneas. Encuentra una fórmula en términos de$b, d, a_{0}$ y$n$ para el término general una de una secuencia que satisfaga un coeficiente constante de recurrencia lineal de primer orden$a_{n} = ba_{n−1} + d$ y demuestre que estás en lo correcto. Si tu fórmula implica una suma, intenta reemplazar la suma por una expresión más compacta. (Pista).

2.2.4: Serie Geométrica

Una secuencia que satisface una recurrencia de la forma$a_{n} = ba_{n−1}$ se denomina progresión geométrica. Así, la secuencia que satisface la Ecuación$\ref{2.2.1}$, la recurrencia para el número de subconjuntos de un conjunto$n$ -elemento, es un ejemplo de una progresión geométrica. De tu solución al Problema 98, una progresión geométrica tiene la forma$a_{n} = a_{0}b^{n}$. En tu solución al Problema 98 es posible que hayas tenido que lidiar con la suma de una progresión geométrica en una notación ligeramente diferente, a saber$\sum^{n-1}_{i=0} db^{i}$. Una suma de esta forma se llama serie geométrica (finita).

Ejercicio$99$

Haz este problema solo si tu respuesta final (hasta ahora) al Problema 98 contenía la suma$\sum^{n-1}_{i=0} db^{i}$.

Ampliar$(1 − x)(1 + x)$. Ampliar$(1 − x)(1 + x + x^{2})$. Ampliar$(1 − x)(1 + x + x^{2} + x^{3})$.
¿Qué esperas$(1 − b)\sum^{n-1}_{i=0} db^{i}$ ser? ¿Qué fórmula te da esto?$\sum^{n-1}_{i=0} db^{i}$ Demuestra que tienes razón.

En Problema 98 y quizás 99 probaste un teorema importante. Si bien el teorema no tiene nombre, la fórmula que afirma se llama la suma de una serie geométrica finita.

Teorema$\PageIndex{1}$

Si$ b \neq 1$ y$a_{n} = ba_{n−1} + d$, entonces$a_{n} = a_{0}b^{n} + d\dfrac{1-b^{n}}{1-b}$, entonces$a_{n} = a_{0} + nd$.

Corolario$\PageIndex{1}$

Si$ b \neq 1$, entonces$\sum^{n-1}_{i=0}b^{i} = \dfrac{1-b^{n}}{1-b}$. Si$b = 1$,$\sum^{n-1}_{i=0}b^{i} = n$.