Selected Solutions

Appendix B Selected Solutions

1 Logic and Proofs
1.1 Mathematical Statements
Practice Problems

7.

Solution.

$P(11)$ is the statement “$16\cdot 11 + 1$ is even”, which is false. Thus the statement $\forall x P(x)$ is false (for example, 11 is a counterexample). However, we cannot tell anything about $\exists x P(x)$ since we do not know the truth value of $P(x)$ for other elements of the domain of discourse. In this case, $\exists x P(x)$ happens to be true (since $P(1)$ is true, for example).

🔗

8.

Solution.

$P(13)$ is the statement “$9\cdot 13 + 1$ is even”, which is true. Thus the statement $\exists x P(x)$ is true (for example, 13 is such an $x$). However, we cannot tell anything about $\forall x P(x)$ since we do not know the truth value of $P(x)$ for all elements of the domain of discourse. In this case, $\forall x P(x)$ happens to be false (since $P(4)$ is false, for example).

🔗

Additional Exercises

1.

Solution.

$P \wedge Q\text{.}$

🔗
$P \imp \neg Q\text{.}$

🔗
Jack passed math or Jill passed math (or both).
🔗

🔗
If Jack and Jill did not both pass math, then Jill did.
🔗

🔗
1. Nothing else.
  
  🔗
2. Jack did not pass math either.
  
  🔗
🔗
🔗

🔗

2.

Solution.

$\neg \exists x (E(x) \wedge O(x))\text{.}$

🔗
$\forall x (E(x) \imp O(x+1))\text{.}$

🔗
$\exists x(P(x) \wedge E(x))$ (where $P(x)$ means “$x$ is prime”).

🔗
$\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\text{.}$

🔗
$\forall x \neg \exists y (x \lt y \lt x+1)\text{.}$

🔗

🔗

1.2 Implications
Practice Problems

1.

Solution.

The main thing to realize is that we do not know the colors of these two shapes, but we do know that we are in one of three cases: We could have a purple diamond and blue circle. We could have a diamond that was not purple but a blue circle. Or we could have a diamond that was not purple and a circle that was not blue. The case in which the diamond is purple but the circle is not blue cannot occur, as that would make the statement false.

🔗

2.

Solution.

The only way for an implication $P\rightarrow Q$ to be true but its converse to be false is for $Q$ to be true and $P$ to be false. Thus we know that square is purple and that circle is not orange.

🔗

3.

Solution.

The converse is "If I will give you a cow, then you will give me magic beans." The contrapositive is "If I will not give you a cow, then you will not give me magic beans." All the other statements are neither the converse nor contrapositive.

🔗

Additional Exercises

1.

Solution.

Any even number plus 2 is an even number.
🔗

🔗
For any $x$ there is a $y$ such that $\sin(x) = y\text{.}$ In other words, every number $x$ is in the domain of sine.
🔗

🔗
For every $y$ there is an $x$ such that $\sin(x) = y\text{.}$ In other words, every number $y$ is in the range of sine (which is false).
🔗

🔗
For any numbers, if the cubes of two numbers are equal, then the numbers are equal.
🔗

🔗

🔗

3.

Solution.

If you have lost weight, then you exercised.
🔗

🔗
If you exercise, then you will lose weight.
🔗

🔗
If you are American, then you are patriotic.
🔗

🔗
If you are patriotic, then you are American.
🔗

🔗
If a number is rational, then it is real.
🔗

🔗
If a number is not even, then it is prime. (Or the contrapositive: If a number is not prime, then it is even.)
🔗

🔗
If the Broncos don’t win the Super Bowl, then they didn’t play in the Super Bowl. Alternatively, if the Broncos play in the Super Bowl, then they will win the Super Bowl.
🔗

🔗

🔗

5.

Solution.

It is true that in order for a function to be differentiable at a point $c\text{,}$ it is necessary for the function to be continuous at $c\text{.}$ However, it is not necessary that a function be differentiable at $c$ for it to be continuous at $c\text{.}$

🔗

It is true that to be continuous at a point $c\text{,}$ it is sufficient that the function be differentiable at $c\text{.}$ However, it is not the case that being continuous at $c$ is sufficient for a function to be differentiable at $c\text{.}$

🔗

1.3 Rules of Logic
Practice Problems

1.

Solution.

If you think about what this statement is saying, it makes sense that it is a tautology (that it is true in every case). The complete truth table is:

🔗

$P$	$Q$	$P \wedge Q$	$P \vee Q$	$(P \wedge Q) \rightarrow (P \vee Q))$
T	T	T	T	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	T

🔗

2.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$\neg Q$	$Q \rightarrow P$	$\neg Q \vee (Q \rightarrow P))$
T	T	F	T	T
T	F	T	T	T
F	T	F	F	F
F	F	T	T	T

If this statement is false, we must be in the third row, making $P$ false and $Q$ true.

🔗

3.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$R$	$\neg P$	$Q \rightarrow R$	$\neg P \wedge (Q \rightarrow R)$
T	T	T	F	T	F
T	T	F	F	F	F
T	F	T	F	T	F
T	F	F	F	T	F
F	T	T	T	T	T
F	T	F	T	F	F
F	F	T	T	T	T
F	F	F	T	T	T

🔗

4.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$R$	$P \rightarrow (Q \vee R)$	$(P \rightarrow Q) \vee (P\rightarrow R)$
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	T	T
F	T	F	T	T
F	F	T	T	T
F	F	F	T	T

Since the two columns are identical, the statements are logically equivalent.

🔗

5.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$P \rightarrow Q$	$\neg Q$	$\neg P$
T	T	T	F	F
T	F	F	T	F
F	T	T	F	T
F	F	T	T	T

There is only one row in which both premises are true (row 4). In this row, the conclusion is also true. Thus the deduction rule is valid.

🔗

6.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$R$	$P \rightarrow (Q \vee R)$	$\neg(P \rightarrow Q)$
T	T	T	T	F
T	T	F	T	F
T	F	T	T	T
T	F	F	F	T
F	T	T	T	F
F	T	F	T	F
F	F	T	T	F
F	F	F	T	F

There is only one row in which both premises are true (row 3). In this row, the conclusion is also true, so the deduction rule is valid.

🔗

7.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$R$	$(P \wedge Q) \rightarrow R$	$\neg P \vee \neg Q$	$\neg R$
T	T	T	T	F	F
T	T	F	F	F	T
T	F	T	T	T	F
T	F	F	T	T	T
F	T	T	T	T	F
F	T	F	T	T	T
F	F	T	T	T	F
F	F	F	T	T	T

In rows 3, 5, and 7 both of the premises are true, but the conclusion is false. Thus the deduction rule is not valid.

🔗

8.

Solution.

The complete truth table is:

🔗

$P$	$Q$	$R$	$P \rightarrow Q$	$P \wedge \neg Q$
T	T	T	T	F
T	T	F	T	F
T	F	T	F	T
T	F	F	F	T
F	T	T	T	F
F	T	F	T	F
F	F	T	T	F
F	F	F	T	F

There is no row in which both premises are true (indeed, these are contradictory premises; the second is the negation of the first). Thus for every row in which both premises are true (i.e., no row), the conclusion is also true. Therefore the deduction rule is valid. (This is an example of how everything follows from a contradiction.)

🔗

Additional Exercises

3.

Solution.

$P\text{:}$ It’s your birthday; $Q\text{:}$ There will be cake. $(P \vee Q) \imp Q$

🔗
Hint: You should get three T’s and one F.
🔗

🔗
Only that there will be cake.
🔗

🔗
It’s NOT your birthday!
🔗

🔗
It’s your birthday, but the cake is a lie.
🔗

🔗

🔗

5.

Solution.

Make a truth table for each and compare. The statements are logically equivalent.

🔗

6.

Solution.

$P \wedge Q\text{.}$

🔗
$(\neg P \vee \neg R) \imp (Q \vee \neg R)$ or, replacing the implication with a disjunction first: $(P \wedge Q) \vee (Q \vee \neg R)\text{.}$

🔗
$(P \wedge Q) \wedge (R \wedge \neg R)\text{.}$ This is necessarily false, so it is also equivalent to $P \wedge \neg P\text{.}$
🔗

🔗
Either Sam is a woman and Chris is a man, or Chris is a woman.
🔗

🔗

🔗

16.

Solution.

$\forall x \exists y (O(x) \wedge \neg E(y))\text{.}$

🔗
$\exists x \forall y (x \ge y \vee \forall z (x \ge z \wedge y \ge z))\text{.}$

🔗
There is a number $n$ for which every other number is strictly greater than $n\text{.}$
🔗

🔗
There is a number $n$ which is not between any other two numbers.
🔗

🔗

🔗

1.4 Proofs
Additional Exercises

1.

Solution.

The claim that $\forall x P(x)$ means that $P(n)$ is true no matter what $n$ you consider in the domain of discourse. Thus the only way to prove that $\forall x P(x)$ is true is to check or otherwise argue that $P(n)$ is true for all $n$ in the domain.
🔗

🔗
To prove $\forall x P(x)$ is false all you need is one example of an element in the domain for which $P(n)$ is false. This is often called a counterexample.
🔗

🔗
We are simply claiming that there is some element $n$ in the domain of discourse for which $P(n)$ is true. If you can find one such element, you have verified the claim.
🔗

🔗
Here we are claiming that no element we find will make $P(n)$ true. The only way to be sure of this is to verify that every element of the domain makes $P(n)$ false. Note that the level of proof needed for this statement is the same as to prove that $\forall x P(x)$ is true.
🔗

🔗

🔗

2.

Solution.

For all integers $a$ and $b\text{,}$ if $a$ or $b$ is not even, then $a+b$ is not even.
🔗

🔗
For all integers $a$ and $b\text{,}$ if $a$ and $b$ are even, then $a+b$ is even.
🔗

🔗
There are numbers $a$ and $b$ such that $a+b$ is even but $a$ and $b$ are not both even.
🔗

🔗
False. For example, $a = 3$ and $b = 5\text{.}$ $a+b = 8\text{,}$ but neither $a$ nor $b$ is even.
🔗

🔗
False, since it is equivalent to the original statement.
🔗

🔗
True. Let $a$ and $b$ be integers. Assume both are even. Then $a = 2k$ and $b = 2j$ for some integers $k$ and $j\text{.}$ But then $a+b = 2k + 2j = 2(k+j)\text{,}$ which is even.
🔗

🔗
True, since the statement is false.
🔗

🔗

🔗

3.

Solution.

Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6y + 3\text{.}$ End of proof: … this is a contradiction, so there are no such integers.
🔗

🔗
Direct proof. Start of proof: Let $n$ be an integer. Assume $n$ is a multiple of 3. End of proof: Therefore $n$ can be written as the sum of consecutive integers.
🔗

🔗
Proof by contrapositive. Start of proof: Let $a$ and $b$ be integers. Assume that $a$ and $b$ are even. End of proof: Therefore $a^2 + b^2$ is even.
🔗

🔗

🔗

4.

Solution.

Direct proof.
Proof.

Let $n$ be an integer. Assume $n$ is even. Then $n = 2k$ for some integer $k\text{.}$ Thus $8n = 16k = 2(8k)\text{.}$ Therefore $8n$ is even.
🔗

🔗
🔗

🔗
The converse is false. That is, there is an integer $n$ such that $8n$ is even but $n$ is odd. For example, consider $n = 3\text{.}$ Then $8n = 24$ which is even, but $n = 3$ is odd.
🔗

🔗

🔗

5.

Solution.

This is an example of the pigeonhole principle. We can prove it by contrapositive.
🔗

Proof.

Suppose that each number only came up 6 or fewer times. So there are at most six 1’s, six 2’s, and so on. That’s a total of 36 dice, so you must not have rolled all 40 dice.
🔗

🔗
🔗
We can have 9 dice without any four matching or any four being all different: three 1’s, three 2’s, three 3’s. We will prove that whenever you roll 10 dice, you will always get four matching or all being different.
🔗

Proof.

Suppose you roll 10 dice, but that there are NOT four matching rolls. This means that at most there are three of any given value. If we only had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 dice that are all different.
🔗

🔗
🔗

🔗

1.6 Chapter Summary

Chapter Review

1.6.1.

Solution.

$P$	$Q$	$R$	$\neg P \imp (Q \wedge R)$
T	T	T	T
T	T	F	T
T	F	T	T
T	F	F	T
F	T	T	T
F	T	F	F
F	F	T	F
F	F	F	F

🔗

1.6.2.

Solution.

Peter is not tall, and Robert is not skinny. You must be in row 6 in the truth table above.

🔗

1.6.3.

Solution.

Yes. To see this, make a truth table for each statement and compare.

🔗

1.6.4.

Solution.

Make a truth table that includes all three statements in the argument:

🔗

$P$	$Q$	$R$	$P \imp Q$	$P \imp R$	$P \imp (Q \wedge R)$
T	T	T	T	T	T
T	T	F	T	F	F
T	F	T	F	T	F
T	F	F	F	F	F
F	T	T	T	T	T
F	T	F	T	T	T
F	F	T	T	T	T
F	F	F	T	T	T

Notice that in every row for which both $P \imp Q$ and $P \imp R$ is true, so is $P \imp (Q \wedge R)\text{.}$ Therefore, whenever the premises of the argument are true, so is the conclusion. In other words, the deduction rule is valid.

🔗

1.6.5.

Solution.

Negation: The power goes off, and the food does not spoil.
🔗

Converse: If the food spoils, then the power went off.
🔗

Contrapositive: If the food does not spoil, then the power did not go off.
🔗

🔗
Negation: The door is closed, and the light is on.
🔗

Converse: If the light is off, then the door is closed.
🔗

Contrapositive: If the light is on, then the door is open.
🔗

🔗
Negation: $\exists x (x \lt 1 \wedge x^2 \ge 1)$
🔗

Converse: $\forall x( x^2 \lt 1 \imp x \lt 1)$
🔗

Contrapositive: $\forall x (x^2 \ge 1 \imp x \ge 1)\text{.}$
🔗

🔗
Negation: There is a natural number $n$ which is prime but not solitary.
🔗

Converse: For all natural numbers $n\text{,}$ if $n$ is solitary, then $n$ is prime.
🔗

Contrapositive: For all natural numbers $n\text{,}$ if $n$ is not solitary, then $n$ is not prime.
🔗

🔗
Negation: There is a function which is differentiable and not continuous.
🔗

Converse: For all functions $f\text{,}$ if $f$ is continuous, then $f$ is differentiable.
🔗

Contrapositive: For all functions $f\text{,}$ if $f$ is not continuous then $f$ is not differentiable.
🔗

🔗
Negation: There are integers $a$ and $b$ for which $a\cdot b$ is even but $a$ or $b$ is odd.
🔗

Converse: For all integers $a$ and $b\text{,}$ if $a$ and $b$ are even, then $ab$ is even.
🔗

Contrapositive: For all integers $a$ and $b\text{,}$ if $a$ or $b$ is odd, then $ab$ is odd.
🔗

🔗
Negation: There are integers $x$ and $y$ such that for every integer $n\text{,}$ $x \gt 0$ and $nx \le y\text{.}$
🔗

Converse: For every integer $x$ and every integer $y$ there is an integer $n$ such that if $nx > y\text{,}$ then $x > 0\text{.}$
🔗

Contrapositive: For every integer $x$ and every integer $y$ there is an integer $n$ such that if $nx \le y\text{,}$ then $x \le 0\text{.}$
🔗

🔗
Negation: There are real numbers $x$ and $y$ such that $xy = 0\text{,}$ but $x \ne 0$ and $y \ne 0\text{.}$
🔗

Converse: For all real numbers $x$ and $y\text{,}$ if $x = 0$ or $y = 0\text{,}$ then $xy = 0$
🔗

