5_1_3A_Generating_Functions

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/5%3A_Additional_Topics/5.1%3A_Generating_Functions

Skip to main content

\\ \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}{&}\\

There is an extremely powerful tool in discrete mathematics used to manipulate sequences called the generating function. The idea is this: instead of an infinite sequence (for example: \\2, 3, 5, 8, 12, \ldots\$ we look at a single function which encodes the sequence. But not a function which gives the \\n\\th term as output. Instead, a function whose power series (like from calculus) “displays” the terms of the sequence. So for example, we would look at the power series \\2 + 3x + 5x^2 + 8x^3 + 12x^4 + \cdots\\ which displays the sequence \\2, 3, 5, 8, 12, \ldots\\ as coefficients.

An infinite power series is simply an infinite sum of terms of the form \\c_nx^n\\ were \\c_n\\ is some constant. So we might write a power series like this:

\begin{equation\*} \sum\_{k=0}^\infty c_k x^k. \end{equation\*}

or expanded like this

\begin{equation\*} c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 + c_5x^5 + \cdots. \end{equation\*}

When viewed in the context of generating functions, we call such a power series a *generating series*. The generating series generates the sequence

\begin{equation\*} c_0, c_1, c_2, c_3, c_4, c_5, \ldots. \end{equation\*}

In other words, the sequence generated by a generating series is simply the sequence of *coefficients* of the infinite polynomial.

Example \\\PageIndex{1}\\

What sequence is represented by the generating series \\3 + 8x^2 + x^3 + \frac{x^5}{7} + 100x^6 + \cdots\text{?}\\

Solution

We just read off the coefficients of each \\x^n\\ term. So \\a_0 = 3\\ since the coefficient of \\x^0\\ is 3 (\\x^0 = 1\\ so this is the constant term). What is \\a_1\text{?}\\ It is NOT 8, since 8 is the coefficient of \\x^2\text{,}\\ so 8 is the term \\a_2\\ of the sequence. To find \\a_1\\ we need to look for the coefficient of \\x^1\\ which in this case is 0. So \\a_1 = 0\text{.}\\ Continuing, we have \\a_2 = 8\text{,}\\ \\a_3 = 1\text{,}\\ \\a_4 = 0\text{,}\\ and \\a_5 = \frac{1}{7}\text{.}\\ So we have the sequence

\begin{equation\*} 3, 0, 8, 1, \frac{1}{7}, 100, \ldots \end{equation\*}

Note that when discussing generating functions, we always start our sequence with \\a_0\text{.}\\

Now you might very naturally ask why we would do such a thing. One reason is that encoding a sequence with a power series helps us keep track of which term is which in the sequence. For example, if we write the sequence \\1, 3, 4, 6, 9, \ldots, 24, 41,\ldots\\ it is impossible to determine which term \\24\\ is (even if we agreed that the first term was supposed to be \\a_0\$. However, if we wrote the generating series instead, we would have \\1 + 3x + 4x^2 + 6x^3 + 9x^4 + \cdots + 24 x^{17} + 41 x^{18} + \cdots\text{.}\\ Now it is clear that 24 is the 17th term of the sequence (that is, \\a\_{17} = 24\$. Of course to get this benefit we could have displayed our sequence in any number of ways, perhaps \\\fbox{1}\_0 \fbox{3}\_1 \fbox{4}\_2 \fbox{6}\_3 \fbox{9}\_4 \cdots \fbox{24}\_{17}\fbox{41}\_{18}\cdots\text{,}\\ but we do not do this. The reason is that the generating series looks like an ordinary power series (although we are interpreting it differently) so we can do things with it that we ordinarily do with power series such as write down what it converges to.

For example, from calculus we know that the power series \\1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdots + \frac{x^n}{n!} + \cdots\\ converges to the function \\e^x\text{.}\\ So we can use \\e^x\\ as a way of talking about the sequence of coefficients of the power series for \\e^x\text{.}\\ When we write down a nice compact function which has an infinite power series that we view as a generating series, then we call that function a *generating function*. In this example, we would say

\begin{equation\*} 1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24}, \ldots, \frac{1}{n!}, \ldots \mbox{ has generating function } e^x \end{equation\*}

Building Generating Functions

The \\e^x\\ example is very specific. We have a rather odd sequence, and the only reason we know its generating function is because we happen to know the Taylor series for \\e^x\text{.}\\ Our goal now is to gather some tools to build the generating function of a particular given sequence.

Let's see what the generating functions are for some very simple sequences. The simplest of all: 1, 1, 1, 1, 1, …. What does the *generating series* look like? It is simply \\1 + x + x^2 + x^3 + x^4 + \cdots\text{.}\\ Now, can we find a closed formula for this power series? Yes! This particular series is really just a geometric series with common ratio \\x\text{.}\\ So if we use our “multiply, shift and subtract” technique from Section 2.2, we have

\begin{align\*} S \amp = 1 + x + x^2 + x^3 + \cdots\\ \underline{- xS} \amp \underline{\\\\ = \~\~\~\~\~~ x + x^2 + x^3 + x^4 + \cdots}\\ (1-x)S \amp = 1 \end{align\*}

Therefore we see that

\begin{equation\*} 1 + x + x^2 + x^3 \cdots = \dfrac{1}{1-x} \end{equation\*}

You might remember from calculus that this is only true on the interval of convergence for the power series, in this case when \\\|x\| \lt 1\text{.}\\ That is true for us, but we don't care. We are never going to plug anything in for \\x\text{,}\\ so as long as there is some value of \\x\\ for which the generating function and generating series agree, we are happy. And in this case we are happy.

\\1,1,1,\ldots\\

The generating function for \\1,1,1,1,1,1,\ldots\\ is \\\dfrac{1}{1-x}\\

Let's use this basic generating function to find generating functions for more sequences. What if we replace \\x\\ by \\-x\text{.}\\ We get

\begin{equation\*} \frac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots \mbox{ which generates } 1, -1, 1, -1, \ldots \end{equation\*}

If we replace \\x\\ by \\3x\\ we get

\begin{equation\*} \frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots \mbox{ which generates } 1, 3, 9, 27, \ldots \end{equation\*}

By replacing the \\x\\ in \\\frac{1}{1-x}\\ we can get generating functions for a variety of sequences, but not all. For example, you cannot plug in anything for \\x\\ to get the generating function for \\2,2,2,2, \ldots\text{.}\\ However, we are not lost yet. Notice that each term of \\2, 2, 2, 2, \ldots\\ is the result of multiplying the terms of \\1, 1, 1, 1, \ldots\\ by the constant 2. So multiply the generating function by 2 as well.

\begin{equation\*} \frac{2}{1-x} = 2 + 2x + 2x^2 + 2x^3 + \cdots \mbox{ which generates } 2, 2, 2, 2, \ldots \end{equation\*}

Similarly, to find the generating function for the sequence \\3, 9, 27, 81, \ldots\text{,}\\ we note that this sequence is the result of multiplying each term of \\1, 3, 9, 27, \ldots\\ by 3. Since we have the generating function for \\1, 3, 9, 27, \ldots\\ we can say

\begin{equation\*} \frac{3}{1-3x} = 3\cdot 1 + 3\cdot 3x + 3\cdot 9x^2 + 3\cdot 27x^3 + \cdots \mbox{ which generates } 3, 9, 27, 81, \ldots \end{equation\*}

What about the sequence \\2, 4, 10, 28, 82, \ldots\text{?}\\ Here the terms are always 1 more than powers of 3. That is, we have added the sequences \\1,1,1,1,\ldots\\ and \\1,3,9, 27,\ldots\\ term by term. Therefore we can get a generating function by adding the respective generating functions:

\begin{align\*} 2 + 4x + 10x^2 + 28x^3 + \cdots \amp = (1 + 1) + (1 + 3)x + (1 + 9)x^2 + (1 + 27)x^3 + \cdots\\ \amp = 1 + x + x^2 + x^3 + \cdots + 1 + 3x + 9x^2 + 27x^3 + \cdots\\ \amp = \frac{1}{1-x} + \frac{1}{1-3x} \end{align\*}

The fun does not stop there: if we replace \\x\\ in our original generating function by \\x^2\\ we get

\begin{equation\*} \frac{1}{1-x^2} = 1 + x^2 + x^4 + x^6\cdots \mbox{ which generates } 1, 0, 1, 0, 1, 0, \ldots. \end{equation\*}

How could we get \\0,1,0,1,0,1,\ldots\text{?}\\ Start with the previous sequence and *shift* it over by 1. But how do you do this? To see how shifting works, let's first try to get the generating function for the sequence \\0, 1, 3, 9, 27, \ldots\text{.}\\ We know that \\\frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots\text{.}\\ To get the zero out front, we need the generating series to look like \\x + 3x^2 + 9x^3 + 27x^4+ \cdots\\ (so there is no constant term). Multiplying by \\x\\ has this effect. So the generating function for \\0, 1, 3, 9, 27, \ldots\\ is \\\frac{x}{1-3x}\text{.}\\ This will also work to get the generating function for \\0,1,0,1,0,1,\ldots\text{:}\\

\begin{equation\*} \frac{x}{1-x^2} = x + x^3 + x^5 + \cdots \mbox{ which generates } 0, 1, 0, 1, 0 , 1 \ldots \end{equation\*}

What if we add the sequences \\1,0,1,0,1,0,\ldots\\ and \\0,1,0,1,0,1,\ldots\\ term by term? We should get \\1,1,1,1,1,1\ldots\text{.}\\ What happens when we add the generating functions? It works (try it)!

\begin{equation\*} \frac{1}{1-x^2} + \frac{x}{1-x^2} = \frac{1}{1-x}. \end{equation\*}

Here's a sneaky one: what happens if you take the *derivative* of \\\frac{1}{1-x}\text{?}\\ We get \\\frac{1}{(1-x)^2}\text{.}\\ On the other hand, if we differentiate term by term in the power series, we get \$1 + x + x^2 + x^3 + \cdots)' = 1 + 2x + 3x^2 + 4x^3 + \cdots\\ which is the generating series for \\1, 2, 3, 4, \ldots\text{.}\\ This says

\\1,2,3,\ldots\\

The generating function for \\1, 2, 3, 4, 5, \ldots\\ is \\\d\frac{1}{(1-x)^2}.\\

Take a second derivative: \\\frac{2}{(1-x)^3} = 2 + 6x + 12x^2 + 20x^3 + \cdots\text{.}\\ So \\\frac{1}{(1-x)^3} = 1 + 3x + 6x^2 + 10x^3 + \cdots\\ is a generating function for the triangular numbers, \\1,3,6,10\ldots\\ (although here we have \\a_0 = 1\\ while \\T_0 = 0\\ usually).

Differencing

We have seen how to find generating functions from \\\frac{1}{1-x}\\ using multiplication (by a constant or by \\x\$, substitution, addition, and differentiation. To use each of these, you must notice a way to transform the sequence \\1,1,1,1,1\ldots\\ into your desired sequence. This is not always easy. It is also not really the way we have analyzed sequences. One thing we have considered often is the sequence of differences between terms of a sequence. This will turn out to be helpful in finding generating functions as well. The sequence of differences is often simpler than the original sequence. So if we know a generating function for the differences, we would like to use this to find a generating function for the original sequence.

For example, consider the sequence \\2, 4, 10, 28, 82, \ldots\text{.}\\ How could we move to the sequence of first differences: \\2, 6, 18, 54,\ldots\text{?}\\ We want to subtract 2 from the 4, 4 from the 10, 10 from the 28, and so on. So if we subtract (term by term) the sequence \\0, 2, 4, 10, 28,\ldots\\ from \\2, 4, 10, 28\ldots\text{,}\\ we will be set. We can get the generating function for \\0,2,4,10,28,\ldots\\ from the generating function for \\2,4,10,28\ldots\\ by multiplying by \\x\text{.}\\ Use \\A\\ to represent the generating function for \\2, 4, 10, 28, 82, \ldots\\ Then:

\begin{align\*} A \amp = 2 + 4x + 10x^2 +28x^3 + 82x^4 + \cdots\\ \underline{-xA} \amp \underline{\\\\= 0 + 2x + 4x^2 + 10x^3 + 28 x^4 + 82x^5 + \cdots}\\ (1-x)A \amp = 2 + 2x + 6x^2 + 18x^3 + 54x^4 + \cdots \end{align\*}

While we don't get exactly the sequence of differences, we do get something close. In this particular case, we already know the generating function \\A\\ (we found it in the previous section) but most of the time we will use this differencing technique to *find* \\A\text{:}\\ if we have the generating function for the sequence of differences, we can then solve for \\A\text{.}\\

Example \\\PageIndex{2}\\

Find a generating function for \\1, 3, 5, 7, 9,\ldots\text{.}\\

Solution

Notice that the sequence of differences is constant. We know how to find the generating function for any constant sequence. So denote the generating function for \\1, 3, 5, 7, 9, \ldots\\ by \\A\text{.}\\ We have

\begin{align\*} A \amp = 1 + 3x + 5x^2 + 7x^3 + 9x^4 + \cdots\\ \underline{-xA} \amp \underline{\\\\= 0 + x + 3x^2 + 5x^3 + 7x^4 + 9x^5 + \cdots}\\ (1-x)A \amp = 1 + 2x + 2x^2 + 2x^3 + 2x^4 + \cdots \end{align\*}

We know that \\2x + 2x^2 + 2x^3 + 2x^4 + \cdots = \dfrac{2x}{1-x}\text{.}\\ Thus

\begin{equation\*} (1-x)A = 1 + \frac{2x}{1-x}. \end{equation\*}

Now solve for \\A\text{:}\\

\begin{equation\*} A = \frac{1}{1-x} + \frac{2x}{(1-x)^2} = \frac{1+x}{(1-x)^2}. \end{equation\*}

Does this makes sense? Before we simplified the two fractions into one, we were adding the generating function for the sequence \\1,1,1,1,\ldots\\ to the generating function for the sequence \\0, 2, 4, 6, 8, 10, \ldots\\ (remember \\\frac{1}{(1-x)^2}\\ generates \\1,2,3,4,5, \ldots\text{,}\\ multiplying by \\2x\\ shifts it over, putting the zero out front, and doubles each term). If we add these term by term, we get the correct sequence \\1,3,5,7, 9, \ldots\text{.}\\

Now that we have a generating function for the odd numbers, we can use that to find the generating function for the squares:

Example \\\PageIndex{3}\\

Find the generating function for \\1, 4, 9, 16, \ldots\text{.}\\ Note we take \\1 = a_0\text{.}\\

Solution

Again we call the generating function for the sequence \\A\text{.}\\ Using differencing:

\begin{align\*} A \amp = 1 + 4x + 9x^2 + 16x^3 + \cdots\\ \underline{- xA} \amp \underline{\\\\ = 0 + x + 4x^2 + 9x^3 + 16x^4 + \cdots}\\ (1-x)A \amp = 1 + 3x + 5x^2 + 7x^3 + \cdots \end{align\*}

Since \\1 + 3x + 5x^2 + 7x^3 + \cdots = \d\frac{1+x}{(1-x)^2}\\ we have \\A = \d\frac{1+x}{(1-x)^3}\text{.}\\

In each of the examples above, we found the difference between consecutive terms which gave us a sequence of differences for which we knew a generating function. We can generalize this to more complicated relationships between terms of the sequence. For example, if we know that the sequence satisfies the recurrence relation \\a_n = 3a\_{n-1} - 2a\_{n-2}\text{?}\\ In other words, if we take a term of the sequence and subtract 3 times the previous term and then add 2 times the term before that, we get 0 (since \\a_n - 3a\_{n-1} + 2a\_{n-2} = 0\$. That will hold for all but the first two terms of the sequence. So after the first two terms, the sequence of results of these calculations would be a sequence of 0's, for which we definitely know a generating function.

Example \\\PageIndex{4}\\

The sequence \\1, 3, 7, 15, 31, 63, \ldots\\ satisfies the recurrence relation \\a_n = 3a\_{n-1} - 2a\_{n-2}\text{.}\\ Find the generating function for the sequence.

Solution

Call the generating function for the sequence \\A\text{.}\\ We have

\begin{align\*} A \amp = 1 + 3x + 7x^2 + 15x^3 + 31x^4 + \cdots + a_nx^n + \cdots\\ -3xA \amp = 0 - 3x - 9x^2 - 21x^3 - 45x^4 - \cdots - 3a\_{n-1}x^n - \cdots\\ \underline{+\~\~~2x^2A\_{~}^{~^{~}}} \amp \underline{\\\\ = 0 + 0x + 2x^2 + 6x^3 + 14x^4 + \cdots + 2a\_{n-2}x^n + \cdots}\\ (1-3x+2x^2)A \amp = 1 \end{align\*}

We multiplied \\A\\ by \\-3x\\ which shifts every term over one spot and multiplies them by \\-3\text{.}\\ On the third line, we multiplied \\A\\ by \\2x^2\text{,}\\ which shifted every term over two spots and multiplied them by 2. When we add up the corresponding terms, we are taking each term, subtracting 3 times the previous term, and adding 2 times the term before that. This will happen for each term after \\a_1\\ because \\a_n - 3a\_{n-1} + 2a\_{n-2} = 0\text{.}\\ In general, we might have two terms from the beginning of the generating series, although in this case the second term happens to be 0 as well.

Now we just need to solve for \\A\text{:}\\

\begin{equation\*} A = \frac{1}{1 - 3x + 2x^2}. \end{equation\*}

Multiplication and Partial Sums

What happens to the sequences when you multiply two generating functions? Let's see: \\A = a_0 + a_1x + a_2x^2 + \cdots\\ and \\B = b_0 + b_1x + b_2x^2 + \cdots\text{.}\\ To multiply \\A\\ and \\B\text{,}\\ we need to do a lot of distributing (infinite FOIL?) but keep in mind we will group like terms and only need to write down the first few terms to see the pattern. The constant term is \\a_0b_0\text{.}\\ The coefficient of \\x\\ is \\a_0b_1 + a_1b_0\text{.}\\ And so on. We get:

\begin{equation\*} AB = a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + (a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0)x^3 + \cdots \end{equation\*}

Example \\\PageIndex{5}\\

“Multiply” the sequence \\1, 2, 3, 4, \ldots\\ by the sequence \\1, 2, 4, 8, 16, \ldots\text{.}\\

Solution

The new constant term is just \\1 \cdot 1\text{.}\\ The next term will be \\1\cdot 2 + 2 \cdot 1 = 4\text{.}\\ The next term: \\1 \cdot 4 + 2 \cdot 2 + 3 \cdot 1 = 11\text{.}\\ One more: \\1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1 = 28\text{.}\\ The resulting sequence is

\begin{equation\*} 1, 4, 11, 28, 57, \ldots \end{equation\*}

Since the generating function for \\1,2,3,4, \ldots\\ is \\\frac{1}{(1-x)^2}\\ and the generating function for \\1,2,4,8, 16, \ldots\\ is \\\frac{1}{1-2x}\text{,}\\ we have that the generating function for \\1,4, 11, 28, 57, \ldots\\ is \\\frac{1}{(1-x)^2(1-2x)}\\

Consider the special case when you multiply a sequence by \\1, 1, 1, \ldots\text{.}\\ For example, multiply \\1,1,1,\ldots\\ by \\1, 2, 3, 4, 5\ldots\text{.}\\ The first term is \\1\cdot 1 = 1\text{.}\\ Then \\1\cdot 2 + 1 \cdot 1 = 3\text{.}\\ Then \\1\cdot 3 + 1\cdot 2 + 1 \cdot 1 = 6\text{.}\\ The next term will be 10. We are getting the triangular numbers. More precisely, we get the sequence of partial sums of \\1,2,3,4,5, \ldots\text{.}\\ In terms of generating functions, we take \\\frac{1}{1-x}\\ (generating \\1,1,1,1,1\ldots\$ and multiply it by \\\frac{1}{(1-x)^2}\\ (generating \\1,2,3,4,5,\ldots\$ and this give \\\frac{1}{(1-x)^3}\text{.}\\ This should not be a surprise as we found the same generating function for the triangular numbers earlier.

The point is, if you need to find a generating function for the sum of the first \\n\\ terms of a particular sequence, and you know the generating function for *that* sequence, you can multiply it by \\\frac{1}{1-x}\text{.}\\ To go back from the sequence of partial sums to the original sequence, you look at the sequence of differences. When you get the sequence of differences you end up multiplying by \\1-x\text{,}\\ or equivalently, dividing by \\\frac{1}{1-x}\text{.}\\ Multiplying by \\\frac{1}{1-x}\\ gives partial sums, dividing by \\\frac{1}{1-x}\\ gives differences.

Solving Recurrence Relations with Generating Functions

We conclude with an example of one of the many reasons studying generating functions is helpful. We can use generating functions to solve recurrence relations.

Example \\\PageIndex{6}\\

Solve the recurrence relation \\a_n = 3a\_{n-1} - 2a\_{n-2}\\ with initial conditions \\a_0 = 1\\ and \\a_1 = 3\text{.}\\

Solution

We saw in an example above that this recurrence relation gives the sequence \\1, 3, 7, 15, 31, 63, \ldots\\ which has generating function \\\dfrac{1}{1 - 3x + 2x^2}\text{.}\\ We did this by calling the generating function \\A\\ and then computing \\A - 3xA + 2x^2A\\ which was just 1, since every other term canceled out.

But how does knowing the generating function help us? First, break up the generating function into two simpler ones. For this, we can use partial fraction decomposition. Start by factoring the denominator:

\begin{equation\*} \frac{1}{1-3x + 2x^2} = \frac{1}{(1-x)(1-2x)}. \end{equation\*}

Partial fraction decomposition tells us that we can write this faction as the sum of two fractions (we decompose the given fraction):

\begin{equation\*} \frac{1}{(1-x)(1-2x)} = \frac{a}{1-x} + \frac{b}{1-2x} \text{ \~~ for some constants } a \text{ and } b. \end{equation\*}

To find \\a\\ and \\b\\ we add the two decomposed fractions using a common denominator. This gives

\begin{equation\*} \frac{1}{(1-x)(1-2x)} = \frac{a(1-2x) + b(1-x)}{(1-x)(1-2x)}. \end{equation\*}

so

\begin{equation\*} 1 = a(1-2x) + b(1-x). \end{equation\*}

This must be true for all values of \\x\text{.}\\ If \\x = 1\text{,}\\ then the equation becomes \\1 = -a\\ so \\a = -1\text{.}\\ When \\x = \frac{1}{2}\\ we get \\1 = b/2\\ so \\b = 2\text{.}\\ This tells us that we can decompose the fraction like this:

\begin{equation\*} \frac{1}{(1-x)(1-2x)} = \frac{-1}{1-x} + \frac{2}{1-2x}. \end{equation\*}

This completes the partial fraction decomposition. Notice that these two fractions are generating functions we know. In fact, we should be able to expand each of them.

\begin{equation\*} \frac{-1}{1-x} = -1 - x - x^2 -x^3 - x^4 - \cdots \mbox{ which generates } -1, -1, -1, -1, -1, \ldots. \end{equation\*} \begin{equation\*} \frac{2}{1-2x} = 2 + 4x + 8x^2 + 16x^3 + 32x^4 + \cdots \mbox{ which generates } 2, 4, 8, 16, 32, \ldots. \end{equation\*}

We can give a closed formula for the \\n\\th term of each of these sequences. The first is just \\a_n = -1\text{.}\\ The second is \\a_n = 2^{n+1}\text{.}\\ The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is

\begin{equation\*} a_n = 2^{n+1} - 1 \end{equation\*}​​​​​​​

We can now add generating functions to our list of methods for solving recurrence relations.

---

5_2_3A_Introduction_to_Number_Theory

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/5%3A_Additional_Topics/5.2%3A_Introduction_to_Number_Theory

Skip to main content

\\ \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}{&}\\

We have used the natural numbers to solve problems. This was the right set of numbers to work with in discrete mathematics because we always dealt with a whole number of things. The natural numbers have been a tool. Let's take a moment now to inspect that tool. What mathematical discoveries can we make *about* the natural numbers themselves?

This is the main question of number theory: a huge, ancient, complex, and above all, beautiful branch of mathematics. Historically, number theory was known as the Queen of Mathematics and was very much a branch of *pure* mathematics, studied for its own sake instead of as a means to understanding real world applications. This has changed in recent years however, as applications of number theory have been unearthed. Probably the most well known example of this is RSA cryptography, one of the methods used in encrypt data on the internet. It is number theory that makes this possible.

What sorts of questions belong to the realm of number theory? Here is a motivating example. Recall in our study of induction, we asked:

Which amounts of postage can be made exactly using just 5-cent and 8-cent stamps?

We were able to prove that *any* amount greater than 27 cents could be made. You might wonder what would happen if we changed the denomination of the stamps. What if we instead had 4- and 9-cent stamps? Would there be some amount after which all amounts would be possible? Well, again, we could replace two 4-cent stamps with a 9-cent stamp, or three 9-cent stamps with seven 4-cent stamps. In each case we can create one more cent of postage. Using this as the inductive case would allow us to prove that any amount of postage greater than 23 cents can be made.

What if we had 2-cent and 4-cent stamps. Here it looks less promising. If we take some number of 2-cent stamps and some number of 4-cent stamps, what can we say about the total? Could it ever be odd? Doesn't look like it.

*Why* does 5 and 8 work, 4 and 9 work, but 2 and 4 not work? What is it about these numbers? If I gave you a pair of numbers, could you tell me right away if they would work or not? We will answer these questions, and more, after first investigating some simpler properties of numbers themselves.

Divisibility

It is easy to add and multiply natural numbers. If we extend our focus to all integers, then subtraction is also easy (we need the negative numbers so we can subtract any number from any other number, even larger from smaller). Division is the first operation that presents a challenge. If we wanted to extend our set of numbers so any division would be possible (maybe excluding division by 0) we would need to look at the rational numbers (the set of all numbers which can be written as fractions). This would be going too far, so we will refuse this option.

In fact, it is a good thing that not every number can be divided by other numbers. This helps us understand the structure of the natural numbers and opens the door to many interesting questions and applications.

If given numbers \\a\\ and \\b\text{,}\\ it is possible that \\a \div b\\ gives a whole number. In this case, we say that \\b\\ *divides* \\a\text{,}\\ in symbols, we write \\b \mid a\text{.}\\ If this holds, then \\b\\ is a divisor or factor of \\a\text{,}\\ and \\a\\ is a multiple of \\b\text{.}\\ In other words, if \\b \mid a\text{,}\\ then \\a = bk\\ for some integer \\k\\ (this is saying \\a\\ is some multiple of \\b\$.

The Divisibility Relation

Given integers \\m\\ and \\n\text{,}\\ we say “\\m\\ divides \\n\\” and write

\begin{equation\*} m \mid n \end{equation\*}

provided \\n \div m\\ is an integer. Thus the following assertions mean the same thing:

1. \\m \mid n\\

2. \\n = mk\\ for some integer \\k\\

3. \\m\\ is a factor (or divisor) of \\n\\

4. \\n\\ is a multiple of \\m\text{.}\\

Notice that \\m \mid n\\ is a statement. It is either true or false. On the other hand, \\n \div m\\ or \\n/m\\ is some number. If we want to claim that \\n/m\\ is not an integer, so \\m\\ does not divide \\n\text{,}\\ then we can write \\m \nmid n\text{.}\\

Example \\\PageIndex{1}\\

Decide whether each of the statements below are true or false.

1. \\4 \mid 20\\

2. \\20 \mid 4\\

3. \\0 \mid 5\\

4. \\5 \mid 0\\

5. \\7 \mid 7\\

6. \\1 \mid 37\\

7. \\-3 \mid 12\\

8. \\8 \mid 12\\

9. \\1642 \mid 136299\\

Solution

1. True. 4 “goes into” 20 five times without remainder. In other words, \\20 \div 4 = 5\text{,}\\ an integer. We could also justify this by saying that \\20\\ is a multiple of 4: \\20 = 4\cdot 5\text{.}\\

2. False. While 20 is a multiple of 4, it is false that \\4\\ is a multiple of 20.

3. False. \\5 \div 0\\ is not even defined, let alone an integer.

4. True. In fact, \\x \mid 0\\ is true for all \\x\text{.}\\ This is because 0 is a multiple of every number: \\0 = x\cdot 0\text{.}\\

5. True. In fact, \\x \mid x\\ is true for all \\x\text{.}\\

6. True. 1 divides every number (other than 0).

7. True. Negative numbers work just fine for the divisibility relation. Here \\12 = -3 \cdot 4\text{.}\\ It is also true that \\3 \mid -12\\ and that \\-3 \mid -12\text{.}\\

8. False. Both 8 and 12 are divisible by 4, but this does not mean that \\12\\ is divisible by \\8\text{.}\\

9. False. See below.

This last example raises a question: how might one decide whether \\m \mid n\text{?}\\ Of course, if you had a trusted calculator, you could ask it for the value of \\n \div m\text{.}\\ If it spits out anything other than an integer, you know \\m \nmid n\text{.}\\ This seems a little like cheating though: we don't have division, so should we really use division to check divisibility?

While we don't really know how to divide, we do know how to multiply. We might try multiplying \\m\\ by larger and larger numbers until we get close to \\n\text{.}\\ How close? Well, we want to be sure that if we multiply \\m\\ by the next larger integer, we go over \\n\text{.}\\

For example, let's try this to decide whether \\1642 \mid 136299\text{.}\\ Start finding multiples of 1642:

\begin{equation\*} 1642 \cdot 2 = 3284 \qquad 1642 \cdot 3 = 4926 \qquad 1642\cdot 4 = 6568 \qquad \cdots \end{equation\*}

All of these are well less than 136299. I suppose we can jump ahead a bit:

\begin{equation\*} 1642 \cdot 50 = 82100 \qquad 1642 \cdot 80 = 131360 \qquad 1642 \cdot 85 = 139570 \end{equation\*}

Ah, so we need to look somewhere between 80 and 85. Try 83:

\begin{equation\*} 1642 \cdot 83 = 136286 \end{equation\*}

Is this the best we can do? How far are we from our desired 136299? If we subtract, we get \\136299 - 136286 = 13\text{.}\\ So we know we cannot go up to 84, that will be too much. In other words, we have found that

\begin{equation\*} 136299 = 83 \cdot 1642 + 13 \end{equation\*}

Since \\13 \< 1642\text{,}\\ we can now safely say that \\1642 \nmid 136299\text{.}\\

It turns out that the process we went through above can be repeated for any pair of numbers. We can always write the number \\a\\ as some multiple of the number \\b\\ plus some remainder. We know this because we know about *division with remainder* from elementary school. This is just a way of saying it using multiplication. Due to the procedural nature that can be used to find the remainder, this fact is usually called the *division algorithm*:

The Division Algorithm

Given any two integers \\a\\ and \\b\text{,}\\ we can always find an integer \\q\\ such that

\begin{equation\*} a = qb + r \end{equation\*}

where \\r\\ is an integer satisfying \\0 \le r \< \|b\|\\

The idea is that we can always take a large enough multiple of \\b\\ so that the remainder \\r\\ is as small as possible. We do allow the possibility of \\r = 0\text{,}\\ in which case we have \\b \mid a\text{.}\\

Remainder Classes

The division algorithm tells us that there are only \\b\\ possible remainders when dividing by \\b\text{.}\\ If we fix this divisor, we can group integers by the remainder. Each group is called a *remainder class modulo \\b\\* (or sometimes *residue class*).

Example \\\PageIndex{2}\\

Describe the remainder classes modulo \\5\text{.}\\

Solution

We want to classify numbers by what their remainder would be when divided by \\5\text{.}\\ From the division algorithm, we know there will be exactly 5 remainder classes, because there are only 5 choices for what \\r\\ could be (\\0 \le r \< 5\$.

First consider \\r = 0\text{.}\\ Here we are looking for all the numbers divisible by \\5\\ since \\a = 5q+0\text{.}\\ In other words, the multiples of 5. We get the infinite set

\begin{equation\*} \\\ldots, -15, -10, -5, 0, 5, 10, 15, 20, \ldots\\ \end{equation\*}

Notice we also include negative integers.

Next consider \\r = 1\text{.}\\ Which integers, when divided by 5, have remainder 1? Well, certainly 1, does, as does 6, and 11. Negatives? Here we must be careful: \\-6\\ does NOT have remainder 1. We can write \\-6 = -2\cdot 5 + 4\\ or \\-6 = -1 \cdot 5 - 1\text{,}\\ but only one of these is a “correct” instance of the division algorithm: \\r = 4\\ since we need \\r\\ to be non-negative. So in fact, to get \\r = 1\text{,}\\ we would have \\-4\text{,}\\ or \\-9\text{,}\\ etc. Thus we get the remainder class

\begin{equation\*} \\\ldots, -14, -9, -4, 1, 6, 11, 16, 21, \ldots\\ \end{equation\*}

There are three more to go. The remainder classes for \\2\text{,}\\ \\3\text{,}\\ and \\4\\ are, respectively

\begin{equation\*} \\\ldots, -13, -8, -3, 2, 7, 12, 17, 22,\ldots\\ \end{equation\*} \begin{equation\*} \\\ldots, -12, -7, -2, 3, 8, 13, 18, 23, \ldots\\ \end{equation\*} \begin{equation\*} \\\ldots, -11, -6, -1, 4, 9, 14, 19, 24, \ldots\\. \end{equation\*}

Note that in the example above, *every* integer is in exactly one remainder class. The technical way to say this is that the remainder classes modulo \\b\\ form a *partition* of the integers.¹It is possible to develop a mathematical theory of partitions, prove statements about all partitions in general and then apply those observations to our case here. The most important fact about partitions, is that it is possible to define an *equivalence relation* from a partition: this is a relationship between pairs of numbers which acts in all the important ways like the “equals” relationship.²Again, there is a mathematical theory of equivalence relations which applies in many more instances than the one we look at here.

All fun technical language aside, the idea is really simple. If two numbers belong to the same remainder class, then in some way, they are the same. That is, they are the same *up to division by \\b\\*. In the case where \\b = 5\\ above, the numbers \\8\\ and \\23\text{,}\\ while not the same number, are the same when it comes to dividing by 5, because both have remainder \\3\text{.}\\

It matters what the divisor is: \\8\\ and \\23\\ are the same up to division by \\5\text{,}\\ but not up to division by \\7\text{,}\\ since \\8\\ has remainder of 1 when divided by 7 while 23 has a remainder of 2.

With all this in mind, let's introduce some notation. We want to say that \\8\\ and 23 are basically the same, even though they are not equal. It would be wrong to say \\8 = 23\text{.}\\ Instead, we write \\8 \equiv 23\text{.}\\ But this is not always true. It works if we are thinking division by 5, so we need to denote that somehow. What we will actually write is this:

\begin{equation\*} 8 \equiv 23 \pmod{5} \end{equation\*}

which is read, “8 is congruent to 23 modulo 5” (or just “mod 5”). Of course then we could observe that

\begin{equation\*} 8 \not\equiv 23 \pmod{7} \end{equation\*}

Congruence Modulo \\n\\

We say \\a\\ is congruent to \\b\\ modulo \\n\\ , and write,

\begin{equation\*} a \equiv b \pmod{n} \end{equation\*}

provided \\a\\ and \\b\\ have the same remainder when divided by \\n\text{.}\\ In other words, provided \\a\\ and \\b\\ belong to the same remainder class modulo \\n\text{.}\\

Many books define congruence modulo \\n\\ slightly differently. They say that \\a \equiv b \pmod{n}\\ if and only if \\n \mid a-b\text{.}\\ In other words, two numbers are congruent modulo \\n\text{,}\\ if their difference is a multiple of \\n\text{.}\\ So which definition is correct? Turns out, it doesn't matter: they are equivalent.

To see why, consider two numbers \\a\\ and \\b\\ which are congruent modulo \\n\text{.}\\ Then \\a\\ and \\b\\ have the same remainder when divided by \\n\text{.}\\ We have

\begin{equation\*} a = q_1 n + r \qquad\qquad b = q_2 n + r \end{equation\*}

Here the two \\r\\'s really are the same. Consider what we get when we take the difference of \\a\\ and \\b\text{:}\\

\begin{equation\*} a-b = q_1n + r - (q_2n + r) = q_1n - q_2 n = (q_1-q_2)n \end{equation\*}

So \\a-b\\ is a multiple of \\n\text{,}\\ or equivalently, \\n \mid a-b\text{.}\\

On the other hand, if we assume first that \\n \mid a-b\text{,}\\ so \\a-b = kn\text{,}\\ then consider what happens if we divide each term by \\n\text{.}\\ Dividing \\a\\ by \\n\\ will leave some remainder, as will dividing \\b\\ by \\n\text{.}\\ However, dividing \\kn\\ by \\n\\ will leave 0 remainder. So the remainders on the left-hand side must cancel out. That is, the remainders must be the same.

Thus we have:

Congruence and Divisibility

For any integers \\a\text{,}\\ \\b\text{,}\\ and \\n\text{,}\\ we have

\begin{equation\*} a \equiv b \pmod{n} \qquad \mbox{ if and only if } \qquad n \mid a-b. \end{equation\*}

It will also be useful to switch back and forth between congruences and regular equations. The above fact helps with this. We know that \\a \equiv b \pmod{n}\\ if and only if \\n \mid a-b\text{,}\\ if and only if \\a-b = kn\\ for some integer \\k\text{.}\\ Rearranging that equation, we get \\a = b + kn\text{.}\\ In other words, if \\a\\ and \\b\\ are congruent modulo \\n\text{,}\\ then \\a\\ is \\b\\ more than some multiple of \\n\text{.}\\ This conforms with our earlier observation that all the numbers in a particular remainder class are the same amount larger than the multiples of \\n\text{.}\\

Congruence and Equality

For any integers \\a\text{,}\\ \\b\text{,}\\ and \\n\text{,}\\ we have

\begin{equation\*} a \equiv b \pmod{n} \qquad \mbox{ if and only if } \qquad a = b + kn \mbox{ for some integer } k . \end{equation\*}

Properties of Congruence

We said earlier that congruence modulo \\n\\ behaves, in many important ways, the same way equality does. Specifically, we could prove that congruence modulo \\n\\ is an *equivalence relation*, which would require checking the following three facts:

Congruence Modulo \\n\\ is an Equivalence Relation

Given any integers \\a\text{,}\\ \\b\text{,}\\ and \\c\text{,}\\ and any positive integer \\n\text{,}\\ the following hold:

1. \\a \equiv a \pmod{n}\text{.}\\

2. If \\a \equiv b \pmod{n}\\ then \\b \equiv a \pmod{n}\text{.}\\

3. If \\a \equiv b \pmod{n}\\ and \\b \equiv c \pmod{n}\text{,}\\ then \\a \equiv c \pmod{n}\text{.}\\

In other words, congruence modulo \\n\\ is reflexive, symmetric, and transitive, so is an equivalence relation.

You should take a minute to convince yourself that each of the properties above actually hold of congruence. Try explaining each using both the remainder and divisibility definitions.

Next, consider how congruence behaves when doing basic arithmetic. We already know that if you subtract two congruent numbers, the result will be congruent to 0 (be a multiple of \\n\$. What if we add something congruent to 1 to something congruent to 2? Will we get something congruent to 3?

Congruence and Arithmetic

Suppose \\a \equiv b \pmod{n}\\ and \\c \equiv d \pmod{n}\text{.}\\ Then the following hold:

1. \\a+c \equiv b+d \pmod{n}\text{.}\\

2. \\a-c \equiv b-d \pmod{n}\text{.}\\

3. \\ac \equiv bd \pmod{n}\text{.}\\

The above facts might be written a little strangely, but the idea is simple. If we have a true congruence, and we add the same thing to both sides, the result is still a true congruence. This sounds like we are saying:

If \\a \equiv b \pmod{n}\\ then \\a+c \equiv b+c \pmod{n}\text{.}\\

Of course this is true as well, it is the special case where \\c = d\text{.}\\ But what we have works in more generality. Think of congruence as being “basically equal.” If we have two numbers which are basically equal, and we add basically the same thing to both sides, the result will be basically equal.

This seems reasonable. Is it really true? Let's prove the first fact:

Proof

Suppose \\a \equiv b \pmod{n}\\ and \\c \equiv d \pmod{n}\text{.}\\ That means \\a = b + kn\\ and \\c = d + jn\\ for integers \\k\\ and \\j\text{.}\\ Add these equations:

\begin{equation\*} a+c = b+d + kn + jn. \end{equation\*}

But \\kn + jn = (k+j)n\text{,}\\ which is just a multiple of \\n\text{.}\\ So \\a+c = b+d + (j+k)n\text{,}\\ or in other words, \\a+c \equiv b+d \pmod{n}\\

\\\square\\

The other two facts can be proved in a similar way.

One of the important consequences of these facts about congruences, is that we can basically replace any number in a congruence with any other number it is congruent to. Here are some examples to see how (and why) that works:

Example \\\PageIndex{3}\\

Find the remainder of \\3491\\ divided by \\9\text{.}\\

Solution

We could do long division, but there is another way. We want to find \\x\\ such that \\x \equiv 3491 \pmod{9}\text{.}\\ Now \\3491 = 3000 + 400 + 90 + 1\text{.}\\ Of course \\90 \equiv 0 \pmod 9\text{,}\\ so we can replace the 90 in the sum with 0. Why is this okay? We are actually subtracting the “same” thing from both sides:

\begin{equation\*} \begin{aligned}x \amp \equiv 3000 + 400 + 90 + 1 \pmod 9 \\ - \~~ 0 \amp \equiv 90 \pmod 9 \\ x \amp \equiv 3000 + 400 + 0 + 1\pmod 9. \end{aligned} \end{equation\*}

Next, note that \\400 = 4 \cdot 100\text{,}\\ and \\100 \equiv 1 \pmod 9\\ (since \\9 \mid 99\$. So we can in fact replace the 400 with simply a 4. Again, we are appealing to our claim that we can replace congruent elements, but we are really appealing to property 3 about the arithmetic of congruence: we know \\100 \equiv 1 \pmod{9}\text{,}\\ so if we multiply both sides by \\4\text{,}\\ we get \\400 \equiv 4 \pmod 9\text{.}\\

Similarly, we can replace 3000 with 3, since \\1000 = 1 + 999 \equiv 1 \pmod 9\text{.}\\ So our original congruence becomes

\begin{equation\*} x \equiv 3 + 4 + 0 + 1 \pmod 9 \end{equation\*} \begin{equation\*} x \equiv 8 \pmod 9. \end{equation\*}

Therefore \\3491\\ divided by 9 has remainder 8.

The above example should convince you that the well known divisibility test for 9 is true: the sum of the digits of a number is divisible by 9 if and only if the original number is divisible by 9. In fact, we now know something more: any number is congruent to the sum of its digits, modulo 9.³This works for 3 as well, but definitely not for any modulus in general.

Let's try another:

Example \\\PageIndex{4}\\

Find the remainder when \\3^{123}\\ is divided by 7.

Solution

Of course, we are working with congruence because we want to find the smallest positive \\x\\ such that \\x \equiv 3^{123} \pmod 7\text{.}\\ Now first write \\3^{123} = (3^3)^{41}\text{.}\\ We have:

\begin{equation\*} 3^{123} = 27^{41} \equiv 6^{41} \pmod 7, \end{equation\*}

since \\27 \equiv 6 \pmod 7\text{.}\\ Notice further that \\6^2 = 36\\ is congruent to 1 modulo 7. Thus we can simplify further:

\begin{equation\*} 6^{41} = 6\cdot (6^2)^{20} \equiv 6 \cdot 1^{20} \pmod 7. \end{equation\*}

But \\1^{20} = 1\text{,}\\ so we are done:

\begin{equation\*} 3^{123} \equiv 6 \pmod 7. \end{equation\*}

In the above example, we are using the fact that if \\a \equiv b \pmod n\text{,}\\ then \\a^p \equiv b^p \pmod n\text{.}\\ This is just applying property 3 a bunch of times.

So far we have seen how to add, subtract and multiply with congruences. What about division? There is a reason we have waited to discuss it. It turns out that we cannot simply divide. In other words, even if \\ad \equiv bd \pmod n\text{,}\\ we do not know that \\a \equiv b \pmod n\text{.}\\ Consider, for example:

\begin{equation\*} 18 \equiv 42 \pmod 8. \end{equation\*}

This is true. Now \\18\\ and \\42\\ are both divisible by 6. However,

\begin{equation\*} 3 \not\equiv 7 \pmod 8. \end{equation\*}

While this doesn't work, note that \\3 \equiv 7 \pmod 4\text{.}\\ We cannot divide \\8\\ by 6, but we can divide 8 by the greatest common factor of \\8\\ and \\6\text{.}\\ Will this always happen?

Suppose \\ad \equiv bd \pmod n\text{.}\\ In other words, we have \\ad = bd + kn\\ for some integer \\k\text{.}\\ Of course \\ad\\ is divisible by \\d\text{,}\\ as is \\bd\text{.}\\ So \\kn\\ must also be divisible by \\d\text{.}\\ Now if \\n\\ and \\d\\ have no common factors (other than 1), then we must have \\d \mid k\text{.}\\ But in general, if we try to divide \\kn\\ by \\d\text{,}\\ we don't know that we will get an integer multiple of \\n\text{.}\\ Some of the \\n\\ might get divided as well. To be safe, let's divide as much of \\n\\ as we can. Take the largest factor of both \\d\\ and \\n\text{,}\\ and cancel that out from \\n\text{.}\\ The rest of the factors of \\d\\ will come from \\k\text{,}\\ no problem.

We will call the largest factor of both \\d\\ and \\n\\ the \\\gcd(d,n)\text{,}\\ for *greatest common divisor*. In our example above, \\\gcd(6,8) = 2\\ since the greatest divisor common to 6 and 8 is 2.

Congruence and Division

Suppose \\ad \equiv bd \pmod n\text{.}\\ Then \\a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}\\

If \\d\\ and \\n\\ have no common factors then \\\gcd(d,n) = 1\text{,}\\ so \\a \equiv b \pmod n\text{.}\\

Example \\\PageIndex{5}\\

Simplify the following congruences using division: (a) \\24 \equiv 39 \pmod 5\\ and (b) \\24 \equiv 39 \pmod{15}\text{.}\\

Solution

$a$ Both \\24\\ and \\39\\ are divisible by \\3\text{,}\\ and \\3\\ and \\5\\ have no common factors, so we get

\begin{equation\*} 8 \equiv 13 \pmod 5. \end{equation\*}

$b$ Again, we can divide by 3. However, doing so blindly gives us \\8 \equiv 13 \pmod{15}\\ which is no longer true. Instead, we must also divide the modulus 15 by the greatest common factor of \\3\\ and \\15\text{,}\\ which is \\3\text{.}\\ Again we get

\begin{equation\*} 8 \equiv 13 \pmod 5. \end{equation\*}

Solving Congruences

Now that we have some algebraic rules to govern congruence relations, we can attempt to solve for an unknown in a congruence. For example, is there a value of \\x\\ that satisfies,

\begin{equation\*} 3x + 2 \equiv 4 \pmod{5}, \end{equation\*}

and if so, what is it?

In this example, since the modulus is small, we could simply try every possible value for \\x\text{.}\\ There are really only 5 to consider, since any integer that satisfied the congruence could be replaced with any other integer it was congruent to modulo 5. Here, when \\x = 4\\ we get \\3x + 2 = 14\\ which is indeed congruent to 4 modulo 5. This means that \\x = 9\\ and \\x = 14\\ and \\x = 19\\ and so on will each also be a solution because as we saw above, replacing any number in a congruence with a congruent number does not change the truth of the congruence.

So in this example, simply compute \\3x + 2\\ for values of \\x \in \\0,1,2,3,4\\\text{.}\\ This gives 2, 5, 8, 11, and 14 respectively, for which only 14 is congruent to 4.

Let's also see how you could solve this using our rules for the algebra of congruences. Such an approach would be much simpler than the trial and error tactic if the modulus was larger. First, we know we can subtract 2 from both sides:

\begin{equation\*} 3x \equiv 2 \pmod{5}. \end{equation\*}

Then to divide both sides by 3, we first add 0 to both sides. Of course, on the right-hand side, we want that 0 to be a 10 (yes, \\10\\ really is 0 since they are congruent modulo 5). This gives,

\begin{equation\*} 3x \equiv 12 \pmod{5}. \end{equation\*}

Now divide both sides by 3. Since \\\gcd(3,5) = 1\text{,}\\ we do not need to change the modulus:

\begin{equation\*} x \equiv 4 \pmod{5}. \end{equation\*}

Notice that this in fact gives the *general solution*: not only can \\x = 4\text{,}\\ but \\x\\ can be any number which is congruent to 4. We can leave it like this, or write “\\x = 4 + 5k\\ for any integer \\k\text{.}\\”

Example \\\PageIndex{6}\\

Solve the following congruences for \\x\text{.}\\

1. \\7x \equiv 12 \pmod{13}\text{.}\\

2. \\84x - 38 \equiv 79 \pmod{15}\text{.}\\

3. \\20x \equiv 23 \pmod{14}\text{.}\\

Solution

1. All we need to do here is divide both sides by 7. We add 13 to the right-hand side repeatedly until we get a multiple of 7 (adding 13 is the same as adding 0, so this is legal). We get \\25\text{,}\\ \\38\text{,}\\ \\51\text{,}\\ \\64\text{,}\\ \\77\\ – got it. So we have: \begin{equation\*} \begin{aligned}7x \amp \equiv 12 \pmod{13} \\ 7x \amp \equiv 77 \pmod{13} \\ x \amp \equiv 11 \pmod{13}. \end{aligned} \end{equation\*}

2. Here, since we have numbers larger than the modulus, we can reduce them prior to applying any algebra. We have \\84 \equiv 9\text{,}\\ \\38 \equiv 8\\ and \\79 \equiv 4\text{.}\\ Thus, \begin{equation\*} \begin{aligned}84x - 38 \amp \equiv 79 \pmod{15} \\ 9x - 8 \amp \equiv 4 \pmod{15} \\ 9x \amp \equiv 12 \pmod{15} \\ 9x \amp \equiv 72 \pmod{15}. \end{aligned} \end{equation\*} We got the 72 by adding \\0 \equiv 60 \pmod{15}\\ to both sides of the congruence. Now divide both sides by 9. However, since \\\gcd(9, 15) = 3\text{,}\\ we must divide the modulus by 3 as well: \begin{equation\*} x \equiv 8 \pmod 5. \end{equation\*} So the solutions are those values which are congruent to 8, or equivalently 3, modulo 5. This means that in some sense there are 3 solutions modulo 15: 3, 8, and 13. We can write the solution: \begin{equation\*} x \equiv 3 \pmod{15}; \~~ x \equiv 8 \pmod{15}; \~~x \equiv 13 \pmod{15}. \end{equation\*}

3. First, reduce modulo 14: \begin{equation\*} 20x \equiv 23 \pmod{14} \end{equation\*} \begin{equation\*} 6x \equiv 9 \pmod{14}. \end{equation\*} We could now divide both sides by 3, or try to increase 9 by a multiple of 14 to get a multiple of 6. If we divide by 3, we get, \begin{equation\*} 2x \equiv 3 \pmod{14}. \end{equation\*} Now try adding multiples of 14 to 3, in hopes of getting a number we can divide by 2. This will not work! Every time we add 14 to the right side, the result will still be odd. We will never get an even number, so we will never be able to divide by 2. Thus there are no solutions to the congruence.

The last congruence above illustrates the way in which congruences might not have solutions. We could have seen this immediately in fact. Look at the original congruence:

\begin{equation\*} 20x \equiv 23 \pmod{14}. \end{equation\*}

If we write this as an equation, we get

\begin{equation\*} 20x = 23 + 14k, \end{equation\*}

or equivalently \\20x - 14k = 23\text{.}\\ We can easily see there will be no solution to this equation in integers. The left-hand side will always be even, but the right-hand side is odd. A similar problem would occur if the right-hand side was divisible by *any* number the left-hand side was not.

So in general, given the congruence

\begin{equation\*} ax \equiv b \pmod{n}, \end{equation\*}

if \\a\\ and \\n\\ are divisible by a number which \\b\\ is not divisible by, then there will be no solutions. In fact, we really only need to check one divisor of \\a\\ and \\n\text{:}\\ the greatest common divisor. Thus, a more compact way to say this is:

Congruences with no solutions

If \\\gcd(a,n) \nmid b\text{,}\\ then \\ax \equiv b \pmod{n}\\ has no solutions.

Solving Linear Diophantine Equations

Discrete math deals with whole numbers of things. So when we want to solve equations, we usually are looking for *integer* solutions. Equations which are intended to only have integer solutions were first studied by in the third century by the Greek mathematician Diophantus of Alexandria, and as such are called *Diophantine equations*. Probably the most famous example of a Diophantine equation is \\a^2 + b^2 = c^2\text{.}\\ The integer solutions to this equation are called *Pythagorean triples*. In general, solving Diophantine equations is hard (in fact, there is provably no general algorithm for deciding whether a Diophantine equation has a solution, a result known as Matiyasevich's Theorem). We will restrict our focus to *linear* Diophantine equations, which are considerably easier to work with.

Diophantine Equations

An equation in two or more variables is called a Diophantine equation if only integers solutions are of interest. A linear Diophantine equation takes the form \\a_1x_1 + a_2x_x + \cdots + a_nx_n = b\\ for constants \\a_1,\ldots, a_n, b\text{.}\\

A solution to a Diophantine equation is a solution to the equation consisting only of integers.

We have the tools we need to solve linear Diophantine equations. We will consider, as a main example, the equation

\begin{equation\*} 51x + 87y = 123. \end{equation\*}

The general strategy will be to convert the equation to a congruence, then solve that congruence.⁴This is certainly not the only way to proceed. A more common technique would be to apply the *Euclidean algorithm*. Our way can be a little faster, and is presented here primarily for variety. Let's work this particular example to see how this might go.

First, check if perhaps there are no solutions because a divisor of \\51\\ and \\87\\ is not a divisor of \\123\text{.}\\ Really, we just need to check whether \\\gcd(51, 87) \mid 123\text{.}\\ This greatest common divisor is 3, and yes \\3 \mid 123\text{.}\\ At this point, we might as well factor out this greatest common divisor. So instead, we will solve:

\begin{equation\*} 17x + 29y = 41. \end{equation\*}

Now observe that if there are going to be solutions, then for those values of \\x\\ and \\y\text{,}\\ the two sides of the equation must have the same remainder as each other, no matter what we divide by. In particular, if we divide both sides by 17, we must get the same remainder. Thus we can safely write

\begin{equation\*} 17x + 29y \equiv 41 \pmod{17}. \end{equation\*}

We choose 17 because \\17x\\ will have remainder 0. This will allow us to reduce the congruence to just one variable. We could have also moved to a congruence modulo 29, although there is usually a good reason to select the smaller choice, as this will allow us to reduce the other coefficient. In our case, we reduce the congruence as follows:

\begin{equation\*} \begin{aligned}17x + 29y \amp \equiv 41 \pmod{17} \\ 0x + 12y \amp \equiv 7 \pmod{17} \\ 12 y \amp \equiv 24 \pmod{17} \\ y \amp \equiv 2 \pmod{17}. \end{aligned} \end{equation\*}

Now at this point we know \\y = 2 + 17k\\ will work for any integer \\k\text{.}\\ If we haven't made a mistake, we should be able to plug this back into our original Diophantine equation to find \\x\text{:}\\

\begin{equation\*} \begin{aligned}17x + 29(2 + 17k) \amp = 41\\ 17x \amp = -17 - 29\cdot 17k\\ x \amp = -1-29k. \end{aligned} \end{equation\*}

We have now found all solutions to the Diophantine equation. For each \\k\text{,}\\ \\x = -1-29k\\ and \\y = 2 + 17k\\ will satisfy the equation. We could check this for a few cases. If \\k = 0\text{,}\\ the solution is \$-1,2)\text{,}\\ and yes, \\-17 + 2\cdot 29 = 41\text{.}\\ If \\k = 3\text{,}\\ the solution is \$-88, 53)\text{.}\\ If \\k = -2\text{,}\\ we get \$57, -32)\text{.}\\

To summarize this process, to solve \\ax + by = c\text{,}\\ we,

1. Divide both sides of the equation by \\\gcd(a,b)\\ (if this does not leave the right-hand side as an integer, there are no solutions). Let's assume that \\ax + by = c\\ has already been reduced in this way.

2. Pick the smaller of \\a\\ and \\b\\ (here, assume it is \\b\$, and convert to a congruence modulo \\b\text{:}\\ \begin{equation\*} ax + by \equiv c \pmod{b}. \end{equation\*} This will reduce to a congruence with one variable, \\x\text{:}\\ \begin{equation\*} ax \equiv c \pmod{b}. \end{equation\*}

3. Solve the congruence as we did in the previous section. Write your solution as an equation, such as, \begin{equation\*} x = n + kb \end{equation\*}

4. Plug this into the original Diophantine equation, and solve for \\y\text{.}\\

5. If we want to know solutions in a particular range (for example, \\0 \le x, y \le 20\$, pick different values of \\k\\ until you have all required solutions.

Here is another example:

Example \\\PageIndex{7}\\

How can you make \$6.37 using just 5-cent and 8-cent stamps? What is the smallest and largest number of stamps you could use?

Solution

First, we need a Diophantine equation. We will work in numbers of cents. Let \\x\\ be the number of \\5\\-cent stamps, and \\y\\ be the number of 8-cent stamps. We have:

\begin{equation\*} 5x + 8y = 637. \end{equation\*}

Convert to a congruence and solve:

\begin{equation\*} \begin{aligned}8y \amp \equiv 367 \pmod{5}\\ 3y \amp \equiv 2 \pmod 5\\ 3y \amp \equiv 12 \pmod 5\\ y \amp \equiv 4 \pmod 5.\\ \end{aligned} \end{equation\*}

Thus \\y = 4 + 5k\text{.}\\ Then \\5x + 8(4+5k) = 637\text{,}\\ so \\x = 121 - 8k\text{.}\\

This says that one way to make \$6.37 is to take 121 of the 5-cent stamps and 4 of the 8-cent stamps. To find the smallest and largest number of stamps, try different values of \\k\text{.}\\

| \\k\\ | \$x,y)\\ | Stamps |

|--------|-----------|--------------|

| -1 | (129, -1) | not possible |

| 0 | (121, 4) | 125 |

| 1 | (113, 9) | 122 |

| 2 | (105, 13) | 119 |

| \vdots | \vdots | \vdots |

This is no surprise. Having the most stamps means we have as many 5-cent stamps as possible, and to get the smallest number of stamps would require have the least number of 5-cent stamps. To minimize the number of 5-cent stamps, we want to pick \\k\\ so that \\121-8k\\ is as small as possible (but still positive). When \\k = 15\text{,}\\ we have \\x = 1\\ and \\y = 79\text{.}\\

Therefore, to make \$6.37, you can us as few as 80 stamps (1 5-cent stamp and 79 8-cent stamps) or as many as 125 stamps (121 5-cent stamps and 4 8-cent stamps).​​​​​​​

Using this method, as long as you can solve linear congruences in one variable, you can solve linear Diophantine equations of two variables. There are times though that solving the linear congruence is a lot of work. For example, suppose you need to solve,

\begin{equation\*} 13x \equiv 6 \pmod{51}. \end{equation\*}

You *could* keep adding 51 to the right side until you get a multiple of 13: You would get 57, 108, 159, 210, 261, 312, and 312 is the first of these that is divisible by 13. This works, but is really too much work. Instead we could convert *back* to a Diophantine equation:

\begin{equation\*} 13x = 6 + 51k \end{equation\*}

Now solve *this* like we have in this section. Write it as a congruence modulo 13:

\begin{equation\*} \begin{aligned}0 \amp \equiv 6 + 51k \pmod{13}\\ -12k \amp \equiv 6 \pmod{13}\\ 2k \amp \equiv -1 \pmod{13}\\ 2k \amp \equiv 12 \pmod{13}\\ k \amp \equiv 6 \pmod{13} \end{aligned} \end{equation\*}

so \\k = 6 + 13j\text{.}\\ Now go back and figure out \\x\text{:}\\

\begin{equation\*} \begin{aligned}13x \amp = 6 + 51(6+13j)\\ x \amp = 24 + 51j. \end{aligned} \end{equation\*}

Of course you could do this switching back and forth between congruences and Diophantine equations as many times as you like. If you *only* used this technique, you would essentially replicate the Euclidean algorithm, a more standard way to solve Diophantine equations.

---

5_E_3A_Additional_Topics__Exercises_

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/5%3A_Additional_Topics/5.E%3A_Additional_Topics_(Exercises)

Skip to main content

\\ \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.

---

Acknowledgements

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/00%3A_Front_Matter/Acknowledgements

Skip to main content

This book would not exist if not for “Discrete and Combinatorial Mathematics” by Richard Grassl and Tabitha Mingus. It is the book I learned discrete math out of, and taught out of the semester before I began writing this text. I wanted to maintain the inquiry based feel of their book but update, expand and rearrange some of the material. Some of the best exposition and exercises here were graciously donated from this source.

Thanks to Alees Seehausen who co-taught the Discrete Mathematics course with me in 2015 and helped develop many of the *Investigate!* activities and other problems currently used in the text. She also offered many suggestions for improvement of the expository text, for which I am quite grateful. Thanks also to Katie Morrison and Nate Eldredge for their suggestions after using parts of this text in their class.

While odds are that there are still errors and typos in the current book, there are many fewer thanks to the work of Michelle Morgan over the summer of 2016.

The book is now available in an interactive online format, and this is entirely thanks to the work of Rob Beezer and David Farmer along with the rest of the participants of the mathbook-xml-support group. Thanks for

Finally, a thank you to the numerous students who have pointed out typos and made suggestions over the years and a thanks in advance to those who will do so in the future.

---

How_to_use_this_book

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/00%3A_Front_Matter/How_to_use_this_book

Skip to main content

In addition to expository text, this book has a few features designed to encourage you to interact with the mathematics.

Investigate! activities

Sprinkled throughout the sections (usually at the very beginning of a topic) you will find activities designed to get you acquainted with the topic soon to be discussed. These are similar (sometimes identical) to group activities I give students to introduce material. You really should spend some time thinking about, or even working through, these problems before reading the section. By priming yourself to the types of issues involved in the material you are about to read, you will better understand what is to come. There are no solutions provided for these problems, but don't worry if you can't solve them or are not confident in your answers. My hope is that you will take this frustration with you while you read the proceeding section. By the time you are done with the section, things should be much clearer.

Examples

I have tried to include the “correct” number of examples. For those examples which include *problems*, full solutions are included. Before reading the solution, try to at least have an understanding of what the problem is asking. Unlike some textbooks, the examples are not meant to be all inclusive for problems you will see in the exercises. They should not be used as a blueprint for solving other problems. Instead, use the examples to deepen our understanding of the concepts and techniques discussed in each section. Then use this understanding to solve the exercises at the end of each section.

Exercises

You get good at math through practice. Each section concludes with a small number of exercises meant to solidify concepts and basic skills presented in that section. At the end of each chapter, a larger collection of similar exercises is included (as a sort of “chapter review”) which might bridge material of different sections in that chapter. Many exercise have a hint, answer or full solution (which in the pdf version of the text can be found by clicking on the exercises number—clicking on the solution number will bring you back to the exercise). Readers are encouraged to try these exercises before looking at the solution. When I teach with this book, I assign these exercises as practice and then use them, or similar problems, on quizzes and exams. There are also problems without answers to challenge yourself (or to be assigned as homework).

---