5.E: Additional Topics (Exercises)

$\def\d{\displaystyle}$
$\newcommand{\f}[1]{\mathfrak #1}$
$\newcommand{\s}[1]{\mathscr #1}$
$\def\N{\mathbb N}$
$\def\B{\mathbf{B}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\Z{\mathbb Z}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\Q{\mathbb Q}$
$\def\circleB{(.5,0) circle (1)}$
$\def\R{\mathbb R}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\C{\mathbb C}$
$\def\circleC{(0,-1) circle (1)}$
$\def\F{\mathbb F}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\A{\mathbb A}$
$\def\twosetbox{(-2,-1.5) rectangle (2,1.5)}$
$\def\X{\mathbb X}$
$\def\threesetbox{(-2,-2.5) rectangle (2,1.5)}$
$\def\E{\mathbb E}$
$\def\O{\mathbb O}$
$\def\U{\mathcal U}$
$\def\pow{\mathcal P}$
$\def\inv{^{-1}}$
$\def\nrml{\triangleleft}$
$\def\st{:}$
$\def\~{\widetilde}$
$\def\rem{\mathcal R}$
$\def\sigalg{$\sigma$-algebra }$
$\def\Gal{\mbox{Gal}}$
$\def\iff{\leftrightarrow}$
$\def\Iff{\Leftrightarrow}$
$\def\land{\wedge}$
$\def\And{\bigwedge}$
$\def\entry{\entry}$
$\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}$
$\def\Vee{\bigvee}$
$\def\VVee{\d\Vee\mkern-18mu\Vee}$
$\def\imp{\rightarrow}$
$\def\Imp{\Rightarrow}$
$\def\Fi{\Leftarrow}$
$\def\var{\mbox{var}}$
$\def\Th{\mbox{Th}}$
$\def\entry{\entry}$
$\def\sat{\mbox{Sat}}$
$\def\con{\mbox{Con}}$
$\def\iffmodels{\bmodels\models}$
$\def\dbland{\bigwedge \!\!\bigwedge}$
$\def\dom{\mbox{dom}}$
$\def\rng{\mbox{range}}$
$\def\isom{\cong}$
$\DeclareMathOperator{\wgt}{wgt}$
$\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}$
$\newcommand{\va}[1]{\vtx{above}{#1}}$
$\newcommand{\vb}[1]{\vtx{below}{#1}}$
$\newcommand{\vr}[1]{\vtx{right}{#1}}$
$\newcommand{\vl}[1]{\vtx{left}{#1}}$
$\renewcommand{\v}{\vtx{above}{}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\circleB{(.5,0) circle (1)}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\circleC{(0,-1) circle (1)}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}$
$\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}$
$\def\ansfilename{practice-answers}$
$\def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }$
$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

$\newcommand{\hexbox}[3]{   \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}   \def\y{-\r*#1-sin{30}*\r*#1}   \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;   \draw (\x,\y) node{#3}; }$

$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

5.1: Generating Functions

1

Find the generating function for each of the following sequences by relating them back to a sequence with known generating function.

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{.}$

Answer

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

Find the sequence generated by the following generating functions:

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}$ (Hint: multiplication).

Answer

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

Show how you can get the generating function for the triangular numbers in three different ways:

1. Take two derivatives of the generating function for $1,1,1,1,1, \ldots$
2. Use differencing.
3. Multiply two known generating functions.

Answer

1. The second derivative of $\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. The triangular numbers are the sum of the first $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

Use differencing to find the generating function for $4, 5, 7, 10, 14, 19, 25, \ldots\text{.}$

Answer

Call the generating function $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

Find a generating function for the sequence with recurrence relation $a_n = 3a_{n-1} - a_{n-2}$ with initial terms $a_0 = 1$ and $a_1 = 5\text{.}$

Answer

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

6

Use the recurrence relation for the Fibonacci numbers to find the generating function for the Fibonacci sequence.

Answer

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

7

Use multiplication to find the generating function for the sequence of partial sums of Fibonacci numbers, $S_0, S_1, S_2, \ldots$ where $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$ and so on.

Answer

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

8

Find the generating function for the sequence with closed formula $a_n = 2(5^n) + 7(-3)^n\text{.}$

Answer

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

9

Find a closed formula for the $n$th term of the sequence with generating function $\dfrac{3x}{1-4x} + \dfrac{1}{1-x}\text{.}$

Answer

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

10

Find $a_7$ for the sequence with generating function $\dfrac{2}{(1-x)^2}\cdot\dfrac{x}{1-x-x^2}\text{.}$

Hint

you should “multiply” the two sequences.

Answer

158

11

Explain how we know that $\dfrac{1}{(1-x)^2}$ is the generating function for $1, 2, 3, 4, \ldots\text{.}$

Answer

Starting with $\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

Starting with the generating function for $1,2,3,4, \ldots\text{,}$ find a generating function for each of the following sequences.

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{.}$ (Hint: relate this sequence to the previous one.)

Answer

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

You may assume that $1, 1, 2, 3, 5, 8,\ldots$ has generating function $\dfrac{1}{1-x-x^2}$ (because it does). Use this fact to find the sequence generated by each of the following generating functions.

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{.}$

Answer

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

Find the generating function for the sequence $1, -2, 4, -8, 16, \ldots\text{.}$

Answer

$\frac{1}{1+2x}\text{.}$

15

Find the generating function for the sequence $1, 1, 1, 2, 3, 4, 5, 6, \ldots\text{.}$

Answer

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

16

Suppose $A$ is the generating function for the sequence $3, 5, 9, 15, 23, 33, \ldots\text{.}$

1. Find a generating function (in terms of $A$) for the sequence of differences between terms.
2. Write the sequence of differences between terms and find a generating function for it (without referencing $A$).
3. Use your answers to parts (a) and (b) to find the generating function for the original sequence.

Answer

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. We know $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: Introduction to Number Theory

1

Suppose $a\text{,}$ $b\text{,}$ and $c$ are integers. Prove that if $a \mid b\text{,}$ then $a \mid bc\text{.}$

Answer

Proof

Suppose $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

Suppose $a\text{,}$ $b\text{,}$ and $c$ are integers. Prove that if $a \mid b$ and $a \mid c$ then $a \mid b+c$ and $a \mid b-c\text{.}$

Answer

Proof

Assume $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

Write out the remainder classes for $n = 4\text{.}$

Answer

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

Let $a\text{,}$ $b\text{,}$ $c\text{,}$ and $n$ be integers. Prove that if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}\text{,}$ then $a-c \equiv b-d \pmod{n}\text{.}$

Answer

Proof

Assume $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:

$$\begin{equation*} a-c = b+kn - (d+jn) = b-d + (k-j)n. \end{equation*}$$

In other words, $a-c$ is $b-d$ more than some multiple of $n\text{,}$ so $a-c \equiv b-d \pmod n\text{.}$

$\square$

5

Find the remainder of $3^{456}$ when divided by

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

Answer

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

Determine which of the following congruences have solutions, and find any solutions (between 0 and the modulus) by trial and 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{.}$

Answer

For all of these, just plug in all integers between 0 and the modulus to see which, if any, work.

1. No solutions.
2. $x = 3\text{.}$
3. $x = 2\text{,}$ $x = 5\text{,}$ $x = 8\text{.}$
4. No solutions.
5. No solutions.
6. $x = 3\text{.}$

7

Solve the following congruences (describe the general solution).

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{.}$

Answer

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. First reduce each number modulo 9, which can be done by adding up the digits of the numbers. Answer: $x = 2 + 9k$ for $k \in \Z\text{.}$

8

I'm thinking of a number. If you multiply my number by 7, add 5, and divide the result by 11, you will be left with a remainder of 2. What remainder would you get if you divided my original number by 11?

Answer

We must solve $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

Solve the following linear Diophantine equations, using modular arithmetic (describe the general solutions).

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

Answer

1. Divide through by 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

You have a 13 oz. bottle and a 20 oz. bottle, with which you wish to measure exactly 2 oz. However, you have a limited supply of water. If any water enters either bottle and then gets dumped out, it is gone forever. What is the least amount of water you can start with and still complete the task?

Answer

First, solve the Diophantine equation $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.