Contrapositive: For all real numbers $x$ and $y\text{,}$ if $x \ne 0$ and $y \ne 0\text{,}$ then $xy \ne 0\text{.}$
🔗

🔗
Negation: There is at least one student in Math 228 who does not understand implications but will still pass the exam.
🔗

Converse: For every student in Math 228, if they fail the exam, then they did not understand implications.
🔗

Contrapositive: For every student in Math 228, if they pass the exam, then they understood implications.
🔗

🔗

🔗

1.6.6.

Solution.

The statement is true. If $n$ is an even integer less than or equal to 7, then the only way it could not be negative is if $n$ was equal to 0, 2, 4, or 6.
🔗

🔗
There is an integer $n$ such that $n$ is even and $n \le 7\text{,}$ but $n$ is not negative and $n \not\in \{0,2,4,6\}\text{.}$ This is false, since the original statement is true.
🔗

🔗
For all integers $n\text{,}$ if $n$ is not negative and $n \not\in\{0,2,4,6\}\text{,}$ then $n$ is odd or $n > 7\text{.}$ This is true, since the contrapositive is equivalent to the original statement (which is true).
🔗

🔗
For all integers $n\text{,}$ if $n$ is negative or $n \in \{0,2,4,6\}\text{,}$ then $n$ is even and $n \le 7\text{.}$ This is false. $n = -3$ is a counterexample.
🔗

🔗

🔗

1.6.7.

Solution.

For any number $x\text{,}$ if it is the case that adding any number to $x$ gives that number back, then multiplying any number by $x$ will give 0. This is true (of the integers or the reals). The “if” part only holds if $x = 0\text{,}$ and in that case, anything times $x$ will be 0.
🔗

🔗
The converse in words is this: For any number $x\text{,}$ if everything times $x$ is zero, then everything added to $x$ gives itself. Or in symbols: $\forall x (\forall z (x \cdot z = 0) \imp \forall y (x + y = y))\text{.}$ The converse is true: The only number which when multiplied by any other number gives 0 is $x = 0\text{.}$ And if $x = 0\text{,}$ then $x + y = y\text{.}$
🔗

🔗
The contrapositive in words is: For any number $x\text{,}$ if there is some number which when multiplied by $x$ does not give zero, then there is some number which when added to $x$ does not give that number. In symbols: $\forall x (\exists z (x\cdot z \ne 0) \imp \exists y (x + y \ne y))\text{.}$ We know the contrapositive must be true because the original implication is true.
🔗

🔗
The negation: There is a number $x$ such that any number added to $x$ gives the number back again, but there is a number you can multiply $x$ by and not get 0. In symbols: $\exists x (\forall y (x + y = y) \wedge \exists z (x \cdot z \ne 0))\text{.}$ Of course since the original implication is true, the negation is false.
🔗

🔗

🔗

1.6.8.

Solution.

$(\neg P \vee Q) \wedge (\neg R \vee (P \wedge \neg R))\text{.}$

🔗
$\forall x \forall y \forall z (z = x+y \wedge \forall w (x-y \ne w))\text{.}$

🔗

🔗

1.6.9.

Solution.

Direct proof.
Proof.

Let $n$ be an integer. Assume $n$ is odd. So $n = 2k+1$ for some integer $k\text{.}$ Then

\begin{equation*} 7n = 7(2k+1) = 14k + 7 = 2(7k +3) + 1\text{.} \end{equation*}

🔗

Since $7k + 3$ is an integer, we see that $7n$ is odd.
🔗

🔗
🔗

🔗
The converse is: For all integers $n\text{,}$ if $7n$ is odd, then $n$ is odd. We will prove this by contrapositive.
Proof.

Let $n$ be an integer. Assume $n$ is not odd. Then $n = 2k$ for some integer $k\text{.}$ So $7n = 14k = 2(7k)$ which is to say $7n$ is even. Therefore $7n$ is not odd.
🔗

🔗
🔗

🔗

🔗

1.6.10.

Solution.

Suppose you only had 5 coins of each denomination. This means you have 5 pennies, 5 nickels, 5 dimes, and 5 quarters. This is a total of 20 coins. But you have more than 20 coins, so you must have more than 5 of at least one type.
🔗

🔗
Suppose you have 22 coins, including $2k$ nickels, $2j$ dimes, and $2l$ quarters (so an even number of each of these three types of coins). The number of pennies you have will then be

\begin{equation*} 22 - 2k - 2j - 2l = 2(11-k-j-l)\text{.} \end{equation*}

But this says that the number of pennies is also even (it is 2 times an integer). Thus we have established the contrapositive of the statement, “If you have an odd number of pennies, then you have an odd number of at least one other coin type.”

🔗

🔗
You need 10 coins. You could have 3 pennies, 3 nickels, and 3 dimes. The 10th coin must either be a quarter, giving you 4 coins that are all different, or else a 4th penny, nickel, or dime. To prove this, assume you don’t have 4 coins that are all the same or all different. In particular, this says that you only have 3 coin types, and each of those types can only contain 3 coins, for a total of 9 coins, which is less than 10.
🔗

🔗

🔗

2 Graph Theory
2.1 Problems and Definitions
Practice Problems

4.

Solution.

By the handshake lemma, the number of edges is twice the sum of the degrees of vertices in the graph.

🔗

The sum of the degrees is $8+8+8+8+8+7+7+7+7 = {68}\text{,}$ so there are ${34}$ edges.

🔗

Additional Exercises

1.

Solution.

This is asking for the number of edges in $K_{10}\text{.}$ Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is $90\text{.}$ However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.

🔗

2.

Solution.

It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph $C_5$). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.

🔗

4.

Solution.

The graphs are not equal. For example, graph 1 has an edge $\{a,b\}\text{,}$ but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is $f:G_1 \to G_2$ defined by $f(a) = d\text{,}$ $f(b) = c\text{,}$ $f(c) = e\text{,}$ $f(d) = b\text{,}$ $f(e) = a\text{.}$

🔗

9.

Solution.

For example:
🔗

$A graph consisting of a vertex with three edges connecting it to three vertices in a row above it.$

$A graph consisting of four vertices arranged in a V. The left point of the V connects to the bottom corner of the V. That vertex is connected to a vertex half way up the right side of the V, which is then connected to the vertex at the right point of the V.$

🔗
This is not possible if we require the graphs to be connected. If not, we could take $C_8$ as one graph and two copies of $C_4$ as the other.
🔗

🔗
Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph $K_5\text{.}$
🔗

🔗
This is not possible. In fact, there is not even one graph with this property (such a graph would have $5\cdot 3/2 = 7.5$ edges).
🔗

🔗

🔗

10.

Solution.

False.
🔗

🔗
True.
🔗

🔗
True.
🔗

🔗
False.
🔗

🔗

🔗

2.2 Trees
Practice Problems

3.

Solution.

Every spanning tree must still contain 12 vertices. Since it is a tree, it will have $12-1 = 11$ edges.

🔗

Thus we must remove 6 edges to get a spanning tree.

🔗

5.

Solution.

Let $x$ be the number of leaves. Then the sum of degrees will be $x + 10 +7 + 4 + 2 = x + 23\text{.}$ This is twice the number of edges. Since the number of edges is one less than the number of vertices, which is $x + 4\text{,}$ we also know that the number of edges is $x+3\text{.}$

🔗

Thus we have $2(x+3) = x+23\text{.}$ Solving for $x$ gives $x = 17\text{.}$

🔗

Additional Exercises

1.

Solution.

This is not a tree since it contains a cycle. Note also that there are too many edges to be a tree, since we know that all trees with $v$ vertices have $v-1$ edges.
🔗

🔗
This is a tree since it is connected and contains no cycles (which you can see by drawing the graph). All paths are trees.
🔗

🔗
This is a tree since it is connected and contains no cycles (draw the graph). All stars are trees.
🔗

🔗
This is a not a tree since it is not connected. Note that there are not enough edges to be a tree.
🔗

🔗

🔗

2.

Solution.

This must be the degree sequence for a tree. This is because the vertex of degree 4 must be adjacent to the four vertices of degree 1 (there are no other vertices for it to be adjacent to), and thus we get a star.
🔗

🔗
This cannot be a tree. Each degree 3 vertex is adjacent to all but one of the vertices in the graph. Thus each must be adjacent to one of the degree 1 vertices (and not the other). That means both degree 3 vertices are adjacent to the degree 2 vertex and to each other, so that means there is a cycle.
🔗

Alternatively, count how many edges there are!
🔗

🔗
This might or might not be a tree. The length 4 path has this degree sequence (this is a tree), but so does the union of a 3-cycle and a length 1 path (which is not connected, so this is not a tree).
🔗

🔗
This cannot be a tree. The sum of the degrees is 28, so there are 14 edges. But there are 14 vertices as well, so we don’t have $v = e+1\text{,}$ meaning this cannot be a tree.
🔗

🔗

🔗

6.

Solution.

Yes. We will prove the contrapositive. Assume $G$ does not contain a cycle. Then $G$ is a tree, so this would have $v = e+1\text{,}$ contrary to stipulation.

🔗

12.

Solution.

No, although there are graphs for which this is true. For example, $K_4$ has a spanning tree that is a path (of three edges) and also a spanning tree that is a star (with center vertex of degree 3).
🔗

🔗
Yes. For a fixed graph, we have a fixed number $v$ of vertices. Any spanning tree of the graph will also have $v$ vertices, and since it is a tree, must have $v-1$ edges.
🔗

🔗
No, although there are graphs for which this is true (note that if all spanning trees are isomorphic, then all spanning trees will have the same number of leaves). Again, $K_4$ is a counterexample. One spanning tree is a path, with only two leaves, and another spanning tree is a star with 3 leaves.
🔗

🔗

🔗

2.3 Planar Graphs
Additional Exercises

1.

Solution.

No. A (connected) planar graph must satisfy Euler’s formula: $v - e + f = 2\text{.}$ Here $v - e + f = 6 - 10 + 5 = 1\text{.}$

🔗

2.

Solution.

$G$ has 10 edges, since $10 = \frac{2+2+3+4+4+5}{2}\text{.}$ It could be planar, and then it would have 6 faces, using Euler’s formula: $6-10+f = 2$ means $f = 6\text{.}$ To make sure that it is actually planar though, we would need to draw a graph with those vertex degrees without edges crossing. This can be done by trial and error (and is possible).

🔗

6.

Solution.

Say the last polyhedron has $n$ edges and also $n$ vertices. The total number of edges the polyhedron has then is $(7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}$ In particular, we know the last face must have an odd number of edges. We also have that $v = 11 \text{.}$ By Euler’s formula, we have $11 - (37+n)/2 + 12 = 2\text{,}$ and solving for $n$ we get $n = 5\text{,}$ so the last face is a pentagon.

🔗

8.

Solution.

Proof.

Suppose there is a graph $G$ with fewest edges that does not satisfy Euler’s formula.

🔗

Note that $G$ cannot be a tree, since for any tree, $v = e+1$ and $f = 1\text{,}$ so $v - e + f = 2\text{.}$ Therefore, $G$ must contain a cycle. Pick any edge $e_0$ that is part of a cycle in $G$ and consider the graph $G' = G-e_0$ that you get by removing just the edge $e_0$ from $G\text{.}$

🔗

Since $G'$ has fewer edges than $G\text{,}$ it must satisfy Euler’s formula. That is, $v' - e' + f' = 2\text{,}$ where $v'\text{,}$ $e'\text{,}$ and $f'$ are the number of vertices, edges, and faces of $G'\text{.}$ Since $G'$ is obtained by removing a single edge from a cycle in $G\text{,}$ we have $v' = v\text{,}$ $e'=e-1\text{,}$ and $f' = f-1\text{.}$ Therefore, $v - (e-1) + (f-1) = 2\text{,}$ so $v - e + f = 2$ as well. This is a contradiction, so no such graph $G$ can exist.

🔗

12.

Solution.

Proof.

We know in any planar graph the number of faces $f$ satisfies $3f \le 2e$ since each face is bounded by at least three edges, but each edge borders two faces. Combine this with Euler’s formula:

\begin{equation*} v - e + f = 2 \end{equation*}

\begin{equation*} v - e + \frac{2e}{3} \ge 2 \end{equation*}

\begin{equation*} 3v - e \ge 6 \end{equation*}

\begin{equation*} 3v - 6 \ge e\text{.} \end{equation*}

🔗

2.4 Euler Trails and Circuits
Additional Exercises

1.

Solution.

This is a question about finding Euler trails. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree, the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

🔗

2.

Solution.

$K_4$ does not have an Euler trail or circuit.

🔗
$K_5$ has an Euler circuit (so also an Euler trail).

🔗
$K_{5,7}$ does not have an Euler trail or circuit.

🔗
$K_{2,7}$ has an Euler trail but not an Euler circuit.

🔗
$C_7$ has an Euler circuit (it is a circuit graph!)

🔗
$P_7$ has an Euler trail but no Euler circuit.

🔗

🔗

8.

Solution.

If we build one bridge, we can have an Euler trail. Two bridges must be built for an Euler circuit.

🔗

$Three dots aligned in a vertical column left of a single dot on the right. Lines connect the dot on the right to each dot on the left. Among the dots on the left, two arced lines connect the bottom dot to the center dot, and two more connect the center dot to the top dot. An additional dashed edge connects the right dot to the top dot and another dashed edge connects the bottom dot to the middle dot in the vertical column.$

🔗

2.5 Coloring
Additional Exercises

1.

Solution.

2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.

🔗

2.

Solution.

For example, $K_6\text{.}$ If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.

🔗

3.

Solution.

The chromatic numbers are 2, 3, 4, 5, and 3 respectively from left to right.

🔗

5.

Solution.

The cube can be represented as a planar graph and colored with two colors as follows:

🔗

$Eight vertices forming a inner and outer square (with edges forming the sides of each square), with edges connecting each inner vertex to its closest outer vertex neighbor. The outer vertices are labeled R, B, R, B (starting at the top left and moving clockwise). The inner vertices are labeled B, R, B, R (starting at the top left and moving clockwise).$

Since it would be impossible to color the vertices with a single color, we see that the cube has chromatic number 2 (it is bipartite).

🔗

9.

Solution.

The wheel graph below has this property. The outside of the wheel forms an odd cycle and so requires 3 colors; the center of the wheel must be a different color from all the outside vertices.

🔗

$Five vertices in a pentagon with a sixth vertex in the center. Edges form the outside of the pentagon, and the center vertex is adjacent to each outside vertex.$

🔗

12.

Solution.

If we drew a graph with each letter representing a vertex and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, $D$ would be adjacent to both $C$ and $E$). By Brooks’ theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph, and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.

🔗

13.

Solution.

🔗

2.7 Matching in Bipartite Graphs

Exercises

2.7.1.

Solution.

The first and third graphs have a matching, shown in bold (there are other matchings as well). The middle graph does not have a matching. If you look at the three circled vertices, you see that they only have two neighbors, which violates the matching condition $\card{N(S)} \ge \card{S}$ (the three circled vertices form the set $S$).

🔗

$A bipartite graph with six vertices, in two sets of three. If we call the top vertices a,b,c, and the bottom vertices 1, 2, 3 (left to right), then the graph has the following edges: (a,1), (a,2), (b,1), (b,3), (c,1), (c,3). The edges (a,2), (b,3), and (c,1) are highlighted bold.$

$A bipartite graph with eight vertices, in two sets of four. If we call the top vertices a,b,c,d and the bottom vertices 1, 2, 3,4 (left to right), then the graph has the following edges: (a,1), (a,3), (a,4) (b,2), (c,1), (c,2), (c,3), (c,4), (d,2). The vertices 1, 3, and 4 are circled.$

