2.S: Secuencias (Resumen)

Template:MathJaxLevin

¡Investiga!

Cada día tu suministro de granos de café espresso cubiertos de chocolate mágico se duplica (cada uno se divide por la mitad), pero luego comes 5 de ellos. Tienes 10 al inicio del día 0.

1. Escribe los primeros términos de la secuencia. Entonces da una definición recursiva para la secuencia y explica cómo sabes que es correcta.
2. Demuestre, usando inducción, que el último dígito del número de frijoles que tiene en el día$n$ th es siempre un 5 para todos$n \ge 1\text{.}$
3. Encuentre una fórmula cerrada para el término$n$ th de la secuencia y demuestre que es correcta por inducción.

En este capítulo exploramos secuencias e inducción matemática. Al principio estos podrían no parecer del todo relacionados, pero hay un vínculo: el razonamiento recursivo. Cuando tenemos muchos casos (quizás infinitamente muchos), muchas veces es más fácil describir un caso particular diciendo cómo se relaciona con otros casos, en lugar de describirlo absolutamente. Para las secuencias, podemos describir el término$n$ th en la secuencia diciendo cómo se relaciona con el término anterior. Al mostrar una declaración que involucra a la variable$n$ es verdadera para todos los valores de$n\text{,}$ podemos describir por qué el caso para$n = k$ es verdadero sobre la base de por qué el caso para$n = k-1$ es verdadero.

Si bien pensar en los problemas recursivamente suele ser más fácil que pensar en ellos absolutamente (al menos después de acostumbrarse a pensar de esta manera), nuestro objetivo final es ir más allá de esta descripción recursiva. Para las secuencias, queremos encontrar fórmulas cerradas para el término$n$ th de la secuencia. Para las pruebas, queremos saber que la afirmación es realmente cierta para un particular$n$ (no sólo bajo el supuesto de que la declaración es verdadera para el valor anterior de$n$). En este capítulo vimos algunos métodos para pasar de descripciones recursivas a descripciones absolutas.

• Si los términos de una secuencia aumentan por una diferencia constante o relación constante (estas son ambas descripciones recursivas), entonces las secuencias son aritméticas o geométricas, respectivamente, y tenemos fórmulas cerradas para cada una de estas basadas en los términos iniciales y la diferencia o relación común.
• Si los términos de una secuencia aumentan a una velocidad polinómica (es decir, si las diferencias entre términos forman una secuencia con una fórmula polinómica cerrada), entonces la secuencia viene dada por una fórmula polinómica cerrada (de grado uno más que la secuencia de diferencias).
• Si los términos de una secuencia aumentan a una velocidad exponencial, entonces esperamos que la fórmula cerrada para la secuencia sea exponencial. Estas secuencias suelen tener fórmulas recursivas relativamente agradables, y la técnica de raíz característica nos permite encontrar la fórmula cerrada para estas secuencias.
• Si queremos probar que una afirmación es verdadera para todos los valores de$n$ (mayor que algún primer valor pequeño), y podemos describir por qué la afirmación es verdadera para$n = k$ implica que la afirmación es verdadera para$n = k+1\text{,}$ entonces el principio de inducción matemática nos da que la afirmación es true para todos los valores de$n$ (mayor que el caso base).

A lo largo del capítulo tratamos de entender por qué estos hechos enumerados anteriormente son ciertos. En parte, eso es lo que las pruebas, por inducción o no, intentan lograr: explican por qué las verdades matemáticas son en realidad verdades. A medida que desarrollamos nuestra capacidad de razonar sobre las matemáticas, es una buena idea asegurarnos de que los métodos de nuestro razonamiento sean sólidos. La rama de las matemáticas que se ocupa de decidir si el razonamiento es bueno o no es la lógica matemática, el tema del siguiente capítulo.

Revisión del Capítulo

1

Encuentra$3 + 7 + 11+ \cdots + 427\text{.}$

Contestar

$\frac{430\cdot 107}{2} = 23005\text{.}$

2

Considera la secuencia$2, 6, 10, 14, \ldots, 4n + 6\text{.}$

1. ¿Cuántos términos hay en la secuencia?
2. ¿Cuál es el penúltimo trimestre?
3. Encuentra la suma de todos los términos en la secuencia.

Contestar

1. $n+2$ terms.
2. $4n+2\text{.}$
3. $\frac{(4n+8)(n+2)}{2}\text{.}$

3

Considere la secuencia dada por$a_n = 2\cdot 5^{n-1}\text{.}$

1. Encuentra los primeros 4 términos de la secuencia. ¿Qué tipo de secuencia es esta?
2. Encuentra la suma de los primeros 25 términos. Es decir, computar$\d\sum_{k=1}^{25}a_k\text{.}$

Contestar

1. $2, 10, 50, 250, \ldots$ The sequence is geometric.
2. $\frac{2 - 2\cdot 5^{25}}{-4}\text{.}$

