8.2: Secuencias

Secuencias y formas en las que se definen

Definición\(\PageIndex{1}\): Sequence

Una secuencia es una función de los números naturales a algún conjunto predeterminado. La imagen de cualquier número natural se\(k\) puede escribir como\(S(k)\) o\(S_k\) y se llama el\(k^{th}\) término de\(S\text{.}\) La variable\(k\) se llama el índice o argumento de la secuencia.

Por ejemplo, una secuencia de enteros sería una función\(S:\mathbb{N}\to \mathbb{Z}\text{.}\)

Ejemplo \(\PageIndex{1}\): Three Sequences Defined in Different Ways

1. La secuencia\(A\) definida por\(A(k) = k^2 - k\text{,}\)\(k \geq 0\text{,}\) es una secuencia de números enteros.
2. La secuencia\(B\) definida recursivamente por\(B(0) = 2\) y\(B(k) = B(k - 1) + 3\) para\(k \geq 1\) es una secuencia de números enteros. Los términos de se\(B\) pueden calcular aplicando la fórmula de recursión o por iteración. Por ejemplo,
   \ begin {ecuación*}\ begin {split} B (3) &= B (2) + 3\\ & =( B (1) +3) +3\\ & = ((B (0) +3) +3) +3\\ & =( (2+3) +3) +3=11\ end {split}\ end {ecuación*}
   o
   \ begin {ecuación*}\ begin {array} {c} B (1) = B (0) + 3 = 2 + 3 = 5\\ B (2) = B (1) + 3 = 5 + 3 = 8 \\ B (3) = B (2) + 3 = 8 + 3 = 11\ end {array}\ end {ecuación*}
3. \(C_r\)Sea el número de cadenas de 0 y 1 de longitud\(r\) sin ceros consecutivos. Estos términos definen una secuencia\(C\) de números enteros.

Observaciones:

1. Una secuencia a menudo se llama función discreta.
2. Si bien es importante tener en cuenta que una secuencia es una función, otra forma útil de visualizar una secuencia es como una lista. Por ejemplo, la secuencia\(A\) en el ejemplo anterior podría escribirse como secuencias\((0, 0, 2, 6, 12, 20, \dots )\text{.}\) finitas pueden aparecer de la misma manera cuando son la entrada o salida de una computadora. El índice de una secuencia se puede considerar como una variable de tiempo. Imagina los términos de una secuencia parpadeando en una pantalla cada segundo. Entonces\(s_k\) sería lo que se ve en el\(k^{th}\) segundo. Es conveniente usar terminología como esta en la descripción de secuencias. Por ejemplo, los términos que preceden al\(k^{th}\) término de\(A\) serían\(A (0), A(1), . . . , A(k -1)\text{.}\) Podrían llamarse los términos anteriores.

Problema Fundamental

Dada la definición de cualquier secuencia, un problema fundamental que nos ocuparemos es idear un método para determinar cualquier término específico en un mínimo de tiempo. Generalmente, el tiempo puede equipararse con el número de operaciones necesarias. En operaciones de conteo, la aplicación de una fórmula recursiva se consideraría una operación.

1. Los términos de\(A\) en Ejemplo\(\PageIndex{1}\) son muy fáciles de calcular debido a la expresión de forma cerrada. No importa qué término decidas calcular, solo se necesitan realizar tres operaciones.
2. Cómo computar los términos de no\(B\) es tan claro. Supongamos que querías saber\(B(100)\text{.}\) Un enfoque sería aplicar la definición recursivamente:
   \ begin {ecuation*} B (100) = B (99) + 3 = (B (98) + 3) + 3 =\ cdots\ end {ecuación*}
   La ecuación de recursión para se\(B\) aplicaría 100 veces y 100 adiciones serían entonces seguir. Para calcular\(B(k)\) por este método, se necesitan\(2k\) operaciones. Un cálculo iterativo de\(B(k)\) es una mejora:\(B(1) =B(0) +3 = 2 + 3 = 5\)\(B(2) =B(1)+3= 5 + 3 = 8\: \text{etc}.\) Solo se necesitan\(k\) adiciones. Esta todavía no es una buena situación. A medida que\(k\) se hace grande, nos toma más y más tiempo calcular\(B(k)\text{.}\) La fórmula\(B(k)=B(k-1)+3\) se llama relación de recurrencia en\(B\text{.}\) El proceso de encontrar una expresión de forma cerrada para\(B(k)\text{,}\) una que no requiera más que algún número fijo de operaciones, se llama resolver la recurrencia relación.