$A bipartite graph with ten vertices, in two sets of five. If we call the top vertices a,b,c,d,e and the bottom vertices 1, 2, 3,4,5 (left to right), then the graph has the following edges: (a,1), (a,2), (a,3), (b,1), (b,3), (c,2), (c,4), (d,3), (d,5), (e,3), (e,4), (e,5). Of these, the following edges are highlighted bold: (a,1), (b,3), (c,2), (d,5), (e,4).$

🔗

2.8 Chapter Summary

Chapter Review

2.8.1.

Solution.

The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).

🔗

2.8.2.

Solution.

The first (and third) graphs contain an Euler trail. All the graphs are planar.

🔗

2.8.3.

Solution.

For example, $K_5\text{.}$

🔗

2.8.4.

Solution.

For example, $K_{3,3}\text{.}$

🔗

2.8.5.

Solution.

Yes, the graphs are isomorphic, which you can see by drawing them. One isomorphism is:

\begin{equation*} f = \begin{pmatrix} a \amp b \amp c \amp d \amp e \amp f \amp g \\ u \amp z \amp v \amp x \amp w \amp y \amp t \end{pmatrix}\text{.} \end{equation*}

🔗

🔗
This is easy to do if you draw the picture. Here is such a graph:
🔗

$A tree with a bottom vertex adjacent to each of three vertices in a row above it. Each of these is adjacent to another vertex directly above them.$

Any labeling of this graph will be not isomorphic to $G\text{.}$ For example, we could take $V'' = \{a,b,c,d,e,f,g\}$ and $E'' = \{ab, ac, ad, be, cf, dg\} \text{.}$
🔗

🔗
The degree sequence for $G$ is $(3, 3, 2, 1, 1, 1, 1)\text{.}$
🔗

🔗
In general this should be possible: The degree sequence does not determine the graph’s isomorphism class. However, in this case, I was almost certain this was not possible. That is, until I stumbled up this:
🔗

$A tree with a center bottom vertex adjacent to two vertices above it. Each of these are adjacent to two vertices above them.$

🔗
$G$ is a tree (there are no cycles) and as such is also bipartite.
🔗

🔗
Yes, all trees are planar. You can draw them in the plane without edges crossing.
🔗

🔗
The chromatic number of $G$ is 2. It shouldn’t be hard to give a 2-coloring (for example, color $a, d, e, g$ red and $b, c, f$ blue), but we know that all bipartite graphs have chromatic number 2.
🔗

🔗
It is clear from the drawing that there is no Euler trail, let alone an Euler circuit. Also, since there are more than 2 vertices of odd degree, we know for sure there is no Euler trail.
🔗

🔗

🔗

2.8.6.

Solution.

Yes. According to Euler’s formula it would have 2 faces. It does. The only such graph is $C_{10}\text{.}$

🔗

2.8.7.

Solution.

Only if $n \ge 6$ and is even.
🔗

🔗
None.
🔗

🔗
12. Such a graph would have $\frac{5n}{2}$ edges. If the graph is planar, then $n - \frac{5n}{2} + f = 2$ so there would be $\frac{4+3n}{2}$ faces. Also, we must have $3f \le 2e\text{,}$ since the graph is simple. So we must have $3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}$ Solving for $n$ gives $n \ge 12\text{.}$
🔗

🔗

🔗

2.8.8.

Solution.

There were 24 couples: 6 choices for the girl and 4 choices for the boy.
🔗

🔗
There were 45 couples: ${10 \choose 2}$ since we must choose two of the 10 people to dance together.
🔗

🔗
For part (a), we are counting the number of edges in $K_{4,6}\text{.}$ In part (b) we count the edges of $K_{10}\text{.}$
🔗

🔗

🔗

2.8.9.

Solution.

Yes, as long as $n$ is even. If $n$ were odd, then the corresponding graph would have an odd number of odd degree vertices, which is impossible.

🔗

2.8.10.

Solution.

No. The 9 triangles each contribute 3 edges, and the 6 pentagons contribute 5 edges. This gives a total of 57, which is exactly twice the number of edges, since each edge borders exactly 2 faces. But 57 is odd, so this is impossible.
🔗

🔗
Now adding up all the edges of all the 16 polygons gives a total of 64, meaning there would be 32 edges in the polyhedron. We can then use Euler’s formula $v - e + f = 2$ to deduce that there must be 18 vertices.
🔗

🔗
If you add up all the vertices from each polygon separately, we get a total of 64. This is not divisible by 3, so it cannot be that each vertex belongs to exactly 3 faces. Could they all belong to 4 faces? That would mean there were $64/4 = 16$ vertices, but we know from Euler’s formula that there must be 18 vertices. We can write $64 = 3x + 4y$ and solve for $x$ and $y$ (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note that the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)
🔗

🔗

🔗

2.8.11.

Solution.

No. Every polyhedron can be represented as a planar graph, and the Four Color Theorem says that every planar graph has chromatic number at most 4.

🔗

2.8.12.

Solution.

$K_{n,n}$ has $n^2$ edges. The graph will have an Euler circuit when $n$ is even. The graph will be planar only when $n \lt 3\text{.}$

🔗

2.8.13.

Solution.

$G$ has 8 edges (since the sum of the degrees is 16). If $G$ is planar, then it will have 4 faces (since $6 - 8 + 4 = 2$). $G$ does not have an Euler trail since there are more than 2 vertices of odd degree.

🔗

2.8.14.

Solution.

$7$ colors. Thus $K_7$ is not planar (by the contrapositive of the Four Color Theorem).

🔗

2.8.15.

Solution.

The chromatic number of $K_{3,4}$ is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is not planar, since it contains $K_{3,3}$ as a subgraph.

🔗

2.8.16.

Solution.

We have that $K_{3,4}$ has 7 vertices and 12 edges (each vertex in the group of 3 has degree 4). Then by Euler’s formula we have that $7 - 12 + f = 2\text{,}$ so if the graph were planar, it would have $f = 7$ faces. However, since the girth of the graph is 4 (there are no cycles of length 3), we get that $4f \le 2e\text{.}$ But this would mean that $28 \le 24\text{,}$ a contradiction.

🔗

2.8.17.

Solution.

For all these questions, we are really coloring the vertices of a graph. You get the graph by first drawing a planar representation of the polyhedron and then taking its planar dual: Put a vertex in the center of each face (including the outside), and connect two vertices if their faces share an edge.

Since the planar dual of a dodecahedron contains a 5-wheel, its chromatic number is at least 4. Alternatively, suppose you could color the faces using 3 colors without any two adjacent faces colored the same. Take any face, and color it blue. The 5 pentagons bordering this blue pentagon cannot be colored blue. Color the first one red. Its two neighbors (adjacent to the blue pentagon) get colored green. The remaining 2 cannot be blue or green, but also cannot both be red since they are adjacent to each other. Thus a 4th color is needed.
🔗

🔗
The planar dual of the dodecahedron is itself a planar graph. Thus by the 4-color theorem, it can be colored using only 4 colors without two adjacent vertices (corresponding to the faces of the polyhedron) being colored identically.
🔗

🔗
The cube can be properly 3-colored. Color the “top” and “bottom” red, the “front” and “back” blue, and the “left” and “right” green.
🔗

🔗

🔗

2.8.18.

Solution.

False. To prove this, we can give an example of a pair of graphs with the same chromatic number that are not isomorphic. For example, $K_{3,3}$ and $K_{3,4}$ both have chromatic number 2 but are not isomorphic.
🔗

🔗
False. The previous example does not work, but you can easily draw two trees that have the same number of vertices and edges but are not isomorphic. Since all trees have chromatic number 2, this is a counterexample.
🔗

🔗
True. If there is an isomorphism from $G_1$ to $G_2\text{,}$ then we have a bijection that tells us how to match up vertices between the graph. Any proper vertex coloring of $G_1$ will tell us how to properly color $G_2\text{,}$ simply by coloring $f(v_i)$ the same color as $v_i\text{,}$ for each vertex $v_i \in V\text{.}$ That is, color the vertices in $G_2$ exactly how you color the corresponding vertices in $G_1\text{.}$ Similarly, any proper vertex coloring of $G_2$ corresponds to a proper vertex coloring of $G_1\text{.}$ Thus the smallest number of colors needed to properly color $G_1$ cannot be smaller than the smallest number of colors needed to properly color $G_2\text{,}$ and vice-versa, so the chromatic numbers must be equal.
🔗

🔗

🔗

2.8.19.

Solution.

$G$ has $13$ edges, since we need $7 - e + 8 = 2\text{.}$

🔗

2.8.20.

Solution.

The graph does have an Euler trail, but not an Euler circuit. There are exactly two vertices with odd degree. The path starts at one and ends at the other.
🔗

🔗
The graph is planar. Even though as it is drawn with edges crossing, it is easy to redraw it without edges crossing.
🔗

🔗
The graph is not bipartite (there is an odd cycle), nor complete.
🔗

🔗
The chromatic number of the graph is 3.
🔗

🔗

🔗

2.8.21.

Solution.

False. For example, $K_{3,3}$ is not planar.
🔗

🔗
True. The graph is bipartite, so it is possible to divide the vertices into two groups with no edges between vertices in the same group. Thus we can color all the vertices of one group red and the other group blue.
🔗

🔗
False. $K_{3,3}$ has 6 vertices with degree 3 and so contains no Euler trail.
🔗

🔗
False. $K_{3,3}$ again.
🔗

🔗
False. The sum of the degrees of all vertices is even for all graphs so this property does not imply that the graph is bipartite.
🔗

🔗

🔗

2.8.22.

Solution.

If a graph has an Euler trail, then it is planar.
🔗

🔗
If a graph does not have an Euler trail, then it is not planar.
🔗

🔗
There is a graph which is planar and does not have an Euler trail.
🔗

🔗
Yes. In fact, in this case it is because the original statement is false.
🔗

🔗
False. $K_4$ is planar but does not have an Euler trail.
🔗

🔗
False. $K_5$ has an Euler trail but is not planar.
🔗

🔗

🔗

3 Counting
3.1 Pascal’s Arithmetical Triangle
Practice Problems

7.

Solution.

${12 \choose 5} = {792}$ choices, since you have to select a 5-element subset of the set of 12 toppings.
🔗

🔗
${11 \choose 5} = {462}$ choices, since you must select 5 of the 11 non-green pepper toppings.
🔗

🔗
${11 \choose 4} = {330}$ choices, since you must select 4 of the remaining 11 non-green pepper toppings to have in addition to the green pepper.
🔗

🔗

🔗

Note that ${792} = {462} + {330}$ choices, which makes sense because every 5-topping pizza either has green pepper or does not have green pepper as a topping.

🔗

9.

Solution.

To get an $x^{9}\text{,}$ we must pick 9 of the 17 factors to contribute an $x\text{,}$ leaving the other 8 to contribute a 3. There are ${17 \choose 9}$ ways to select these 9 factors. So the term containing an $x^{9}$ will be ${17 \choose 9}x^{9}3^{8}\text{.}$ In other words, the coefficient of $x^{9}$ is ${17\choose 9}3^8 = {1.59498\times 10^{8}}\text{.}$

🔗

10.

Solution.

To get an $x^{8}$ from the first term, we must pick 8 of the 17 factors to contribute an $x\text{,}$ leaving the other 9 to contribute a 2. There are ${17 \choose 8}$ ways to select these 8 factors, so the coefficient will be ${17 \choose 8} *2^{9}\text{.}$ Now we must choose 4 of the factors in the second term to contribute an $x\text{,}$ leaving the other 14 terms to contribute a 3. This gives us ${18 \choose 4}*3^{14}$ for the coefficient resulting from this term. In total, the term containing an $x^{8}$ will be ${17 \choose 8} *2^{9} + {18 \choose 4}*3^{14}= {1.46483\times 10^{10}}\text{.}$

🔗

3.2 Combining Outcomes
Practice Problems

1.

Solution.

There are $2 \cdot 4 \cdot 18 = {144}$ outfits. Use the multiplicative principle.

🔗

2.

Solution.

$2 + 6 = {8}$ ties. Use the additive principle.
🔗

🔗
$2 \cdot 6 = {12}$ ties. Use the multiplicative principle
🔗

🔗
$6 \cdot (5+7) + 8 = 42$ outfits.
🔗

🔗

🔗

3.

Solution.

There are 4096 4-digit hexadecimals in which the first digit is an E (one for each choice of the remaining digits). Similarly, there are 4096 hexadecimals in which the first digit is an F. We want the union of these two disjoint sets, so there are $4096 + 4096 = 2\cdot4096=8192$ 4-digit hexadecimals in which the first digit is either an E or an F.
🔗

🔗
We can select the first digit in 6 ways, digits 2-5 in 16 ways each, and the final digit in 10 ways. Thus there are $6\cdot 16^{4} \cdot 10 = 3932160$ hexadecimals given these restrictions.
🔗

🔗
The number of 5-digit hexadecimals that start with a letter is $6 \cdot 16^4 = 393216\text{.}$ The number of 5-hexadecimals that end with a numeral is $16^{4} \cdot 10 = 655360\text{.}$ We want all the elements from both these sets. However, both sets include those 5-digit hexadecimals which both start with a letter and end with a numeral( $6\cdot16^{3}\cdot 10=245760$), so we must subtract these (once). Thus the number of 5-digit hexadecimals starting with a letter or ending with a numeral is:
🔗

$\displaystyle{ 393216 + 655360 - 245760 = 802816 }$
🔗

🔗

🔗

4.

Solution.

$2^{11} = 2048$ subsets. We need to select yes/no for each of the 11 elements.
🔗

🔗
$2^{8} = 256$ subsets. We need to select yes/no for each of the remaining 8 elements.
🔗

🔗
$2^{11} - 2^{5} = 2016$ subsets. We subtract the number of subsets which do not contain any odd numbers ($2^{5}$-select yes or no for each even element) from the total number of possible subsets.
🔗

🔗
${5 \choose 1}\cdot 2^{6} ={320}$ subsets. First pick the even number. Then say yes or no to each of the odd numbers.
🔗

🔗

🔗

5.

Solution.

$\binom{8}{5} = 56$ subsets
🔗

🔗
$\binom{5}{2} = 10$ subsets. We need to select 2 of the 5 remaining elements of $S$ to be in the subset.
🔗

🔗
$\binom{8}{5} = 56$ subsets. All subsets of cardinality $5$ must contain at least one odd number.
🔗

🔗
$\binom{4}{1} = 4$ subsets. Select 1 of the 4 even numbers. The remaining 4 odd numbers of $S$ must all be in the set.
🔗

🔗

🔗

7.

Solution.

We can think of each row as a 12-bit string of weight 6 (since of the 12 coins, we require 6 to be pennies). Thus there are ${12 \choose 6} = {924}$ rows possible. Each row requires 12 coins, so if we want to make all the rows at the same time, we will need 11088 coins, half of them nickels and half of them pennies.
🔗

🔗
Now there are $2^{12} = 4096$ rows possible, which is also ${12 \choose 0} + {12\choose 1} + {12 \choose 2} +\dots + {12 \choose 12}\text{,}$ if you break them up into rows containing 0, 1, 2, etc. pennies. Thus, since there are 12 coins in each row, we need $12 \cdot 4096 = {49152}$ total coins.
🔗

🔗

🔗

8.

Solution.

Count the number of strings with each permissible number of 1’s separately and then add them up. So there are ${13 \choose 4} + {13 \choose 5} + \cdots {13 \choose 13} = {7814}$ strings.

🔗

9.

Solution.

This is the same as a question about 8-bit strings, since we can think of each subset as a 8-bit string with a 1 representing that we include that element in the subset. ${10 \choose 8} + {10\choose 9} + \cdots + {10\choose 10} = {56}$ subsets.

