5.E: Temas adicionales (Ejercicios)

Template:MathJaxLevin

5.1: Generando funciones

1

Encuentra la función generadora para cada una de las siguientes secuencias relacionándolas de nuevo con una secuencia con función generadora conocida.

1. \(4,4,4,4,4,\ldots\text{.}\)
2. \(2, 4, 6, 8, 10, \ldots\text{.}\)
3. \(0,0,0,2,4,6,8,10,\ldots\text{.}\)
4. \(1, 5, 25, 125, \ldots\text{.}\)
5. \(1, -3, 9, -27, 81, \ldots\text{.}\)
6. \(1, 0, 5, 0, 25, 0, 125, 0, \ldots\text{.}\)
7. \(0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 4, 0, 0, 5, \ldots\text{.}\)

Contestar

1. \(\dfrac{4}{1-x}\text{.}\)
2. \(\dfrac{2}{(1-x)^2}\text{.}\)
3. \(\dfrac{2x^3}{(1-x}^2\text{.}\)
4. \(\dfrac{1}{1-5x}\text{.}\)
5. \(\dfrac{1}{1+3x}\text{.}\)
6. \(\dfrac{1}{1-5x^2}\text{.}\)
7. \(\dfrac{x}{(1-x^3)^2}\text{.}\)

2

Encuentra la secuencia generada por las siguientes funciones generadoras:

1. \(\dfrac{4x}{1-x}\text{.}\)
2. \(\dfrac{1}{1-4x}\text{.}\)
3. \(\dfrac{x}{1+x}\text{.}\)
4. \(\dfrac{3x}{(1+x)^2}\text{.}\)
5. \(\dfrac{1+x+x^2}{(1-x)^2}\)(Pista: multiplicación).

Contestar

1. \(0, 4, 4, 4, 4, 4, \ldots\text{.}\)
2. \(1, 4, 16, 64, 256, \ldots\text{.}\)
3. \(0, 1, -1, 1, -1, 1, -1, \ldots\text{.}\)
4. \(0, 3, -6, 9, -12, 15, -18, \ldots\text{.}\)
5. \(1, 3, 6, 9, 12, 15, \ldots\text{.}\)

3

Muestra cómo puedes obtener la función generadora para los números triangulares de tres maneras diferentes:

1. Tomar dos derivadas de la función generadora para\(1,1,1,1,1, \ldots\)
2. Utilice la diferenciación.
3. Multiplicar dos funciones generadoras conocidas.

Contestar

1. La segunda derivada de\(\dfrac{1}{1-x}\) is \(\dfrac{2}{(1-x)^3}\) which expands to \(2 + 6x + 12x^2 + 20x^3 + 30x^4 + \cdots\text{.}\) Dividing by 2 gives the generating function for the triangular numbers.
2. Compute\(A - xA\) and you get \(1 + 2x + 3x^2 + 4x^3 + \cdots\) which can be written as \(\dfrac{1}{(1-x)^2}\text{.}\) Solving for \(A\) gives the correct generating function.
3. Los números triangulares son la suma de los primeros\(n\) numbers \(1,2,3,4, \ldots\text{.}\) To get the sequence of partial sums, we multiply by \(\frac{1}{1-x}\text{.}\) So this gives the correct generating function again.

4

Utilice la diferenciación para encontrar la función generadora para\(4, 5, 7, 10, 14, 19, 25, \ldots\text{.}\)

Contestar

Llamar a la función generadora\(A\text{.}\) Compute \(A - xA = 4 + x + 2x^2 + 3x^3 + 4x^4 + \cdots\text{.}\) Thus \(A - xA = 4 + \dfrac{x}{(1-x)^2}\text{.}\) Solving for \(A\) gives \(\d\frac{4}{1-x} + \frac{x}{(1-x)^3}\text{.}\)

5

Encontrar una función generadora para la secuencia con relación de recurrencia\(a_n = 3a_{n-1} - a_{n-2}\) con términos iniciales\(a_0 = 1\) y\(a_1 = 5\text{.}\)

Contestar

\(\dfrac{1+2x}{1-3x + x^2}\text{.}\)

6

Utilice la relación de recurrencia para los números de Fibonacci para encontrar la función generadora para la secuencia de Fibonacci.

Contestar

Compute\(A - xA - x^2A\) and the solve for \(A\text{.}\) The generating function will be \(\dfrac{x}{1-x-x^2}\text{.}\)

7

Utilice la multiplicación para encontrar la función generadora para la secuencia de sumas parciales de números de Fibonacci,\(S_0, S_1, S_2, \ldots\) donde\(S_0 = F_0\text{,}\)\(S_1 = F_0 + F_1\text{,}\)\(S_2 = F_0 + F_1 + F_2\text{,}\)\(S_3 = F_0 + F_1 + F_2 + F_3\) y así sucesivamente.

Contestar

\(\dfrac{x}{(1-x)(1-x-x^2)}\text{.}\)

8

Encuentra la función generadora para la secuencia con fórmula cerrada\(a_n = 2(5^n) + 7(-3)^n\text{.}\)

Contestar

\(\dfrac{2}{1-5x} + \dfrac{7}{1+3x}\text{.}\)

9

Encuentra una fórmula cerrada para el término\(n\) th de la secuencia con función generadora\(\dfrac{3x}{1-4x} + \dfrac{1}{1-x}\text{.}\)

Contestar

\(a_n = 3\cdot 4^{n-1} + 1\text{.}\)

10

Buscar\(a_7\) para la secuencia con función de generación\(\dfrac{2}{(1-x)^2}\cdot\dfrac{x}{1-x-x^2}\text{.}\)

Pista

deberías “multiplicar” las dos secuencias.

Contestar

158

11

Explicar cómo sabemos que\(\dfrac{1}{(1-x)^2}\) es la función generadora para\(1, 2, 3, 4, \ldots\text{.}\)

Contestar

Empezando con\(\frac{1}{1-x} = 1 + x + x^2 + x^3 +\cdots\text{,}\) we can take derivatives of both sides, given \(\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots\text{.}\) By the definition of generating functions, this says that \(\frac{1}{(1-x)^2}\) generates the sequence 1, 2, 3…. You can also find this using differencing or by multiplying.

12

Comenzando con la función generadora para\(1,2,3,4, \ldots\text{,}\) encontrar una función generadora para cada una de las siguientes secuencias.

1. \(1, 0, 2, 0, 3, 0, 4,\ldots\text{.}\)
2. \(1, -2, 3, -4, 5, -6, \ldots\text{.}\)
3. \(0, 3, 6, 9, 12, 15, 18, \ldots\text{.}\)
4. \(0, 3, 9, 18, 30, 45, 63,\ldots\text{.}\)(Pista: relaciona esta secuencia con la anterior.)

Contestar

1. \(\frac{1}{(1-x^2)^2}\text{.}\)
2. \(\frac{1}{(1+x)^2}\text{.}\)
3. \(\frac{3x}{(1-x)^2}\text{.}\)
4. \(\frac{3x}{(1-x)^3}\text{.}\) (partial sums).

13

Se puede suponer que\(1, 1, 2, 3, 5, 8,\ldots\) tiene función generadora\(\dfrac{1}{1-x-x^2}\) (porque lo hace). Utilice este hecho para encontrar la secuencia generada por cada una de las siguientes funciones generadoras.

1. \(\frac{x^2}{1-x-x^2}\text{.}\)
2. \(\frac{1}{1-x^2-x^4}\text{.}\)
3. \(\frac{1}{1-3x-9x^2}\text{.}\)
4. \(\frac{1}{(1-x-x^2)(1-x)}\text{.}\)

Contestar

1. \(0,0,1,1,2,3,5,8, \ldots\text{.}\)
2. \(1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, \ldots\text{.}\)
3. \(1, 3, 18, 81, 405, \ldots\text{.}\)
4. \(1, 2, 4, 7, 12, 20, \ldots\text{.}\)

14

Encuentra la función generadora para la secuencia\(1, -2, 4, -8, 16, \ldots\text{.}\)

Contestar

\(\frac{1}{1+2x}\text{.}\)

15

Encuentra la función generadora para la secuencia\(1, 1, 1, 2, 3, 4, 5, 6, \ldots\text{.}\)

Contestar

\(\frac{x^3}{(1-x)^2} + \frac{1}{1-x}\text{.}\)

16

Supongamos que\(A\) es la función generadora para la secuencia\(3, 5, 9, 15, 23, 33, \ldots\text{.}\)

1. Encontrar una función generadora (en términos de\(A\)) para la secuencia de diferencias entre términos.
2. Escribe la secuencia de diferencias entre términos y encuentra una función generadora para ello (sin hacer referencia\(A\)).
3. Usa tus respuestas a las partes (a) y (b) para encontrar la función generadora para la secuencia original.

Contestar

1. \((1-x)A = 3 + 2x + 4x^2 + 6x^3 + \cdots\) which is almost right. We can fix it like this: \(2 + 4x + 6x^2 + \cdots = \frac{(1-x)A - 3}{x}\text{.}\)
2. Sabemos\(2 + 4x + 6x^3 + \cdots = \frac{2}{(1-x)^2}\text{.}\)
3. \(A = \frac{2x}{(1-x)^3} + \frac{3}{1-x} = \frac{3 -4x + 3x^2}{(1-x)^3}\text{.}\)

5.2: Introducción a la Teoría de Números

1

Supongamos\(a\text{,}\)\(b\text{,}\) y\(c\) son enteros. Demostrar que si\(a \mid b\text{,}\) entonces\(a \mid bc\text{.}\)

Contestar

Prueba

Supongamos\(a \mid b\text{.}\) Then \(b\) is a multiple of \(a\text{,}\) or in other words, \(b = ak\) for some \(k\text{.}\) But then \(bc = akc\text{,}\) and since \(kc\) is an integer, this says \(bc\) is a multiple of \(a\text{.}\) In other words, \(a \mid bc\text{.}\)

\(\square\)

2

Supongamos\(a\text{,}\)\(b\text{,}\) y\(c\) son enteros. Demostrar que si\(a \mid b\) y\(a \mid c\) entonces\(a \mid b+c\) y\(a \mid b-c\text{.}\)

Contestar

Prueba

Asumir\(a \mid b\) and \(a \mid c\text{.}\) This means that \(b\) and \(c\) are both multiples of \(a\text{,}\) so \(b = am\) and \(c = an\) for integers \(m\) and \(n\text{.}\) Then \(b+c = am+an = a(m+n)\text{,}\) so \(b+c\) is a multiple of \(a\text{,}\) or equivalently, \(a \mid b+c\text{.}\) Similarly, \(b-c = am-an = a(m-n)\text{,}\) so \(b-c\) is a multiple of \(a\text{,}\) which is to say \(a \mid b-c\text{.}\)

\(\square\)

3

Escribe las clases restantes para\(n = 4\text{.}\)

Contestar

\(\{\ldots, -8, -4, 0, 4, 8, 12, \ldots\}\text{,}\) \(\{\ldots, -7, -3, 1, 5, 9, 13, \ldots\}\text{,}\)

\(\{\ldots, -6, -2, 2, 6, 10, 14, \ldots\}\text{,}\) and \(\{\ldots, -5, -1, 3, 7, 11, 15, \ldots\}\text{.}\)

4

Dejar\(a\text{,}\)\(b\text{,}\)\(c\text{,}\) y\(n\) ser enteros. Demostrar que si\(a \equiv b \pmod{n}\) y\(c \equiv d \pmod{n}\text{,}\) entonces\(a-c \equiv b-d \pmod{n}\text{.}\)

Contestar

Prueba

Asumir\(a \equiv b \pmod n\) and \(c \equiv d \pmod n\text{.}\) This means \(a = b + kn\) and \(c = d + jn\) for some integers \(k\) and \(j\text{.}\) Consider \(a-c\text{.}\) We have:

\ comenzar {ecuación*} a-c = b+kn - (d+jn) = b-d + (k-j) n.\ final {ecuación*}

En otras palabras,\(a-c\) is \(b-d\) more than some multiple of \(n\text{,}\) so \(a-c \equiv b-d \pmod n\text{.}\)

\(\square\)

5

Encuentra el resto de\(3^{456}\) cuando se divide por

1. 2.
2. 5.
3. 7.
4. 9.

Contestar

1. \(3^{456} \equiv 1^{456} = 1 \pmod 2\text{.}\)
2. \(3^{456} = 9^{228} \equiv (-1)^{228} = 1 \pmod{5}\text{.}\)
3. \(3^{456} = 9^{228} \equiv 2^{228} = 8^{76} \equiv 1^{76} = 1 \pmod 7\text{.}\)
4. \(3^{456} = 9^{228} \equiv 0^{228} = 0 \pmod{9}\text{.}\)

6

Determinar cuáles de las siguientes congruencias tienen soluciones, y encontrar cualquier solución (entre 0 y el módulo) por ensayo y error.

1. \(4x \equiv 5 \pmod 6\text{.}\)
2. \(4x \equiv 5 \pmod 7\text{.}\)
3. \(6x \equiv 3 \pmod 9\text{.}\)
4. \(6x \equiv 4 \pmod 9\text{.}\)
5. \(x^2 \equiv 2 \pmod 4\text{.}\)
6. \(x^2 \equiv 2 \pmod 7\text{.}\)

Contestar

Para todos estos, basta con enchufar todos los enteros entre 0 y el módulo para ver cuál, si los hay, funciona.

1. Sin soluciones.
2. \(x = 3\text{.}\)
3. \(x = 2\text{,}\) \(x = 5\text{,}\) \(x = 8\text{.}\)
4. Sin soluciones.
5. Sin soluciones.
6. \(x = 3\text{.}\)

7

Resolver las siguientes congruencias (describa la solución general).

1. \(5x + 8 \equiv 11 \pmod{22}\text{.}\)
2. \(6x \equiv 4 \pmod{10}\text{.}\)
3. \(4x \equiv 24 \pmod{30}\text{.}\)
4. \(341x \equiv 2941 \pmod{9}\text{.}\)

Contestar

1. \(x = 5+22k\) for \(k \in \Z\text{.}\)
2. \(x = 4 + 5k\) for \(k \in \Z\text{.}\)
3. \(x = 6 + 15k\) for \(k \in \Z\text{.}\)
4. Primero reducir cada número módulo 9, lo que se puede hacer sumando los dígitos de los números. Respuesta:\(x = 2 + 9k\) for \(k \in \Z\text{.}\)

8

Estoy pensando en un número. Si multiplicas mi número por 7, sumas 5, y divides el resultado por 11, te quedarás con un resto de 2. ¿Qué resto obtendrías si dividieras mi número original por 11?

Contestar

Debemos resolver\(7x + 5 \equiv 2 \pmod{11}\text{.}\) This gives \(x \equiv 9 \pmod{11}\text{.}\) In general, \(x = 9 + 11k\text{,}\) but when you divide any such \(x\) by 11, the remainder will be 9.

9

Resolver las siguientes ecuaciones lineales Diofantinas, usando aritmética modular (describa las soluciones generales).

1. \(6x + 10y = 32\text{.}\)
2. \(17x + 8y = 31\text{.}\)
3. \(35x + 47y = 1\text{.}\)

Contestar

1. Dividir por 2:\(3x + 5y = 16\text{.}\) Convert to a congruence, modulo 3: \(5y \equiv 16 \pmod 3\text{,}\) which reduces to \(2y \equiv 1 \pmod 3\text{.}\) So \(y \equiv 2 \pmod 3\) or \(y = 2 + 3k\text{.}\) Plug this back into \(3x + 5y = 16\) and solve for \(x\text{,}\) to get \(x = 2-5k\text{.}\) So the general solution is \(x = 2-5k\) and \(y = 2+3k\) for \(k \in \Z\text{.}\)
2. \(x = 7+8k\) and \(y = -11 - 17k\) for \(k \in \Z\text{.}\)
3. \(x = -4-47k\) and \(y = 3 + 35k\) for \(k \in \Z\text{.}\)

10

Tienes una botella de 13 oz y una botella de 20 oz. con las que deseas medir exactamente 2 oz. Sin embargo, tienes un suministro limitado de agua. Si entra cualquier agua en cualquiera de las botellas y luego se desecha, se va para siempre. ¿Cuál es la menor cantidad de agua con la que puedes comenzar y aún así completar la tarea?

Contestar

Primero, resolver la ecuación Diofantina\(13x + 20 y = 2\text{.}\) The general solution is \(x = -6 - 20k\) and \(y = 4+13k\text{.}\) Now if \(k = 0\text{,}\) this correspond to filling the 20 oz. bottle 4 times, and emptying the 13 oz. bottle 6 times, which would require 80 oz. of water. Increasing \(k\) would require considerably more water. Perhaps \(k = -1\) would be better? Then we would have \(x = -6+20 = 14\) and \(y = 4-13 = -11\text{,}\) which describes the solution where we fill the 13 oz. bottle 14 times, and empty the 20 oz. bottle 11 times. This would require 182 oz. of water. Thus the most efficient procedure is to repeatedly fill the 20 oz bottle, emptying it into the 13 oz bottle, and discarding full 13 oz. bottles, which requires 80 oz. of water.