4

Considere la secuencia$5, 11, 19, 29, 41, 55,\ldots\text{.}$ Asumir$a_1 = 5\text{.}$

1. Encuentra una fórmula cerrada para$a_n\text{,}$ el término$n$ th de la secuencia, escribiendo cada término como una suma de una secuencia. Pista: primero encuentra$a_0\text{,}$ pero ignórala al colapsar la suma.
2. Vuelva a encontrar una fórmula cerrada, esta vez usando el ajuste polinómico o la técnica de raíz característica (lo que sea apropiado). Muestre su trabajo.
3. Encuentra una fórmula cerrada una vez más, esta vez reconociendo la secuencia como una modificación a alguna secuencia o secuencias bien conocidas. Explique.

5

Utilice el ajuste polinomial para encontrar una fórmula cerrada para la secuencia$(a_n)_{n\ge 1}\text{:}$

\ begin {ecuación*} 4, 11, 20, 31, 44,\ ldots. \ end {ecuación*}

Contestar

$a_n = n^2 + 4n - 1\text{.}$

6

Supongamos que la fórmula cerrada para una secuencia particular es un polinomio de grado 3. ¿Qué puedes decir sobre la fórmula cerrada para:

1. La secuencia de sumas parciales.
2. La secuencia de segundas diferencias.

Contestar

1. La secuencia de sumas parciales será un polinomio grado 4 (su secuencia de diferencias será la secuencia original).
2. La secuencia de segundas diferencias será un polinomio de grado 1, una secuencia aritmética.

7

Considere la secuencia dada recursivamente por$a_1 = 4\text{,}$$a_2 = 6$ y$a_n = a_{n-1} + a_{n-2}\text{.}$

1. Escribe los primeros 6 términos de la secuencia.
2. ¿Podría la fórmula cerrada para$a_n$ ser un polinomio? Explique.

Contestar

1. $4, 6, 10, 16, 26, 42, \ldots\text{.}$
2. No, tomar las diferencias devuelve la secuencia original, por lo que las diferencias nunca serán constantes.

8

La secuencia$-1, 0, 2, 5, 9, 14\ldots$ tiene fórmula cerrada$a_n = \dfrac{(n+1)(n-2)}{2}\text{.}$ Usa este hecho para encontrar una fórmula cerrada para la secuencia$4, 10, 18, 28, 40, \ldots\text{.}$

Contestar

$b_n = (n+3)n\text{.}$

9

El en canción Los doce días de Navidad, mi verdadero amor me dio primero 1 regalo, luego 2 regalos y 1 regalo, luego 3 regalos, 2 regalos y 1 regalo, y así sucesivamente. ¿Cuántos regalos me dio mi verdadero amor todos juntos durante los doce días?

10

Considerar la relación de recurrencia$a_n = 3a_{n-1} + 10 a_{n-2}$ con los dos primeros términos$a_0 = 1$ y$a_1 = 2\text{.}$

1. Escribe los primeros 5 términos de la secuencia definida por esta relación de recurrencia.
2. Resolver la relación de recurrencia. Es decir, encontrar una fórmula cerrada para$a_n\text{.}$

Contestar

1. $1, 2, 16,68, 364, \ldots\text{.}$
2. $a_n = \frac{3}{7}(-2)^n + \frac{4}{7}5^n\text{.}$

11

Considerar la relación de recurrencia$a_n = 2a_{n-1} + 8a_{n-2}\text{,}$ con términos iniciales$a_0 = 1$ y$a_1= 3\text{.}$

1. Encuentra los siguientes dos términos de la secuencia ($a_2$y$a_3$).
2. Resolver la relación de recurrencia. Es decir, encontrar una fórmula cerrada para el término$n$ th de la secuencia.

Contestar

1. $a_2 = 14\text{.}$ $a_3 = 52\text{.}$
2. $a_n = \frac{1}{6}(-2)^n + \frac{5}{6}4^n\text{.}$

12

Tus conejitos mágicos de chocolate se reproducen como conejos: cada conejito grande produce 2 mini conejitos nuevos cada día, y cada día cada mini conejito nacido el día anterior se convierte en un conejito grande. Asume que comienzas con 2 mini conejitos y ningún conejito muere (o se come) nunca.

1. Escribe los primeros términos de la secuencia.
2. Dar una definición recursiva de la secuencia y explicar por qué es correcta.
3. Encuentra una fórmula cerrada para el término$n$ th de la secuencia.

Contestar