🔗

10.

Solution.

${ 22\choose 11} = {705432}$ paths. The paths all have length 22 (11 steps up and 11 steps right); we just select which 11 of those 22 should be right.
🔗

🔗
${11 \choose 5}{11\choose 6} = {213444}$ paths. First travel to $(6,7)\text{,}$ and then continue on to $(12,12)$ .
🔗

🔗
${ 22\choose 11} - {11 \choose 5}{11\choose 6} = {491988}$ paths. Remove all the paths that you found in part (b).
🔗

🔗

🔗

Additional Exercises

1.

Solution.

For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick.
🔗

🔗
For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror movie.
🔗

🔗

🔗

3.3 Non-Disjoint Outcomes
Practice Problems

3.

Solution.

48 students. Use Venn diagram or PIE: $29 + 24 + 27 - (10 + 13+17) + 8= {48}\text{.}$

🔗

4.

Solution.

Using the principle of inclusion/exclusion, the number of students who like their potatoes in at least one of the ways described is

🔗

$\displaystyle{ 53 + 51 + 70 -(22 + 33 + 36) +16 = {99}. }$

🔗

Therefore there are $115 - {99} = {16}$ students who do not like potatoes. You can also do this problem with a Venn diagram.

🔗

5.

Solution.

$2^{11} = {2048}\text{.}$ You have 2 choices for each of the remaining 11 bits.
🔗

🔗
${11 \choose 6} = 462\text{.}$ You need to choose 6 of the remaining 11 bits to be 1’s.
🔗

🔗
5632. There are $2^{11}$ strings that start with 011, and another $2^{12}$ which end with 01 (we choose 1 or 0 for 12 bits). However, we count the strings that start with 011 and end with 01 twice; there are $2^{9}$ such strings. So using PIE, we have $2^{11} + 2^{12} - 2^{9} = {5632}\text{.}$
🔗

🔗
1128. There are ${11 \choose 6} = 462$ strings of weight 8 which start with 011, and another ${12 \choose 7} ={792}$ which end with 01. We have over counted again: There are weight 8 strings which both start with 011 and end with 01, in fact ${9 \choose 5} ={126}$ of them. So all together we have $462+{792}-{126} = {1128}$ strings.
🔗

🔗

🔗

6.

Solution.

299 values of $n\text{.}$ Use PIE: $98 + 158+ 87 - (19 + 10 + 17) + 2$ or a Venn diagram. To find out how many numbers are divisible by 5 and 9, for example, take $790/(5\cdot9)$ and round down.

🔗

7.

Solution.

To find out how many numbers strictly less than 850 are multiples of 9, we can divide 850 by 9 and round down. There are 94 of these. Similarly, there are 169 multiples of 5 and 424 multiples of 2 less than 850.

🔗

We also need the combinations of these. To be a multiple of 9 and 5 means you are a multiple of 45 , and there are 18 multiples of 9 and 5. There will be 47 multiples of 9 and 2. There will be 84 multiples of 5 and 2. Finally, there will be 9 multiples of all three.

🔗

Using PIE, we get

🔗

$\displaystyle{ 94 +169+ 424 - (18 + 47 + 84) + 9 = {547} }$

🔗

multiples of 9, 5, or 2 less than 850.

🔗

8.

Solution.

$7^{12} = {1.38413\times 10^{10}}$ words, since you select from 7 letters 12 times.
🔗

🔗
$(7)\cdot (6)\cdot (5) \dots (7-12+1) = {0}$ words. After selecting a letter, you have fewer letters to select for the next one.
🔗

🔗
$7 ^ {9} ={4.03536\times 10^{7}}$ words: You need to select the letters that follow the “ade.”
🔗

🔗
$7^{9} + 7^{10} - 7^{7}={3.22005\times 10^{8}}$ words. There are $7^{9}$ words which start with “ade” and another $7^{10}$ words that end with “be.” Then we need to subtract the words that have both, which we have overcounted.
🔗

🔗
$(7 \cdot (7-1) \cdot (7-2) \dots (7-12+1)) - (10\cdot (4)\cdot (4-1) \cdot (4-2) \dots 4-9+1) = {0}$ words. All possible words without repeats minus the bad ones. The taboo word “bed” can be in any of 10 positions, and for each position we must choose the remaining 9 letters from the remaining 4 letters in our alphabet.
🔗

🔗

🔗

3.4 Combinations and Permutations
Practice Problems

1.

Solution.

${8 \choose 4} = {70}$ pizzas. We must choose (in no particular order) 4 out of the 8 toppings.
🔗

🔗
$2^{8} = {256}$ pizzas. Say yes or no to each topping.
🔗

🔗
$P(8,4) = {1680}$ ways. Assign each of the 4 spots in the left column to a unique pizza topping.
🔗

🔗

🔗

2.

Solution.

Despite its name, we are not looking for a combination here. The order in which the three numbers appear matters. There are $P(45,3) = 45\cdot 44 \cdot 43$ different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be $45^3$).

🔗

3.

Solution.

This is just the multiplicative principle. There are 8 digits which we can select for each of the 3 positions, so we have $8^3 = {512}$ such numbers.
🔗

🔗
Now we have 8 choices for the first number, 7 for the second, etc. So there are $8 \cdot 7 \cdot \dots \cdot 3 = P(8,3) = {336}$ such numbers.
🔗

🔗
To build such a number we simply must select 3 different digits. After doing so, there will only be one way to arrange them into increasing order. Thus there are ${8 \choose 3} = {56}$ such numbers.
🔗

🔗

🔗

4.

Solution.

We can write the answer as $P(18,14) = 18 \cdot 17 \cdot 16 \cdot \dots \cdot 5$ , which is the same as $\frac{18!}{4!}$ . Or, if you think of picking the 14 books and then arranging those 14, you can write this as $\binom{18}{14}\cdot 14!$ . Note, that since any order is acceptable, we are distinguishing between different orders, so a permutation is appropriate here.
🔗

🔗
Here we just need to select the books, and have no choice as how to arrange them. So the answer is just $\binom{18}{14}$
🔗

🔗

🔗

5.

Solution.

Since there are 14 different letters in “troublemakings”, we have 14 choices for the first letter, 13 for the next, 12 for the next, and so on. Thus there are $14!$ anagrams.

🔗

6.

Solution.

After the first letter (namely, v), we must rearrange the remaining 5 letters. There are only two choices of letter now, so this is really just a bit-string question where one of the letters is 0, and the other letter is 1. Thus there are ${5 \choose 1} = {5}$ anagrams starting with “v”.

🔗

7.

Solution.

First, decide where to put the “a”s. There are 8 positions, and we must choose 3 of them to fill with an “a”. This can be done in $\binom{8}{3}$ ways. The remaining 5 spots all get a different letter, so there are $5!$ ways to finish off the anagram. This gives a total of $\binom{8}{3}\cdot 5!$ anagrams. Strangely enough, this is 6720, which is also equal to $P(8,5)\text{.}$ To get the answer that way, start by picking one of the 8 positions to be filled by the first non-”a” letter, one of the remaining 7 positions to be filled by the next, and so on. Then put “a”s in the remaining 3 positions.

🔗

8.

Solution.

${24 \choose 4}\cdot {20 \choose 4} \cdot {16 \choose 4} \cdot \dots \cdot{4 \choose 4}$ ways. Pick 4 out of 24 people to be in the first foursome, then 4 of the remaining 20 for the second foursome, and so on (use the multiplicative principle to combine).
🔗

🔗
$6!{18 \choose 3}\cdot {15 \choose 3}\cdot {12 \choose 3} \cdot \dots \cdot {3 \choose 3}$ ways. First determine the tee time of the 6 board members, then select 3 of the 18 non-board members to golf with the first board member, then 3 of the remaining 15 to golf with the second, and so on.
🔗

🔗

🔗

9.

Solution.

$16!\text{.}$ There are 17 people seated around the table, but it does not matter where King Arthur sits, only who sits to his left, two seats to his left, and so on.

🔗

10.

Solution.

$21^{14}$ functions. There are 21 choices for the image of each element in the domain.
🔗

🔗
$P(21, 14)=21\cdot20\cdot19\cdot \dots \cdot 7$ injective functions. There are 21 choices for the image of the first element of the domain, then only 20 choices for the second, 19 for the third, and so on.
🔗

🔗

🔗

11.

Solution.

$7^{6} = {117649}$ functions, since there are 7 choices of where to send each of the 6 elements of the domain.
🔗

🔗
$P(7, 6) = 7\cdot 6 \cdot \cdots \cdot 2 = {5040}$ functions, since outputs cannot be repeated.
🔗

🔗
${7 \choose 6} = {7}$ functions. Since the function must be injective and increasing, we just need to select the 6 distinct elements of the range from the 7 elements of the codomain. Once these have been selected, we must put the smallest as the image of 1, the next smallest as the image of 2, and so on (doing this does not increase the number of functions, since there is one choice for how this event can occur).
🔗

🔗

🔗

Additional Exercises

1.

Solution.

120.

🔗

3.5 Counting Multisets
Practice Problems

1.

Solution.

${10\choose 5}$ sets. We must select 5 of the 10 digits to put in the set.
🔗

🔗
Use sticks and stones: Each stone represents one of the 5 elements of the set; each stick represents a switch between digits. So there are 5 stones and 9 sticks, giving us ${14 \choose 5}$ sets.
🔗

🔗

🔗

2.

Solution.

There are ${6 \choose 5}$ numbers. We simply choose 5 of the 6 digits and, once the choice is made, put them in increasing order.
🔗

🔗
This uses sticks and stones. Use a stone to represent each of the 5 digits in the number, and use their position relative to the sticks to say what numeral fills that spot. So we will have 5 stones and 5 sticks, giving ${10 \choose 5}$ numbers.
🔗

🔗

🔗

3.

Solution.

${30 \choose 21}$ ways. Each outcome can be represented by a sequence of 9 sticks and 21 stones.
🔗

🔗
${20 \choose 11}$ ways. First put one ball in each bin. This leaves 9 sticks and 11 stones.
🔗

🔗

🔗

4.

Solution.

${10 \choose 8}$ solutions. After each variable gets 1 stone for free, we are left with 8 stones and 2 sticks.
🔗

🔗
${13 \choose 11}$ solutions. We have 11 stones and 2 sticks.
🔗

🔗
${22 \choose 2}$ solutions. This problem is equivalent to finding the number of solutions to $x' + y' + z' = 20$ where $x'\text{,}$ $y'\text{,}$ and $z'$ are non-negative. (In fact, we really just do a substitution. Let $x = x'- 3\text{,}$ $y = y' - 3$ and $z = z' - 3$).
🔗

🔗

🔗

5.

Solution.

${10 \choose 5}$ outcomes are possible in traditional Yahtzee. Each die is a stone; its value is determined by where it is put relative to the sticks.

🔗

For Super-Yahtzee, ${10 \choose 4}$ outcomes. We have 6 stones (the 6 dice) and 4 sticks (the 4 switches between the numbers 1-5).

🔗

6.

Solution.

We must figure out how many different combinations of 11 coins are possible. Let a stone represent each coin, and a stick represent switching between type of coin. For example, if we have 7 coins, $**|*||****$ represents 2 pennies, one nickel, no dimes and 4 quarters. The number of such stone and stick diagrams for 14 total stones and sticks (with 11 stones and 3 sticks) is ${14 \choose 11} = {0.00274725}\text{.}$ Thus you have a 1 in 0.00274725 chance of guessing correctly.

🔗

7.

Solution.

${31 \choose 28}$ solutions. First we guarantee the restrictions on the variables by distributing 10 units to the variables. Then we find all solutions to $x_1' + x_2' + x_3' + x_4' = 28$ in non-negative integers.

🔗

8.

Solution.

${11\choose 7}= {330}\text{.}$ Note that a strictly increasing function is automatically injective. So the 7 outputs must all be different. So let’s first pick which 7 outputs we will use: there are ${11 \choose 7}$ ways to do this. Now how many ways are there to assign those outputs to the inputs $1$ through 7? Only one way, since there is only one way to arrange numbers in increasing order.
🔗

🔗
${17 \choose 7}\text{.}$ This is in fact a sticks and stones problem. The stones are the 7 inputs, and the sticks are the 10 spots between the 11 possible outputs. Think of it this way: We will specify $f(1)\text{,}$ then $f(2)\text{,}$ then $f(3)\text{,}$ and so on in that order. Start with the possible output 0. We can use it as the output of $f(1)\text{,}$ or we can switch to 1 as a potential output. Say we put $f(1) = 1\text{.}$ Now we are at 1 (can’t go back to 0). Should $f(2) = 1\text{?}$ If yes, then we are putting down another stone. If no, put down a bar and switch to 2. Maybe you switch to 3, then assign $f(2) = 3$ and $f(3) = 3$ (two more stones) before switching to 4 as a possible output. And so on.
🔗

🔗

🔗

9.

Solution.

${17 \choose 7}$ sodas (order does not matter, and repeats are not allowed).
🔗

🔗
$P(17, 7) = (17)\cdot (17-1)\cdot \dots \cdot 11$ sodas (order matters, and repeats are not allowed).
🔗

🔗
${23 \choose 7}$ sodas (order does not matter, and repeats are allowed; 7 stars and 16 bars).
🔗

🔗
$17^{7}$ sodas (order matters, and repeats are allowed; 17 choices 7 times).
🔗

🔗

🔗

Additional Exercises

1.

Solution.

You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry, and 0 bubblegum.
🔗

🔗
This is backwards. We don’t want the stones to represent the kids because the kids are not identical, but the stones are. Instead we should use 5 stones (for the lollipops) and use 5 sticks to switch between the 6 kids. For example,

\begin{equation*} \o\o||\o\o\o||| \end{equation*}

would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none.

🔗

🔗
This is the word AAAEOO.
🔗

🔗
This doesn’t represent a solution. Each stone should represent one of the 6 units that add up to 6, and the sticks should switch between the different variables. We have one too many sticks. An example of a correct diagram would be

\begin{equation*} \o|\o\o||\o\o\o\text{,} \end{equation*}

representing that $x_1 = 1\text{,}$ $x_2 = 2\text{,}$ $x_3 = 0\text{,}$ and $x_4 = 3\text{.}$

🔗

🔗

🔗

3.6 Combinatorial Proofs
Additional Exercises

1.

Solution.

Proof.

Question: How many 2-letter words start with a, b, or c and end with either y or z?

🔗

Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of $2+2+2\text{.}$

🔗

Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of $3 \cdot 2\text{.}$

🔗

Since the two answers are both answers to the same question, they are equal. Thus $2 + 2 + 2 = 3\cdot 2\text{.}$

🔗

5.

Solution.

She has ${15 \choose 6}$ ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has ${15 \choose 6}6$ choices.
🔗

🔗
She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in ${14 \choose 5}$ ways. Thus she has $15 {14 \choose 5}$ choices.
🔗

🔗
We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity, and the second way gives the right-hand side of the identity. Therefore the identity holds.
🔗

🔗

🔗

7.

Solution.

Proof.

Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select $k$ of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?

🔗

Answer 1: First select 2 of the $n$ balls to put in the jar. Then select $k-2$ of the remaining $n-2$ balls to put in the box. The first task can be completed in ${n \choose 2}$ different ways and the second task in ${n-2 \choose k-2}$ ways. Thus there are ${n \choose 2}{n-2 \choose k-2}$ ways to select the balls.

🔗

Answer 2: First select $k$ balls from the $n$ in the container. Then pick 2 of the $k$ balls you picked to put in the jar, placing the remaining $k-2$ in the box. The first task can be completed in ${n \choose k}$ ways and the second task in ${k \choose 2}$ ways. Thus there are ${n \choose k}{k \choose 2}$ ways to select the balls.

🔗

Since both answers count the same thing, they must be equal, and the identity is established.

🔗

3.8 Advanced Counting Using PIE
Practice Problems

1.

Solution.

${17 \choose 6}$ meals. First spend $7 to buy one of each item and then use 11 stars to select items between 6 bars.
🔗

🔗
${24 \choose 6}$ meals. Here you have 18 stars and 6 bars (separating the 7 items). a. ${24 \choose 6} - \left[{7 \choose 1}{21 \choose 6} - {7 \choose 2}{18 \choose 6} + {7 \choose 3}{15 \choose 6}\cdots\right]$ meals. Use PIE to subtract all the meals in which you get 3 or more of a particular item.
🔗

🔗

🔗

2.

Solution.

${29 \choose 9} = {1.0015\times 10^{7}}$ - there are 20 stars and 9 bars.
🔗

🔗
${19 \choose 9}= {92378}$ - buy one of each item, using $10. This leaves you $10 to distribute to the 10 items, so 10 stars and 9 bars.
🔗

🔗
${29 \choose 9} - \left[{10 \choose 1}{24 \choose 9} - {10 \choose 2}{19 \choose 9} + \cdots\right]$ meals. Use PIE to subtract all the meals in which you get 5 or more of a particular item.
🔗

🔗

🔗

3.

Solution.

${18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}$

🔗

4.

Solution.

The easiest way to solve this is to first distribute the minimum number of units to each variable (1), and then count the solutions to $y_1 + y_2 + y_3 + y_4 = 14$ with $0 \le y_i \le 5\text{.}$ By taking $x_i = y_i+5\text{,}$ each solution to this new equation corresponds to exactly one solution to the original equation.

🔗

Now all the ways to distribute the 14 units to the four $y_i$ variables can be found using stars and bars, specifically 14 stars and 3 bars, so ${17 \choose 14}$ ways. But this includes the ways that one or more $y_i$ variables can be assigned more than 3 units. So subtract using PIE to get $\displaystyle{ {17 \choose 3} -\left( {4\choose 1} {11 \choose 3}-{4\choose 2} {5 \choose 3} + \dots \right) }$

🔗

The ${4 \choose 1}$ counts the number of ways to pick one variable to be over-assigned; the ${11 \choose 3}$ is the number of ways to assign the remaining units to the 4 variables, etc.

🔗

5.

Solution.

${15 \choose 13} = 105\text{.}$ This makes sense because if each student can receive at most one star, you must pick which 13 of the 15 kids will get one.
🔗

🔗
Without any restriction, there would be ${27\choose 14}$ ways to distribute the stars. Now we must use PIE to eliminate all distributions in which one or more students get more than one star:
🔗

🔗

🔗

$\displaystyle{ {27 \choose 14} - \left[{15 \choose 1}{25 \choose 14} - {15\choose 2}{23 \choose 14} + {15\choose 3}{21 \choose 14} - \cdots \right] = 105. }$

🔗

6.

Solution.

First pick one of the 6 elements to be fixed. For each such choice, derange the remaining 5, using the standard advanced PIE formula. We get ${6 \choose 1}\left( 5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + \dots {5 \choose 5}0! \right] \right)$ permutations.