3. La determinación de\(C_k\) es un tipo estándar de problema en combinatoria. Una solución es a través de una relación de recurrencia. De hecho, muchos problemas en combinatoria se resuelven más fácilmente buscando primero una relación de recurrencia y luego resolviéndola. La siguiente observación sugerirá la relación de recurrencia que necesitamos determinar\(C_k\text{.}\) Si\(k \geq 2\text{,}\) entonces cada cadena de 0 y 1 con longitud\(k\) y no dos 0 consecutivos es\(1s_{k-1}\) o\(01s_{k-2}\text{,}\) dónde\(s_{k-1}\) y\(s_{k-2}\) son cadenas sin dos 0 consecutivos de longitud\(k - 1\) y\(k - 2\) respectivamente. De esta observación podemos ver que\(C_k= C_{k-2}+C_{k-1}\) para\(k\geq 2\text{.}\) Los términos\(C_0= 1\) y\(C_1 = 2\) son fáciles de determinar por enumeración. Ahora, por iteración, cualquiera se\(C_k\) puede determinar fácilmente. Por ejemplo, se\(C_5 = 21\) puede computar con cinco adiciones. Una expresión de forma cerrada para\(C_k\) sería una mejora. Obsérvese que la relación de recurrencia para\(C_k\) es idéntica a la de La Secuencia de Fibonacci, Ejemplo 8.1.3. Sólo la base es diferente.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Demostrar por inducción que\(B(k) = 3k + 2,\)\(k\geq 0\text{,}\) es una expresión de forma cerrada para la secuencia\(B\) en el Ejemplo\(\PageIndex{1}\)

Contestar

Base:\(B(0)=3\cdot 0+2=2\text{,}\) como se define.

Inducción: Supongamos:\(B(k)=3k+2\) para algunos\(k\geq 0\text{.}\)

\ begin {ecuación*}\ begin {split} B (k+1) &=B (k) +3\\ &= (3k+2) +3\ quad\ textrm {por la hipótesis de inducción}\\ &= (3k+3) +2\\ &=3 (k+1) +2\ quad\ textrm {como se desee}\ end {split}\ end {ecuación*}

Ejercicio\(\PageIndex{2}\)

1. Considere la secuencia\(Q\) definida por\(Q(k) = 2k + 9\text{,}\)\(k \geq 1\text{.}\) Complete la tabla a continuación y determine una relación de recurrencia que describe\(Q\text{.}\)
   \(\begin{array}{c|c|c} k & Q(k) & Q(k)-Q(k-1) \\ \hline 2 & & \\ 3 & & \\ 4 & \text{ } & \\ 5 & & \\ 6 & & \\ 7 & & \\ \end{array}\)
2. Deje\(A(k) = k^2 - k\text{,}\)\(k \geq 0\text{.}\) Completar la tabla a continuación y determinar una relación de recurrencia para\(A\text{.}\)
   \ begin {ecuation*}\ begin {array} {c|c|c} k & A (k) & A (k) -A (k-1) & A (k) -2A (k-1) +A (k-2)\\ hline 2 & & & &\\ 3 & & &\\ 4 & & & &\\ 5 & & & &\\\ end {array}\ end {ecuación*}

Ejercicio \(\PageIndex{3}\)

Dadas\(k\) líneas (\(k\geq 0\)) en un plano tal que no hay dos líneas paralelas y no se encuentran tres líneas en un mismo punto, deja\(P(k)\) ser el número de regiones en las que las líneas dividen el plano (incluyendo las infinitas (ver Figura\(\PageIndex{1}\)). Describir cómo se\(P(k) = P(k - 1) + k\) puede derivar la relación de recurrencia. Teniendo en cuenta que\(P(0) = 1\text{,}\) determinar\(P(5)\text{.}\)

Figura\(\PageIndex{1}\): Una configuración general de tres líneas

Contestar

Imagina trazar línea\(k\) en una de las infinitas regiones por las que pasa. Esa región infinita se divide en dos regiones infinitas por línea A\(k\text{.}\) medida que la línea\(k\) se dibuja a través de cada una de las líneas\(k-1\) anteriores, se ingresa otra región que la línea\(k\) divide. Por lo tanto,\(k\) las regiones se dividen y el número de regiones se incrementa en\(k\text{.}\) A partir de esta observación obtenemos\(P(5)=16\text{.}\)

Ejercicio\(\PageIndex{4}\)

Se espera que una muestra de una sustancia radiactiva descomponga 0.15 por ciento cada hora. Si\(w_t,\)\(t \geq 0\text{,}\) es el peso de las\(t\) horas de muestra en un experimento, escriba una relación de recurrencia para\(w\text{.}\)

Ejercicio\(\PageIndex{5}\)

\(M(n)\)Sea el número de multiplicaciones necesarias para evaluar un\(n^{th}\) grado polinomio. Utilice la definición recursiva de una expresión polinómica para definir\(M\) recursivamente.

Contestar

Para\(n\) mayores de cero,\(M(n)=M(n-1)+1\text{,}\) y\(M(0)=0\text{.}\)

Ejercicio\(\PageIndex{6}\)

Let\(S\) Ser secuencia de enteros. Usando frases cortas en inglés, no símbolos, describe lo que dicen las siguientes proposiciones sobre ¿\(S\text{.}\)Son equivalentes las dos proposiciones?

1. \(\displaystyle (\forall M)_{\mathbb{N}}((\exists n)_{\mathbb{N}}(S(n)\geq M))\)
2. \(\displaystyle (\forall M)_{\mathbb{N}}((\exists N)_{\mathbb{N}}((\forall n)_{\mathbb{N}}(n \geq N \rightarrow S(n)\geq M)))\)