1. El primer día, tus 2 mini conejitos se convierten en 2 conejitos grandes. El día 2, tus dos conejitos grandes producen 4 mini conejitos. En el día 3, tienes 4 mini conejitos (producidos por tus 2 conejitos grandes) más 6 conejitos grandes (tus 2 originales más los 4 conejitos recién madurados). En el día 4, tendrás$12$ mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is $2, 2, 6, 10, 22, 42\ldots$ starting with $a_0 = 2$ and $a_1 = 2\text{.}$
2. $a_n = a_{n-1} + 2a_{n-2}\text{.}$ This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).
3. Usando la técnica de raíz característica, encontramos$a_n = a2^n + b(-1)^n\text{,}$ and we can find $a$ and $b$ to give $a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}$

13

Demostrar las siguientes afirmaciones por inducción matemática:

1. $n! \lt n^n$para$n \ge 2$
2. $\d\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} +\frac{1}{3\cdot 4}+\cdots + \frac{1}{n\cdot(n+1)} = \d\frac{n}{n+1}$para todos$n \in \Z^+\text{.}$
3. $4^n - 1$es un múltiplo de 3 para todos$n \in \N\text{.}$
4. La mayor cantidad de franqueo que no puedes hacer exactamente usando sellos de 4 y 9 centavos es de 23 centavos.
5. Cada número par al cuadrado es divisible por 4.

Contestar

1. Pista:$(n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}$
2. Pista: Esto debería ser similar a las otras pruebas de suma. El último bit se reduce a sumar fracciones.
3. Pista: Escribir$4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}$
4. Pista: un sello de 9 centavos es 1 más de dos sellos de 4 centavos, y siete sellos de 4 centavos es 1 más de tres sellos de 9 centavos.
5. Cuidado de usar realmente la inducción aquí. El caso base:$2^2 = 4\text{.}$ The inductive case: assume $(2n)^2$ is divisible by 4 and consider $(2n+2)^2 = (2n)^2 + 4n + 4\text{.}$ This is divisible by 4 because $4n +4$ clearly is, and by our inductive hypothesis, so is $(2n)^2\text{.}$

14

Demostrar$1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ retenciones para todos$n \ge 1\text{,}$ por inducción matemática.

Hin

Esta es una prueba de inducción directa. Tenga en cuenta que necesitará simplificar$\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3$ and get $\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}$

15

Supongamos$a_0 = 1\text{,}$$a_1 = 1$ y$a_n = 3a_{n-1} - 2a_{n-1}\text{.}$ Probar, usando una fuerte inducción, que$a_n = 1$ para todos$n\text{.}$

Pista

Hay dos casos base$P(0)$ and $P(1)\text{.}$ Then, for the inductive case, assume $P(k)$ is true for all $k \lt n\text{.}$ This allows you to assume $a_{n-1} = 1$ and $a_{n-2} = 1\text{.}$ Apply the recurrence relation.

16

Demuestre, usando una fuerte inducción, que cada entero positivo puede escribirse como la suma de distintas potencias de 2. Por ejemplo,$13 = 1 + 4 + 8 = 2^0 + 2^2 + 2^3\text{.}$

Contestar

Tenga en cuenta que$1 = 2^0\text{;}$ this is your base case. Now suppose $k$ can be written as the sum of distinct powers of 2 for all $1\le k \le n\text{.}$ We can then write $n$ as the sum of distinct powers of 2 as follows: subtract the largest power of 2 less than $n$ from $n\text{.}$ That is, write $n = 2^j + k$ for the largest possible $j\text{.}$ But $k$ is now less than $n\text{,}$ and also less than $2^j\text{,}$ so write $k$ as the sum of distinct powers of 2 (we can do so by the inductive hypothesis). Thus $n$ can be written as the sum of distinct powers of 2 for all $n \ge 1\text{.}$

17

Demostrar usando inducción que cada conjunto que contiene$n$ elementos tiene$2^n$ diferentes subconjuntos para cualquier$n \ge 1\text{.}$

Contestar

Let$P(n)$ be the statement, “every set containing $n$ elements has $2^n$ different subsets.” We will show $P(n)$ is true for all $n \ge 1\text{.}$ Base case: Any set with 1 element $\{a\}$ has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is $2= 2^1\text{.}$ Thus $P(1)$ is true. Inductive case: Suppose $P(k)$ is true for some arbitrary $k \ge 1\text{.}$ Thus every set containing exactly $k$ elements has $2^k$ different subsets. Now consider a set containing $k+1$ elements: $A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}$ Any subset of $A$ must either contain $a_{k+1}$ or not. In other words, a subset of $A$ is just a subset of $\{a_1, a_2,\ldots, a_k\}$ with or without $a_{k+1}\text{.}$ Thus there are $2^k$ subsets of $A$ which contain $a_{k+1}$ and another $2^{k+1}$ subsets of $A$ which do not contain $a^{k+1}\text{.}$ This gives a total of $2^k + 2^k = 2\cdot 2^k = 2^{k+1}$ subsets of $A\text{.}$ But our choice of $A$ was arbitrary, so this works for any subset containing $k+1$ elements, so $P(k+1)$ is true. Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$