🔗

7.

Solution.

${11 \choose 6}\left(5! - \left[{5 \choose 1} 4! - {5 \choose 2}3! \dots + {5 \choose 5}0! \right]\right)={20328}$ ways. We choose 6 of the 11 ladies to get their own hats, and then multiply by the number of ways the remaining hats can be deranged.

🔗

8.

Solution.

🔗

$\displaystyle{ 9! - \left[{9 \choose 1}8! - {9 \choose 2}7! \dots {9 \choose 9}0! \right] = {133496} }$
🔗

🔗
🔗

$\displaystyle{ {9 \choose 4}\left(5! - \left[{5\choose 1}4! - {5 \choose 2}3! + \dots {5 \choose 5}0!\right]\right) = {5544} }$
🔗

🔗
0. Once 8 presents have their original label, there is only one present left and only one label left, so the 9th present must get its own label.
🔗

🔗

🔗

9.

Solution.

There are $5 \cdot 6^{8}$ functions for which $f(1) \ne c$ and another $5 \cdot 6^{8}$ functions for which $f(2) \ne f\text{.}$ There are $5^2 \cdot 6^{7}$ functions for which both $f(1) \ne c$ and $f(2) \ne f\text{.}$ So the total number of functions for which $f(1) \ne c$ or $f(2) \ne f$ or both is

🔗

$\displaystyle{ 5 \cdot 6^{8}+ 5 \cdot 6^{8} - 5^2 \cdot 6^{7} = {9.79776\times 10^{6}}. }$

🔗

10.

Solution.

$4^{11} - \left[{4 \choose 1}3^{11} - {4 \choose 2}2^{11} + {4 \choose 3}1^{11} - \dots +{4 \choose 3}1^{11}\right]$ functions. The $4^{11}$ is all the functions from $A$ to $B\text{.}$ We subtract those that aren’t surjective. Pick one of the elements in $B$ to not be in the range (in ${4 \choose 1}$ ways) and count all those functions ($3^{11}$). But this overcounts the functions where two elements from $B$ are excluded from the range, so subtract those. And so on, using PIE.

🔗

11.

Solution.

14833 functions. This is a sneaky way to ask for the number of derangements on 8 elements.

🔗

Additional Exercises

2.

Solution.

The 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

🔗

3.9 Chapter Summary

Chapter Review

3.9.1.

Solution.

${7 \choose 4}$ ways. After giving one present to each kid, you are left with 4 presents (stones) which need to be divided among the 4 kids (giving 3 sticks).
🔗

🔗
${11 \choose 8}={165}$ ways. You have 8 stones and 3 sticks.
🔗

🔗
$4^{8}\text{.}$ You have 4 choices for whom to give each present. This is like making a function from the set of presents to the set of kids.
🔗

🔗
$4^{8}- \left[{4 \choose 1}(4-1)^{8} - {4\choose 2}(4-2)^{8} + {4 \choose 3}(4-3)^{8} \dots \right]$ ways. Now the function from the set of presents to the set of kids must be surjective.
🔗

🔗

🔗

3.9.2.

Solution.

Neither. ${14 \choose 4}$ paths.
🔗

🔗
${10\choose 4}$ bow ties.

🔗
$P(10,4)\text{,}$ since order is important.

🔗
Neither. Assuming you will wear each of the 4 ties on just 4 of the 7 days, without repeats: ${10\choose 4}P(7,4)\text{.}$
🔗

🔗
$P(10,4)\text{.}$

🔗
${10\choose 4}\text{.}$

🔗
Neither. Since you could repeat letters: $10^4\text{.}$ If no repeats are allowed, it would be $P(10,4)\text{.}$
🔗

🔗
Neither. Actually, “k” is the 11th letter of the alphabet, so the answer is 0. If “k” was among the first 10 letters, there would only be 1 way – write it down.
🔗

🔗
Neither. Either ${9\choose 3}$ (if every kid gets an apple) or ${13 \choose 3}$ (if appleless kids are allowed).
🔗

🔗
Neither. Note that this could not be ${10 \choose 4}$ since the 10 things and 4 things are from different groups. $4^{10}\text{,}$ assuming each kid eats one type of cereal.
🔗

🔗
${10 \choose 4}\text{.}$ Don’t be fooled by the “arrange” in there. You are picking 4 out of 10 spots to put the 1’s.

🔗
${10 \choose 4}$ (assuming order is irrelevant).

🔗
Neither. $16^{10}$ (each kid chooses yes or no to 4 varieties).
🔗

🔗
Neither. 0.
🔗

🔗
Neither. $4^{10} - [{4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}]\text{.}$
🔗

🔗
Neither. $10\cdot 4\text{.}$
🔗

🔗
Neither. $4^{10}\text{.}$
🔗

🔗
${10 \choose 4}$ (which is the same as ${10 \choose 6}$).

🔗
Neither. If all the kids were identical, and you wanted no empty teams, it would be ${10 \choose 4}\text{.}$ Instead, this will be the same as the number of surjective functions from a set of size 11 to a set of size 5.
🔗

🔗
${10 \choose 4}\text{.}$

🔗
${10 \choose 4}\text{.}$

🔗
Neither. $4!\text{.}$
🔗

🔗
Neither. It’s ${10 \choose 4}$ if you won’t repeat any choices. If repetition is allowed, then this becomes $x_1 + x_2 + \cdots +x_{10} = 4\text{,}$ which has ${13 \choose 9}$ solutions in non-negative integers.
🔗

🔗
Neither. Since repetition of cookie type is allowed, the answer is $10^4\text{.}$ Without repetition, you would have $P(10,4)\text{.}$
🔗

🔗
${10 \choose 4}$ since that is equal to ${9 \choose 4} + {9 \choose 3}\text{.}$

🔗
Neither. It will be a complicated (possibly PIE) counting problem.
🔗

🔗

🔗

3.9.3.

Solution.

$2^{12} = {4096}$ choices. You have two choices for each tie: wear it or don’t.
🔗

🔗
You have 15 choices for regular ties (the $2^{4}$ choices less the “no regular tie” option) and 255 choices for bow ties ($2^{8}$ total minus the “no bow tie” option). Thus you have ${15} \cdot {255} = {3825}$ total choices.
🔗

🔗
${4\choose 3}{8\choose 2} = {112}$ choices.
🔗

🔗
Select one of the 2 bow ties to go on top. There are then 4 choices for the next tie, 4-1 for the tie after that, and so on. Thus $2\cdot 4! = {48}$ choices.
🔗

🔗

🔗

3.9.4.

Solution.

You own 8 purple bow ties, 3 red bow ties, 3 blue bow ties, and 5 green bow ties. How many ways can you select one of each color bow tie to take with you on a trip? $8 \cdot 3 \cdot 3 \cdot 5$ ways. How many choices do you have for a single bow tie to wear tomorrow? $8 + 3 + 3 + 5$ choices.

🔗

3.9.5.

Solution.

$8^{11}$ numbers.
🔗

🔗
$8^{10} \cdot 4$ numbers (choose any digits for the first 10 digits, then pick either an even or an odd last digit to make the sum even).
🔗

🔗
We need 6 or more even digits. 6 even digits: ${11 \choose 6}4^6 4^{11-6}\text{.}$ 6+1 even digits: ${11 \choose (6+1)}4^{6+1} *4^{11-6-1}\text{,}$ etc. By adding these together, we get the total number of ways to have 6 or more even digits.
🔗

🔗

🔗

3.9.6.

Solution.

47 passengers. We are asking for the size of the union of three non-disjoint sets. Using PIE, we have $27+22+30-(13 +11 + 12) + 4 = {47}\text{.}$

🔗

3.9.7.

Solution.

$2^11$ strings.
🔗

🔗
${11 \choose 4}$ strings.
🔗

🔗
${11 \choose 4}$ strings.
🔗

🔗

🔗

3.9.8.

Solution.

$3^{5}\cdot{16 \choose 11} + 5^{12}\cdot{20 \choose 8}\text{.}$

🔗

3.9.9.

Solution.

With repeated letters allowed, we select which 3 of the 11 letters will be vowels, then pick one of the 5 vowels for each spot, and finally pick one of the other 21 letters for each of the remaining 8 spots. Thus, ${11 \choose 3}5^3 21^{8}$ words.

🔗

Without repeats, we still pick the positions of the vowels, but now each time we place a vowel there, we have one fewer choice for the next one. Similarly, we cannot repeat the consonants. We get ${11 \choose 3}P(5,3) P(21, 8)$ words.

🔗

3.9.10.

Solution.

${3 \choose 2}{7 \choose 3}={105}$ paths.
🔗

🔗
${10 \choose 5} - {8 \choose 4}{2 \choose 1}={112}$ paths.
🔗

🔗
${3 \choose 2}{7 \choose 3} + {8 \choose 4}{2 \choose 1} - {3 \choose 2}{5 \choose 2}{2 \choose 1}= {185}$ paths.
🔗

🔗

🔗

3.9.11.

Solution.

${30 \choose 18}\left({30 \choose 18} - 1\right)$ routes. For each of the $\binom{30}{18}$ routes to work, there is exactly one less route back.

🔗

3.9.12.

Solution.

$2^{2} + 2^{3} - 2^{0}$ strings (using PIE).

🔗

3.9.13.

Solution.

${6 \choose 5} + {7 \choose 6} - {4 \choose 4}$ strings.

🔗

3.9.14.

Solution.

There are 7 spots to start the word, and then there are $6!$ ways to arrange the other letters in the remaining three spots. Thus the number of words avoiding the sub-word “bad” in consecutive letters is $9! - 7\cdot 6!={357840}\text{.}$

🔗

If we now need to avoid words that put “b” before “a” before “d”, we must choose which spots those letters go (in that order) and then arrange the remaining 6 letters. Thus, $9! - {9 \choose 3}6!={302400}$ words.

🔗

3.9.15.

Solution.

$2^n$ is the number of lattice paths which have length $n\text{,}$ since for each step you can go up or right. Such a path would end along the line $x + y = n\text{.}$ So you will end at $(0,n)\text{,}$ or $(1,n-1)$ or $(2, n-2)$ or … or $(n,0)\text{.}$ Counting the paths to each of these points separately, give ${n \choose 0}\text{,}$ ${n \choose 1}\text{,}$ ${n \choose 2}\text{,}$ …, ${n \choose n}$ (each time choosing which of the $n$ steps to be to the right). These two methods count the same quantity, and so are equal.

🔗

3.9.16.

Solution.

${18 \choose 13}={8568}$ ways.
🔗

🔗
${24 \choose 19}={42504}$ ways.
🔗

🔗
${18 \choose 13} - \left[{6 \choose 1}{11 \choose 5} - {6 \choose 2}{4 \choose 5} \dots \right]={7056}$ ways.
🔗

🔗

🔗

3.9.17.

Solution.

$6^5 + 6^5 - 6^4={14256}$ functions.
🔗

🔗
$5\cdot 6^5 + 6 \cdot 5 \cdot 6^4 - 5 \cdot 5 \cdot 6^4={45360}$ functions.
🔗

🔗
$6! - \left[ 5! + 5! - 4! \right]={504}$ functions. Note that we use factorials instead of powers because we are looking for injective functions.
🔗

🔗
Note that being surjective here is the same as being injective, so we can start with all $6!$ injective functions and subtract those which have one or more “fixed point”. We get $6! - \left[{6 \choose 1}(6-1)! - {6 \choose 2}(6-2)! + {6 \choose 3}(6-3)! - \dots {6 \choose 6}0! \right]={265}$ functions.
🔗

🔗

🔗

3.9.18.

Solution.

$4^6 - \left[{4 \choose 1}3^6 - {4 \choose 2}2^6 + {4 \choose 3} 1^6 \right]\text{.}$

🔗

3.9.19.

Solution.

${15 \choose 8}={6435}$ combinations. You need to choose 8 of the 15 cookie types. Order doesn’t matter.
🔗

🔗
$P(15, 8) = 15 \cdot (15-1) \cdot (15-2) \cdot \dots \cdot (15-8+1)= {2.59459\times 10^{8}}$ ways. You are choosing and arranging 8 out of 15 cookies. Order matters now.
🔗

🔗
${36 \choose 22}={3.7963\times 10^{9}}$ choices. You must switch between cookie type 14 times as you make your 22 cookies. The cookies are the stones; the switches between cookie types are the sticks.
🔗

🔗
$15^{22}$ choices. You have 15 choices for the “1” cookie, 15 choices for the “2” cookie, and so on.
🔗

🔗
$15^{22} - \left[{15 \choose 1}(15-1)^{22} - {15 \choose 2}(15-2)^{22} + \cdots - {15 \choose 15}0^{22} \right]={4.51953\times 10^{23}}$ choices. We must use PIE to remove all the ways in which one or more cookie type is not selected.
🔗

🔗

🔗

3.9.20.

Solution.

You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We could say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn’t matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types).
🔗

🔗
We want to consider injective functions from the set $\{$most, second most, second least, least$\}$ to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example).
🔗

🔗
This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.).
🔗

🔗
The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here.
🔗

🔗
Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part.
🔗

🔗

🔗

4 Sequences
4.1 Describing Sequences
Additional Exercises

1.

Solution.

The recursive definition is $a_n = a_{n-1} + 2$ with $a_1 = 1\text{.}$ A closed formula is $a_n = 2n-1\text{.}$
🔗

🔗
The sequence of partial sums is $1, 4, 9, 16, 25, 36, \ldots\text{.}$ A recursive definition is (as always) $b_n = b_{n-1} + a_n$ which in this case is $b_n = b_{n-1} + 2n-1\text{.}$ It appears that the closed formula is $b_n = n^2$
🔗

🔗

🔗

2.

Solution.

$0, 1, 2, 4, 7, 12, 20, \ldots\text{.}$

🔗
$F_0 + F_1 + \cdots + F_n = F_{n+2} - 1\text{.}$

🔗

🔗

3.

Solution.

The sequences all have the same recurrence relation: $a_n = a_{n-1} + a_{n-2}$ (the same as the Fibonacci numbers). The only difference is the initial conditions.

🔗

4.

Solution.

$3, 10, 24, 52, 108,\ldots\text{.}$ The recursive definition for $10, 24, 52, \ldots$ is $a_n = 2a_{n-1} + 4$ with $a_1 = 10\text{.}$

🔗

5.

Solution.

$-1, -1, 1, 5, 11, 19,\ldots$ Thus the sequence $0, 2, 6, 12, 20,\ldots$ has closed formula $a_n = (n+1)^2 - 3(n+1) + 2\text{.}$

🔗

6.

Solution.

This closed formula would have $a_{n-1} = 3\cdot 2^{n-1} + 7 \cdot 5^{n-1}$ and $a_{n-2} = 3\cdot 2^{n-2} + 7 \cdot 5^{n-2}\text{.}$ Then we would have

\begin{align*} 7a_{n-1} - 10a_{n-2} = \amp 7(3\cdot 2^{n-1} + 7 \cdot 5^{n-1}) - 10(3\cdot 2^{n-2} + 7 \cdot 5^{n-2})\\ = \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 30\cdot 2^{n-2} - 70 \cdot 5^{n-2})\\ = \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 15\cdot 2^{n-1} - 14 \cdot 5^{n-1})\\ = \amp 6\cdot 2^{n-1} + 35 \cdot 5^{n-1}\\ = \amp 3\cdot 2^{n} + 7 \cdot 5^{n} = a_n\text{.} \end{align*}

So the closed formula agrees with the recurrence relation. The closed formula has initial terms $a_0 = 10$ and $a_1 = 41\text{.}$

🔗

10.

Solution.

$\d\sum_{k=1}^n 2k\text{.}$

🔗
$\d\sum_{k=1}^{107} (1 + 4(k-1))\text{.}$

🔗
$\d\sum_{k=1}^{50} \frac{1}{k}\text{.}$

🔗
$\d\prod_{k=1}^n 2k\text{.}$

🔗
$\d\prod_{k=1}^{100} \frac{k}{k+1}\text{.}$

🔗

🔗

11.

Solution.

$\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\text{.}$

🔗
$\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\text{.}$

🔗
$\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\text{.}$

🔗
$\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)} = \frac{4}{3}\cdot\frac{9}{8}\cdot\frac{16}{15}\cdots\frac{10000}{9999}\text{.}$

🔗
$\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\text{.}$

🔗

🔗

4.2 Rate of Growth
Practice Problems

8.

Solution.

For arithmetic: $x = 83.6666666666667\text{,}$ $y = 42.3333333333333\text{.}$ For the arithmetic sequence, we know $125 + d = x\text{,}$ $x + d = y\text{,}$ and $y + d = 1\text{.}$ In other words, $125 + 3d = 1$ so $d = (-41.3333333333333)/3\text{.}$ For geometric: $x = {25}$ and $y = {5}\text{.}$ Similarly we can find the common ratio for the geometric sequence by solving $125\cdot r^3 = 1$ for $r\text{.}$

🔗

9.

Solution.

For arithmetic: $x = 18 \text{,}$ $y = 31 \text{.}$ We know that $5 + d = x\text{,}$ $x + d = y\text{,}$ and $y + d = 44\text{.}$ In other words, $5 + 3d = 44$ so $d = (39)/3\text{.}$

🔗

For geometric: $x = {10.3228}$ and $y = {21.312}\text{.}$ We can find the common ratio for the geometric sequence by solving $5\cdot r^3 = 44$ for $r\text{.}$

🔗

4.3 Polynomial Sequences
Practice Problems

1.

Solution.

This is an arithmetic sequence with initial term 10 and common difference 4.

🔗

For the last part, you are finding the sequence of partial sums, added to 5.

🔗

2.

Solution.

$50\text{,}$ which is $38+12\text{.}$
🔗

🔗
The sequence is arithmetic, with $a_0 = 2$ and constant difference 12, so $a_n = 2 + 12n\text{.}$
🔗

🔗
$59600\text{.}$ We want $2 + 26 + \cdots + 1190\text{.}$ Reverse and add to get 100 sums of 1192, a total of 119200, which is twice the sum we are looking for.
🔗

🔗

🔗

3.

Solution.

33.
🔗

🔗
$\displaystyle \frac{294 \cdot 32}{2} = 4851\text{.}$
🔗

🔗

🔗

4.

Solution.

${n-2+1}$ terms, since to get $10$ using the formula $5n+0$ we must use $n=2\text{.}$
🔗

🔗
$5n - 5\text{,}$ which is 5 less than $5n+0$ (or plug in $n-1$ for $n$).
🔗

🔗
$\frac{(5n+10)*({n-2+1})}{2}\text{.}$ Reverse and add. Each sum gives the constant $5n+10\text{,}$ and there are ${n-2+1}$ terms.
🔗

🔗

🔗

5.

Solution.

$666246\text{.}$ If we take $a_0 = 6\text{,}$ the terms of the sum are an arithmetic sequence with closed formula $a_n = 6+11n\text{.}$ Then $3823 = a_{347}\text{,}$ for a total of 348 terms in the sum. Reverse and add to get 348 identical 3829 terms, which is twice the total we seek. $3829\cdot 348/2 = 666246\text{.}$

🔗

6.

Solution.

$a_n = {2n^{2}+3n}\text{.}$ Here we know that we are looking for a quadratic because the second differences are constant. So $a_n = an^2 + bn + c\text{.}$ Since $a_0 = 0\text{,}$ we know $c= 0\text{.}$ So just solve the system

🔗

$\begin{aligned} {5} \amp = a + b\\ {14} \amp = 4a + 2b \end{aligned}$

🔗

to find $a = 2$ and $b = 3\text{.}$

🔗

7.

Solution.

$a_n = {n^{2}+2n-1}\text{.}$ Here we know that we are looking for a quadratic because the second differences are constant. So $a_n = an^2 + bn + c\text{.}$ Since $a_0 = {-1}\text{,}$ we know $c= {-1}\text{.}$ So just solve the system

🔗

$\begin{aligned} {2} \amp = a + b + {-1}\\ {7} \amp = 4a + 2b + {-1} \end{aligned}$

🔗

to find $a = {1}$ and $b = {2}\text{.}$

🔗

8.

Solution.

$a_n = {\left({\frac{3}{2}}\right)n^{3}+\left({\frac{7}{2}}\right)n-1}\text{.}$ Here we know that we are looking for a cubic because the third differences are constant. So $a_n = an^3 + bn^2 + cn + d\text{.}$ Since $a_0 = {-1}\text{,}$ we know $d= {-1}\text{.}$ So just solve the system

🔗

\begin{equation*} \begin{aligned} {4} \amp = a + b + c + {-1}\\ {18} \amp = 8a + 4b + 2c + {-1}\\ {50} \amp = 27a + 9b + 3c + {-1}\\ \end{aligned} \end{equation*}

🔗

to find $a = {{\frac{3}{2}}}\text{,}$ $b = 0\text{,}$ and $c = {{\frac{7}{2}}}\text{.}$

🔗

9.

Solution.

$a_n = {3n^{3}+2n^{2}+4n-4}\text{.}$ Here we know that we are looking for a cubic because the third differences are constant. So $a_n = an^3 + bn^2 + cn + d\text{.}$ We can work backwards to find that $a_0 = {-4}\text{,}$ so we know $d= {-4}\text{.}$ Then solve the system,

🔗

$\begin{aligned} {5} \amp = a + b + c + {-4}\\ {36} \amp = 8a + 4b + 2c + {-4}\\ {107} \amp = 27a + 9b + 3c + {-4}\\ \end{aligned}$

🔗

to find $a = {3}\text{,}$ $b = {2}\text{,}$ and $c = {4}\text{.}$

🔗

10.

Solution.

$a_{n-1} = (n-1)^2 - 3(n-1) - 5 = {3n^{2}-9n+1}\text{.}$ Thus $a_n - a_{n-1} = {6n-6}\text{.}$ Note that this is linear (arithmetic).

🔗

11.

Solution.

$a_n = {n^{3}+6n^{2}+n}\text{.}$ Here we know that we are looking for a cubic because the third differences are constant. So $a_n = an^3 + bn^2 + cn + d\text{.}$ We can work backwards to find that $a_0 = {0}\text{,}$ so we know $d= {0}\text{.}$ Then solve the system,

🔗

$\begin{aligned} {8} \amp = a + b + c\\ {34} \amp = 8a + 4b + 2c\\ {84} \amp = 27a + 9b + 3c\\ \end{aligned}$

🔗

to find $a = {1}\text{,}$ $b = {6}\text{,}$ and $c = {1}\text{.}$

🔗

Additional Exercises

4.

Solution.

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

🔗

5.

Solution.

$a_n = n^3 + n^2 - n + 1$

🔗

6.

Solution.

We have $2 = 2\text{,}$ $7 = 2+5\text{,}$ $15 = 2 + 5 + 8\text{,}$ $26 = 2+5+8+11\text{,}$ and so on. The terms in the sums are given by the arithmetic sequence $b_n = 2+3n\text{.}$ In other words, $a_n = \sum_{k=0}^n (2+3k)\text{.}$ To find the closed formula, we reverse and add. We get $a_n = \frac{(4+3n)(n+1)}{2}$ (we have $n+1$ there because there are $n+1$ terms in the sum for $a_n$).

🔗

9.

Solution.

$a_{n-1} = a(n-1)^2 + b(n-1) + c = an^2 - 2an + a + bn - b + c\text{.}$ Therefore $a_n - a_{n-1} = 2an - a + b\text{,}$ which is arithmetic. Notice that this is not quite the derivative of $a_n\text{,}$ which would be $2an + b\text{,}$ but it is close.

🔗

10.

Solution.

No. The sequence of differences is the same as the original sequence, so no differences will be constant.

🔗

11.

Solution.

No. The sequence is geometric, and in fact has closed formula $2\cdot 3^n\text{.}$ This is an exponential function, which is not equal to any polynomial of any degree. If the $n$th sequence of differences was constant, then the closed formula for the original sequence would be a degree $n$ polynomial.

🔗

4.4 Exponential Sequences
Practice Problems

1.

Solution.

$\frac{3\cdot 2^{19}-3}{1}\text{.}$ Let the sum be $S\text{,}$ and compute $2S - S = 1S\text{,}$ which causes terms except $3$ and $3\cdot 2^{19}$ to cancel. Then solve for $S\text{.}$

🔗

2.

Solution.

$\frac{1 + (-1)^{28} \frac{3^{28}}{5^{28}}}{8/5}\text{.}$ Compute $S + \frac{3}{5}S\text{.}$

🔗

3.

Solution.

$a_n = 1 + 2^{n+1}\text{.}$ We should use telescoping or iteration here. For example, telescoping gives

🔗

\begin{equation*} \begin{aligned} a_1 - a_0 \amp = 2^1\\ a_2 - a_1 \amp = 2^2\\ a_3 - a_2 \amp = 2^3\\ \vdots\amp \vdots \\ a_n - a_{n-1} \amp = 2^n \end{aligned} \end{equation*}

🔗

which sums to $a_n - a_0 = 2^{n+1} - 2$ (using the multiply-shift-subtract technique for the geometric series on the right-hand side). Substituting $a_0 =3$ and solving for $a_n$ completes the solution.

🔗

4.

Solution.

By the characteristic root technique. $a_n = {2^{n}+\left(-5\right)^{n}}\text{.}$

🔗

5.

Solution.

The characteristic roots for both sequences are $4$ and $-3$ (since the two sequences have the same recurrence relation, they have the same characteristic roots). Solving for coefficients in each case gives the closed formulas. We have $a_n = {4^{n}+\left(-3\right)^{n}}$ and $b_n = {\left({\frac{25}{7}}\right)\cdot 4^{n}+\left({\frac{10}{7}}\right)\mathopen{}\left(-3\right)^{n}}\text{.}$

🔗

6.

Solution.

By the characteristic root technique. $a_n = {\left({\frac{18}{5}}\right)\cdot 3^{n}-\left({\frac{13}{5}}\right)\mathopen{}\left(-2\right)^{n}}\text{.}$

🔗

Additional Exercises

1.

Solution.

171 and 341. $a_n = a_{n-1} + 2a_{n-2}$ with $a_0 = 3$ and $a_1 = 5\text{.}$ Closed formula: $a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\text{.}$ To find this solve the characteristic equation, $x^2 - x - 2 = 0\text{,}$ to get characteristic roots $x = 2$ and $x=-1\text{.}$ Then solve the system

\begin{align*} 3 \amp = a + b\\ 5 \amp = 2a - b \end{align*}

🔗

3.

Solution.

We claim $a_n = 4^n$ works. Plug it in: $4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}$ This works; just simplify the right-hand side.

🔗

6.

Solution.

$a_n = 4a_{n-1} + 5a_{n-2}\text{.}$
🔗

🔗
4, 21, 104, 521, 2604, 13021
🔗

🔗
$a_n = \frac{5}{6} 5^n + \frac{1}{6}(-1)^n \text{.}$
🔗

🔗

🔗

8.

Solution.

We have characteristic polynomial $x^2 - 2x + 1\text{,}$ which has $x = 1$ as the only repeated root. Thus, using the characteristic root technique for repeated roots, the general solution is $a_n = a + bn$ where $a$ and $b$ depend on the initial conditions.

$a_n = 1 + n\text{.}$

🔗
For example, we could have $a_0 = 21$ and $a_1 = 22\text{.}$
🔗

🔗
For every $x\text{.}$ Take $a_0 = x-9$ and $a_1 = x-8\text{.}$
🔗

🔗

🔗

4.5 Proof by Induction
Additional Exercises

1.

Solution.

If we have a number of beans ending in a 5, and we double it, we will get a number of beans ending in a 0 (since $5\cdot 2 = 10$ ). Then if we subtract 5, we will once again get a number of beans ending in a 5. Thus, if on any day we have a number ending in a 5, the next day we will also have a number ending in a 5.
🔗

🔗
If you don’t start with a number of beans ending in a 5 (on day 1), the above reasoning is still correct but not helpful. For example, if you start with a number ending in a 3, the next day you will have a number ending in a 1.
🔗

🔗
Part (b) is the base case, and part (a) is the inductive case. If on day 1 we have a number ending in a 5 (by part (b)), then on day 2 we will also have a number ending in a 5 (by part (a)). Then by part (a) again, we will have a number ending in a 5 on day 3. By part (a) again, this means we will have a number ending in a 5 on day 4.
🔗

The proof by induction would say that on every day we will have a number ending in a 5, and this works because we can start with the base case and then use the inductive case over and over until we get up to our desired $n\text{.}$
🔗

🔗

🔗

2.

Solution.

Proof.

We must prove that $1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1$ for all $n \in \N\text{.}$ Thus let $P(n)$ be the statement $1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}$ We will prove that $P(n)$ is true for all $n \in \N\text{.}$ First we establish the base case, $P(0)\text{,}$ which claims that $1 = 2^{0+1} -1\text{.}$ Since $2^1 - 1 = 2 - 1 = 1\text{,}$ we see that $P(0)$ is true. Now for the inductive case. Assume that $P(k)$ is true for an arbitrary $k \in \N\text{.}$ That is, $1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}$ We must show that $P(k+1)$ is true (i.e., that $1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1$). To do this, we start with the left-hand side of $P(k+1)$ and work to the right-hand side:

\begin{align*} 1 + 2 + 2^2 + \cdots + 2^k + 2^{k+1} = \amp ~ 2^{k+1} - 1 + 2^{k+1} \amp \text{by the inductive hypothesis.}\\ = \amp ~2\cdot 2^{k+1} - 1 \amp\\ = \amp ~ 2^{k+2} - 1 \amp \end{align*}

🔗

Thus $P(k+1)$ is true, so by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

🔗

3.

Solution.

Proof.

Let $P(n)$ be the statement, “$7^n - 1$ is a multiple of 6.” We will show $P(n)$ is true for all $n \in \N\text{.}$ First we establish the base case, $P(0)\text{.}$ Since $7^0 - 1 = 0\text{,}$ and $0$ is a multiple of 6, $P(0)$ is true. Now for the inductive case. Assume $P(k)$ holds for an arbitrary $k \in \N\text{.}$ That is, $7^k - 1$ is a multiple of 6, or in other words, $7^k - 1 = 6j$ for some integer $j\text{.}$ Now consider $7^{k+1} - 1\text{:}$

\begin{align*} 7^{k+1} - 1 ~ \amp = 7^{k+1} - 7 + 6 \amp \text{by cleverness:} -1 = -7 + 6\\ \amp = 7(7^k - 1) + 6 \amp \text{factor out a 7 from the first two terms}\\ \amp = 7(6j) + 6 \amp \text{by the inductive hypothesis}\\ \amp = 6(7j + 1) \amp \text{factor out a 6} \end{align*}

🔗

Therefore $7^{k+1} - 1$ is a multiple of 6, or in other words, $P(k+1)$ is true. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \in \N\text{.}$

🔗

4.

Solution.

Proof.

Let $P(n)$ be the statement $1+3 +5 + \cdots + (2n-1) = n^2\text{.}$ We will prove that $P(n)$ is true for all $n \ge 1\text{.}$ First the base case, $P(1)\text{.}$ We have $1 = 1^2$ which is true, so $P(1)$ is established. Now the inductive case. Assume that $P(k)$ is true for some fixed arbitrary $k \ge 1\text{.}$ That is, $1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}$ We will now prove that $P(k+1)$ is also true (i.e., that $1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2$). We start with the left-hand side of $P(k+1)$ and work to the right-hand side:

\begin{align*} 1 + 3 + 5 + \cdots + (2k-1) + (2k+1) ~ \amp = k^2 + (2k+1) \amp \text{by the inductive hypothesis}\\ \amp = (k+1)^2 \amp \text{by factoring} \end{align*}

🔗

Thus $P(k+1)$ holds, so by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$

🔗

5.

Solution.

Proof.

Let $P(n)$ be the statement $F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}$ We will show that $P(n)$ is true for all $n \ge 0\text{.}$ First the base case is easy because $F_0 = 0$ and $F_1 = 1$ so $F_0 = F_1 - 1\text{.}$ Now consider the inductive case. Assume $P(k)$ is true, that is, assume $F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}$ To establish $P(k+1)$ we work from left to right:

\begin{align*} F_0 + F_2 + \cdots + F_{2k} + F_{2k+2} ~ \amp = F_{2k+1} - 1 + F_{2k+2} \amp \text{by the inductive hypothesis.}\\ \amp = F_{2k+1} + F_{2k+2} - 1 \amp\\ \amp = F_{2k+3} - 1 \amp \text{by the recursive definition.} \end{align*}

🔗

Therefore $F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}$ which is to say $P(k+1)$ holds. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 0\text{.}$

🔗

6.

Solution.

Proof.

Let $P(n)$ be the statement $2^n \lt n!\text{.}$ We will show $P(n)$ is true for all $n \ge 4\text{.}$ First, we check the base case and see that yes, $2^4 \lt 4!$ (as $16 \lt 24$), so $P(4)$ is true. Now for the inductive case. Assume $P(k)$ is true for an arbitrary $k \ge 4\text{.}$ That is, $2^k \lt k!\text{.}$ Now consider $P(k+1)\text{:}$ $2^{k+1} \lt (k+1)!\text{.}$ To prove this, we start with the left side and work to the right side.

\begin{align*} 2^{k+1}~ \amp = 2\cdot 2^k \amp\\ \amp \lt 2\cdot k! \amp \text{by the inductive hypothesis}\\ \amp \lt (k+1) \cdot k! \amp \text{ since } k+1 \gt 2\\ \amp = (k+1)! \amp \end{align*}

🔗

Therefore $2^{k+1} \lt (k+1)!\text{,}$ so we have established $P(k+1)\text{.}$ Thus by the principle of mathematical induction $P(n)$ is true for all $n \ge 4\text{.}$

🔗

12.

Solution.

The only problem is that we never established the base case. Of course, when $n = 0\text{,}$ $0+3 \ne 0+7\text{.}$

🔗

13.

Solution.

Proof.

Let $P(n)$ be the statement that $n + 3 \lt n + 7\text{.}$ We will prove that $P(n)$ is true for all $n \in \N\text{.}$ First, note that the base case holds: $0+3 \lt 0+7\text{.}$ Now assume for induction that $P(k)$ is true. That is, $k+3 \lt k+7\text{.}$ We must show that $P(k+1)$ is true. Now since $k + 3 \lt k + 7\text{,}$ add 1 to both sides. This gives $k + 3 + 1 \lt k + 7 + 1\text{.}$ Regrouping $(k+1) + 3 \lt (k+1) + 7\text{.}$ But this is simply $P(k+1)\text{.}$ Thus by the principle of mathematical induction $P(n)$ is true for all $n \in \N\text{.}$

🔗

14.

Solution.

The problem here is that while $P(0)$ is true, and while $P(k) \imp P(k+1)$ for some values of $k\text{,}$ there is at least one value of $k$ (namely $k = 99$) when that implication fails. For a valid proof by induction, $P(k) \imp P(k+1)$ must be true for all values of $k$ greater than or equal to the base case.

🔗

16.

Solution.

We once again failed to establish the base case: When $n = 0\text{,}$ $n^2 + n = 0$ which is even, not odd.

🔗

22.

Solution.

The idea here is that if we take the logarithm of $a^n\text{,}$ we can increase $n$ by 1 if we multiply by another $a$ (inside the logarithm). This results in adding 1 more $\log(a)$ to the total.

🔗

Proof.

Let $P(n)$ be the statement $\log(a^n) = n \log(a)\text{.}$ The base case, $P(2)$ is true, because $\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}$ by the product rule for logarithms. Now assume, for induction, that $P(k)$ is true. That is, $\log(a^k) = k\log(a)\text{.}$ Consider $\log(a^{k+1})\text{.}$ We have

\begin{equation*} \log(a^{k+1}) = \log(a^k\cdot a) = \log(a^k) + \log(a) = k\log(a) + \log(a)\text{,} \end{equation*}

with the last equality due to the inductive hypothesis. But this simplifies to $(k+1) \log(a)\text{,}$ establishing $P(k+1)\text{.}$ Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 2\text{.}$

🔗

4.6 Strong Induction
Additional Exercises

3.

Solution.

The proof will be by strong induction.

🔗

Proof.

Let $P(n)$ be the statement, “$n$ is either a power of 2 or can be written as the sum of distinct powers of 2.” We will show that $P(n)$ is true for all $n \ge 1\text{.}$

🔗

Base case: $1 = 2^0$ is a power of 2, so $P(1)$ is true.

🔗

Inductive case: Suppose $P(k)$ is true for all $k \lt n\text{.}$ Now if $n$ is a power of 2, we are done. If not, let $2^x$ be the largest power of 2 strictly less than $n\text{.}$ Consider $n - 2^x\text{,}$ which is a smaller number, in fact smaller than both $n$ and $2^x\text{.}$ Thus $n-2^x$ is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be $2^x\text{,}$ so together with $2^x$ we have written $n$ as the sum of distinct powers of 2.

🔗

Therefore, by the principle of (strong) mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$

🔗

4.7 Chapter Summary

Chapter Review

4.7.1.

Solution.

$\frac{1028\cdot 128}{2} = {65792}\text{.}$

🔗

4.7.2.

Solution.

${n-3}$ terms.
🔗

🔗
$\displaystyle {4n+\left(-3\right)}\text{.}$
🔗

🔗
$\displaystyle \frac{(4n+14)*({n-3})}{2}\text{.}$
🔗

🔗

🔗

4.7.3.

Solution.

$3, 15, 75, 375, \ldots$ The sequence is geometric.
🔗

🔗
$\displaystyle \frac{3\cdot5^{21}-3}{4}={3.57628\times 10^{14}}\text{.}$
🔗

🔗

🔗

4.7.5.

Solution.

$a_n = {n^{2}-n+3}\text{.}$ Here we know that we are looking for a quadratic because the second differences are constant. So $a_n = an^2 + bn + c\text{.}$ We can work backwards to find that $a_0 = {3}\text{,}$ so we know $c= {3}\text{.}$ Then solve the system,

🔗

\begin{equation*} \begin{aligned} {3} \amp = a + b + {3}\\ {5} \amp = 4a + 2b + {3} \end{aligned} \end{equation*}

🔗

to find $a = {1}$ and $b = {-1}\text{.}$

🔗

4.7.6.

Solution.

The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence).
🔗

🔗
The sequence of second differences will be a degree 1 polynomial (an arithmetic sequence).
🔗

🔗

🔗

4.7.7.

Solution.

$4, 6, 10, 16, 26, 42, \ldots\text{.}$

🔗
No, taking differences gives the original sequence back, so the differences will never be constant.
🔗

🔗

🔗

4.7.8.

Solution.

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

🔗

4.7.10.

Solution.

The sequence is $3, 6, {12}, {24}, {48}, \ldots\text{.}$ It has closed formula $a_n = {3\cdot 2^{n}}\text{,}$ using the characteristic root technique.

🔗

4.7.11.

Solution.

The sequence is $5, 9, {39}, {93}, {327}, \ldots\text{.}$ It has closed formula $a_n = {\left({\frac{19}{5}}\right)\cdot 3^{n}+\left({\frac{6}{5}}\right)\mathopen{}\left(-2\right)^{n}}\text{,}$ using the characteristic root technique.

🔗

4.7.12.

Solution.

On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your 2 large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have $12$ mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is $2, 2, 6, 10, 22, 42\ldots$ starting with $a_0 = 2$ and $a_1 = 2\text{.}$
🔗

🔗
$a_n = a_{n-1} + 2a_{n-2}\text{.}$ This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).

🔗
Using the characteristic root technique, we find $a_n = a2^n + b(-1)^n\text{,}$ and we can find $a$ and $b$ to give $a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}$
🔗

🔗

🔗

4.7.17.

Solution.

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

🔗

5 Discrete Structures Revisited
5.1 Sets
Exercises

1.

Solution.

$A \cup B = {\left\{5,7,8,9,10,11,15,20\right\}}\text{.}$ It includes everything that is in $A$ or $B$ or both.
🔗

🔗
$A \cap B = {\left\{5,10\right\}}\text{.}$ It contains everything that is in both $A$ and $B\text{.}$
🔗

🔗
$A \setminus B = {\left\{7,8,9\right\}}\text{.}$ It contains everything that is in $A$ except anything that is also in $B\text{.}$ We could also have written this set as $A \cap \bar{B}\text{.}$
🔗

🔗
$B \setminus A = {\left\{11,15,20\right\}}\text{.}$ It contains everything in $B$ except anything that is also in $A\text{.}$ Another way to write this is $B \cap \bar{A}\text{.}$ Note that $A \setminus B \ne B \setminus A\text{.}$
🔗

🔗

🔗

2.

Solution.

This is the set $\{4, 5, 6, \ldots\}$ since we need each element to be a natural number whose square is at least 5 more than 5. Since $4^2 - 5 = 11$ but $3^2 - 5 = 4$ we see that the first such natural number is 4.
🔗

🔗
We get the same set as the previous part, and the smallest non-negative number for which $n^2 - 10$ is a natural number is 4.
🔗

Note that if we didn’t specify $n \ge 0$ by saying that $n \in \mathbb N$ then any integer less than $-4$ would also be in the set, so there would not be a least element.
🔗

🔗
This is the set $\{3, 4, 7, 12, \ldots\}\text{,}$ namely the set of numbers that are the result of squaring and adding 3 to a natural number. ($0^2 + 3 = 3\text{,}$ $1^2 + 3 = 4\text{,}$ $2^2 + 3 = 7$ and so on.) Thus the least element of the set is 3.
🔗

🔗
Now we are looking for natural numbers that are equal to taking some natural number, squaring it and adding 3. That is, $\{3, 4, 7, 12, \ldots\}\text{,}$ the same set as the previous part. So again, the least element is 3.
🔗

🔗

🔗

4.

Solution.

The set of largest size that is a subset of both $A \text{ and } B$ is the intersection of $A \text{ and } B \text{,}$ $A \cap B = {\left\{2,4,5,6\right\}}\text{.}$

🔗

7.

Solution.

There will be exactly 4 such sets: ${\left\{3,6,14\right\}}\text{,}$${\left\{3,6,13,14\right\}}\text{,}$ ${\left\{3,6,11,14\right\}}\text{,}$ and ${\left\{3,6,11,13,14\right\}}\text{.}$

🔗

8.

Solution.

$\displaystyle A \cap B = {\left\{7,8,9\right\}}\text{.}$
🔗

🔗
$\displaystyle A \cup B = {\left\{5,6,7,8,9,10,11\right\}}\text{.}$
🔗

🔗
$\displaystyle A \setminus B ={\left\{5,6\right\}}\text{.}$
🔗

🔗
$\displaystyle A \cap \overline{(B \cup C)} = {\left\{5\right\}}\text{.}$
🔗

🔗

🔗

11.

Solution.

For example, $A = \{2,3,5,7,8\}$ and $B = \{3,5\}$ .

🔗

12.

Solution.

For example, $A = \{1,2,3\}$ and $B = \{1,2,3,4,5,\{1,2,3\}\}$

🔗

13.

Solution.

No.
🔗

🔗
No.
🔗

🔗
$2\Z \cap 3\Z$ is the set of all integers which are multiples of both 2 and 3 (so multiples of 6). Therefore $2\Z \cap 3\Z = \{x \in \Z \st \exists y\in \Z(x = 6y)\}\text{.}$

🔗
$2\Z \cup 3\Z\text{.}$

🔗

🔗

15.

Solution.

$A \cup \bar B\text{:}$
🔗

$A venn diagram of two sets A and B. Every region is shaded except the region inside just B$

🔗
$\bar{(A \cup B)}\text{:}$
🔗

$A venn diagram of two sets A and B. The only region shaded is the region outside both circles.$

🔗
$A \cap (B \cup C)\text{:}$
🔗

$A Venn diagram of three sets, A, B, and C. 3 of the 8 regions are shaded: the center region common to all sets, and the regions common to A and B, and to A and C.$

🔗
$(A \cap B) \cup C\text{:}$
🔗

$A Venn diagram of three sets, A, B, and C. The entirety of C is shaded, as is the region common to A and B.$

🔗
$\bar A \cap B \cap \bar C\text{:}$
🔗

$A Venn diagram of three sets, A, B, and C. The only shaded region is inside just B$

🔗
$(A \cup B) \setminus C\text{:}$
🔗

$A Venn diagram of three sets, A, B, and C. The shaded regions are those inside just A, inside just B, and inside A and B (but outside of C).$

🔗

🔗

17.

Solution.

\begin{align*} \pow(A) = \{\amp \emptyset, \{a\}, \{b\}, \{c\}, \{d\}, \{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\},\\ \amp \{c,d\} \{a,b,c\}, \{a,b,d\}, \{a,c,d\}, \{b,c,d\}, \{a,b,c,d\}\}\text{.} \end{align*}

🔗

18.

Solution.

Each of the 13 elements can be in a singleton set, so there are 13 of these.

🔗

To count the number of doubletons, not that there are 12 sets that include 1, and then 11 sets that include 2 and not 1, and then 10 that include 3 and not 1 or 2, and so on. So you can find 78 by summing the numbers from 1 to 12.

🔗

20.

Solution.

For example, $A = \{1,2,3,4\}$ and $B = \{5,6,7,8,9\}$ gives $A \cup B = \{1,2,3,4,5,6,7,8,9\}\text{.}$

🔗

28.

Solution.

We need to be a little careful here. If $B$ contains 3 elements, then $A$ contains just the number 3 (listed twice). So that would make $|A| = 1\text{,}$ which would make $B = \{1, 3\}\text{,}$ which only has 2 elements. Thus $|B| \ne 3\text{.}$ This means that $|A| = 2\text{,}$ so $B$ contains at least the elements 1 and 2. Since $\card{B} \ne 3\text{,}$ we must have $\card{B} = 2\text{,}$ which agrees with the definition of $B\text{.}$

🔗

Therefore it must be that $A = \{2,3\}$ and $B = \{1, 2\}$

🔗

5.2 Functions
Exercises

1.

Solution.

$f(5) = 2\text{,}$ since 2 is the number below 5 in the two-line notation.
🔗

🔗
Such an $n$ is $n= 1\text{,}$ since $f(1) = 5\text{.}$ Note that 1 is above a 5 in the notation.
🔗

🔗
$n = 3$ has this property. We say that 3 is a fixed point of $f\text{.}$ Not all functions have such a point.
🔗

🔗
Such an element is 1 (in fact, that is the only element in the codomain that is not in the range). In other words, 1 is not the image of any element under $f\text{;}$ nothing is sent to 1.
🔗

🔗

🔗

5.

Solution.

There are 16 different functions. None of the functions are injective. Exactly 14 of the functions are surjective (there are 2 that are not: those that send everything to $a$ or everything to $b$). No functions are both (since no functions here are injective).

🔗

6.

Solution.

There are 16 functions: you have a choice of four outputs for $f(1)\text{,}$ and for each, you have four choices for the output $f(2)\text{.}$ Of these functions, 12 are injective, 0 are surjective, and 0 are both (i.e., bijective):

🔗

\begin{equation*} f = \twoline{1 \amp 2}{a\amp a} \quad f = \twoline{1 \amp 2}{b \amp b} \quad f = \twoline{1 \amp 2}{c \amp c} \quad f = \twoline{1 \amp 2}{d \amp d} \end{equation*}

🔗

\begin{equation*} f = \twoline{1 \amp 2}{a\amp b} \quad f = \twoline{1 \amp 2}{a \amp c} \quad f = \twoline{1 \amp 2}{a \amp d} \quad f = \twoline{1 \amp 2}{b \amp c} \end{equation*}

🔗

\begin{equation*} f = \twoline{1 \amp 2}{b \amp a} \quad f = \twoline{1 \amp 2}{c \amp a} \quad f = \twoline{1 \amp 2}{d \amp a} \quad f = \twoline{1 \amp 2}{c \amp b} \end{equation*}

🔗

\begin{equation*} f = \twoline{1 \amp 2}{b \amp d} \quad f = \twoline{1 \amp 2}{d \amp b} \quad f = \twoline{1 \amp 2}{c \amp d} \quad f = \twoline{1 \amp 2}{d \amp c} \end{equation*}

🔗

7.

Solution.

$f$ is not injective, since $f(2) = f(5)\text{;}$ two different inputs have the same output.
🔗

🔗
$f$ is surjective, since every element of the codomain is an element of the range.
🔗

🔗
$f=\begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \\ 3 \amp 2 \amp 4 \amp 1 \amp 2\end{pmatrix}\text{.}$
🔗

🔗

🔗

12.

Solution.

$f$ is injective, but not surjective (since 0, for example, is never an output).

🔗
$f$ is injective and surjective. Unlike in the previous question, every integers is an output (of the integer 4 less than it).

🔗
$f$ is injective, but not surjective (10 is not 8 less than a multiple of 5, for example).

🔗
$f$ is not injective, but is surjective. Every integer is an output (of twice itself, for example) but some integers are outputs of more than one input: $f(5) = 3 = f(6)\text{.}$

🔗

🔗

13.

Solution.

$f$ is not injective. To prove this, we must simply find two different elements of the domain which map to the same element of the codomain. Since $f(\{1\}) = 1$ and $f(\{2\}) = 1\text{,}$ we see that $f$ is not injective.
🔗

🔗
$f$ is not surjective. The largest subset of $A$ is $A$ itself, and $|A| = 10\text{.}$ So no natural number greater than 10 will ever be an output.
🔗

🔗
$f\inv(1) = \{\{1\}, \{2\}, \{3\}, \ldots \{10\}\}$ (the set of all the singleton subsets of $A$ ).
🔗

🔗
$f\inv(0) = \{\emptyset\}\text{.}$ Note that it would be wrong to write $f\inv(0) = \emptyset\text{;}$ that would claim that there is no input which has 0 as an output.
🔗

🔗
$f\inv(12) = \emptyset\text{,}$ since there are no subsets of $A$ with cardinality 12.
🔗

🔗

🔗

16.

Solution.

$|f\inv(3)| \le 1\text{.}$ In other words, either $f\inv(3)$ is the empty set or is a set containing exactly one element. Injective functions cannot have two elements from the domain both map to 3.
🔗

🔗
$|f\inv(3)| \ge 1\text{.}$ In other words, $f\inv(3)$ is a set containing at least one elements, possibly more. Surjective functions must have something map to 3.
🔗

🔗
$|f\inv(3)| = 1\text{.}$ There is exactly one element from $X$ which gets mapped to 3, so $f\inv(3)$ is the set containing that one element.
🔗

🔗

🔗

17.

Solution.

$X$ can really be any set, as long as $f(x) = 0$ or $f(x) = 1$ for every $x \in X\text{.}$ For example, $X = \N$ and $f(n) = 0$ works.

🔗

21.

Solution.

$f$ is injective.
🔗

Proof.

Let $x$ and $y$ be elements of the domain $\Z\text{.}$ Assume $f(x) = f(y)\text{.}$ If $x$ and $y$ are both even, then $f(x) = x+1$ and $f(y) = y+1\text{.}$ Since $f(x) = f(y)\text{,}$ we have $x + 1 = y + 1$ which implies that $x = y\text{.}$ Similarly, if $x$ and $y$ are both odd, then $x - 3 = y-3$ so again $x = y\text{.}$ The only other possibility is that $x$ is even and $y$ is odd (or vice-versa). But then $x + 1$ would be odd, and $y - 3$ would be even, so it cannot be that $f(x) = f(y)\text{.}$ Therefore if $f(x) = f(y)$ we then have $x = y\text{,}$ which proves that $f$ is injective.
🔗

🔗
🔗
$f$ is surjective.
🔗

Proof.

Let $y$ be an element of the codomain $\Z\text{.}$ We will show there is an element $n$ of the domain ($\Z$) such that $f(n) = y\text{.}$ There are two cases: First, if $y$ is even, then let $n = y+3\text{.}$ Since $y$ is even, $n$ is odd, so $f(n) = n-3 = y+3-3 = y$ as desired. Second, if $y$ is odd, then let $n = y-1\text{.}$ Since $y$ is odd, $n$ is even, so $f(n) = n+1 = y-1+1 = y$ as needed. Therefore $f$ is surjective.
🔗

🔗
🔗

🔗

22.

Solution.

Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective – it will be if there is at least one student who gets each grade.

🔗

24.

Solution.

This is not a function.

🔗

25.

Solution.

The recurrence relation is $f(n+1) = f(n) + n\text{.}$

🔗

26.

Solution.

In general, $\card{A} \ge \card{f(A)}\text{,}$ since you cannot get more outputs than you have inputs (each input goes to exactly one output), but you could have fewer outputs if the function is not injective. If the function is injective, then $\card{A} = \card{f(A)}\text{,}$ although you can have equality even if $f$ is not injective (it must be injective restricted to $A$).

🔗

27.

Solution.

In general, there is no relationship between $\card{B}$ and $\card{f\inv(B)}\text{.}$ This is because $B$ might contain elements that are not in the range of $f\text{,}$ so we might even have $f\inv(B) = \emptyset\text{.}$ On the other hand, there might be lots of elements from the domain that all get sent to a few elements in $B\text{,}$ making $f\inv(B)$ larger than $B\text{.}$

🔗

More specifically, if $f$ is injective, then $\card{B} \ge \card{f\inv(B)}$ (since every element in $B$ must come from at most one element from the domain). If $f$ is surjective, then $\card{B} \le \card{f\inv(B)}$ (since every element in $B$ must come from at least one element of the domain). Thus if $f$ is bijective then $\card{B} = \card{f\inv(B)}\text{.}$

🔗

6 Additional Topics
6.1 Generating Functions
Exercises

1.

Solution.

$\dfrac{4}{1-x}\text{.}$

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

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

🔗
$\dfrac{1}{1-5x}\text{.}$

🔗
$\dfrac{1}{1+3x}\text{.}$

🔗
$\dfrac{1}{1-5x^2}\text{.}$

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

🔗

🔗

2.

Solution.

$0, 4, 4, 4, 4, 4, \ldots\text{.}$

🔗
$1, 4, 16, 64, 256, \ldots\text{.}$

🔗
$0, 1, -1, 1, -1, 1, -1, \ldots\text{.}$

🔗
$0, 3, -6, 9, -12, 15, -18, \ldots\text{.}$

🔗
$1, 3, 6, 9, 12, 15, \ldots\text{.}$

🔗

🔗

4.

Solution.

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.

Solution.

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

🔗

6.

Solution.

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

🔗

7.

Solution.

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

🔗

8.

Solution.

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

🔗

9.

Solution.

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

🔗

12.

Solution.

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

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

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

🔗
$\frac{3x}{(1-x)^3}\text{.}$ (partial sums).

🔗

🔗

13.

Solution.

$0,0,1,1,2,3,5,8, \ldots\text{.}$

🔗
$1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, \ldots\text{.}$

🔗
$1, 3, 18, 81, 405, \ldots\text{.}$

🔗
$1, 2, 4, 7, 12, 20, \ldots\text{.}$

🔗

🔗

15.

Solution.

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

🔗

6.2 Introduction to Number Theory
Exercises

1.

Solution.

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

🔗

3.

Solution.

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

🔗

5.

Solution.

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

🔗

6.

Solution.

$3^{456} \equiv 1^{456} = 1 \pmod 2\text{.}$

🔗
$3^{456} = 9^{228} \equiv (-1)^{228} = 1 \pmod{5}\text{.}$

🔗
$3^{456} = 9^{228} \equiv 2^{228} = 8^{76} \equiv 1^{76} = 1 \pmod 7\text{.}$

🔗
$3^{456} = 9^{228} \equiv 0^{228} = 0 \pmod{9}\text{.}$

🔗

🔗

8.

Solution.

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

No solutions.
🔗

🔗
$x = 2\text{,}$ $x = 5\text{,}$ $x = 8\text{.}$

🔗
No solutions.
🔗

🔗

🔗

10.

Solution.

$x = 5+22k$ for $k \in \Z\text{.}$

🔗

12.

Solution.

$x = 6 + 15k$ for $k \in \Z\text{.}$

🔗

14.

Solution.

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.

🔗

15.

Solution.

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

🔗

Prev Top Next

\(P\)	\(Q\)	\(P \wedge Q\)	\(P \vee Q\)	\((P \wedge Q) \rightarrow (P \vee Q))\)
T	T	T	T	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	T

\(P\)	\(Q\)	\(\neg Q\)	\(Q \rightarrow P\)	\(\neg Q \vee (Q \rightarrow P))\)
T	T	F	T	T
T	F	T	T	T
F	T	F	F	F
F	F	T	T	T

\(P\)	\(Q\)	\(R\)	\(\neg P\)	\(Q \rightarrow R\)	\(\neg P \wedge (Q \rightarrow R)\)
T	T	T	F	T	F
T	T	F	F	F	F
T	F	T	F	T	F
T	F	F	F	T	F
F	T	T	T	T	T
F	T	F	T	F	F
F	F	T	T	T	T
F	F	F	T	T	T

\(P\)	\(Q\)	\(R\)	\(P \rightarrow (Q \vee R)\)	\((P \rightarrow Q) \vee (P\rightarrow R)\)
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	T	T
F	T	F	T	T
F	F	T	T	T
F	F	F	T	T

\(P\)	\(Q\)	\(P \rightarrow Q\)	\(\neg Q\)	\(\neg P\)
T	T	T	F	F
T	F	F	T	F
F	T	T	F	T
F	F	T	T	T

Appendix B Selected Solutions

1 Logic and Proofs1.1 Mathematical Statements Practice Problems

7.

8.

Additional Exercises

1.

2.

1.2 Implications Practice Problems

1.

2.

3.

Additional Exercises

1.

3.

5.

1.3 Rules of Logic Practice Problems

1.

2.

3.

4.

5.

6.

7.

8.

Additional Exercises

3.

5.

6.

16.

1.4 Proofs Additional Exercises

1.

2.

3.

4.

Proof.

5.

Proof.

Proof.

1.6 Chapter Summary

Chapter Review

1.6.1.

1.6.2.

1.6.3.

1.6.4.

1.6.5.

1.6.6.

1.6.7.

1.6.8.

1.6.9.

Proof.

Proof.

1.6.10.

2 Graph Theory2.1 Problems and Definitions Practice Problems

4.

Additional Exercises

1.

2.

4.

9.

10.

2.2 Trees Practice Problems

3.

5.

Additional Exercises

1.

2.

6.

12.

2.3 Planar Graphs Additional Exercises

1.

2.

6.

8.

Proof.

12.

Proof.

2.4 Euler Trails and Circuits Additional Exercises

1.

2.

8.

1 Logic and Proofs
1.1 Mathematical Statements
Practice Problems

1.2 Implications
Practice Problems

1.3 Rules of Logic
Practice Problems

1.4 Proofs
Additional Exercises

2 Graph Theory
2.1 Problems and Definitions
Practice Problems

2.2 Trees
Practice Problems

2.3 Planar Graphs
Additional Exercises

2.4 Euler Trails and Circuits
Additional Exercises

2.5 Coloring
Additional Exercises

3 Counting
3.1 Pascal’s Arithmetical Triangle
Practice Problems

3.2 Combining Outcomes
Practice Problems

3.3 Non-Disjoint Outcomes
Practice Problems

3.4 Combinations and Permutations
Practice Problems