---
tags: mth225
---

# Key for Learning Target Quiz 7, 2021-11-22

## L.1

| Statement: | $R \rightarrow S$ | If it snows, the temperature is below freezing. |
| --- | --- | --- |
| Hypothesis | $R$ | It snows |
| Conclusion | $S$ | The temperature is below freezing |
| Negation | $R \wedge (\neg S)$ | It's snowing but the temperature is not below freezing. |
| Converse | $S \rightarrow R$ | If the temperature is below freezing, then it's snowing. |
| Contrapositive | $(\neg S) \rightarrow (\neg R)$ | If the temperature is not below freezing, then it's not snowing. |

Note, "but" and "and" in the negation are interchangeable.

## L.2

1.
| $A$ | $B$ | $\neg A$ | $\neg B$ | $A \wedge (\neg B)$ | $(\neg A) \vee B$
| --- | --- | ---------- | -----------------| :----: | :--: |
| T | T |F | F | F | T |
| T | F |F | T | T | F |
| F | T | T | F | F| T|
| F | F | T | T | F | T |

So the two statements are **not** logically equivalent.

2.
| $P$ | $Q$ | $R$ | $P \rightarrow Q$ | $Q \rightarrow R$ | $(P \rightarrow Q) \wedge (Q \rightarrow R)$ |
|:---:|:---:|:---:|:----------:|:---------------------:| :--: |
| T | T | T | T | T | T
| T | F | T | F | T | F
| F | T | T | T | T | T
| F | F | T | T | T |T
| T | T | F | T | F |F
| T | F | F | F | T |T
| F | T | F | T | F |F
| F | F | F | T | T |T

## L.3

1. False, False, False, True
2. (a) False, for example $x = 10$
(b) True, for example $x = 16$
(c) False, for example $x = 1$
3. Some faculty senate meetings do not run over time.

## SF.1

1. (a) $\{10, 20, 30, \dots, 100\}$
(b) $\{0,1\}$ (No duplicates!)

2. For example: $\{3 + 10n \, : \, n \in \mathbb{N}\}$
3. (a) True
(b) False
(c) True
(d) True
(e) True
(f) False

## SF.2

1. $\{4\}$
2. $\{0,1,2,3,4,5,6,8\}$
3. $\{0,1,2,3,5\}$
4. $\{0,1,3,5,7,9,10\}$
5. $\{ 4,8\}$
6. $8$
7. $\{\emptyset, \{4\}, \{8\}, \{4,8\}\}$

## SF.3

1. This is NOT a function because 2 maps to two different things
2. This is NOT a function because $5$ doesn't map to anything.
3. This is a function; domain = $\{1,2,3,4,5\}$, codomain = $\{x,y,z,t\}$, range = $\{x,z,t\}$

## SF.4

1. Here's a table of inputs-outputs for this function:

| $x$ | 1 | 2 | 3 | 4 | 5 |
| -- | - | - | - | - | - |
| $f(x)$ | 2 | 3 | 4 | 1 | 2 |

So this function is surjective because every point in the codomain $\{1,2,3,4\}$ is mapped to, but not injective because $1$ and $5$ map to $2$.

2.This is not injective, because for example $h(-1)$ and $h(1)$ both equal 2. It's also not surjective because no negative number is ever hit.

3. This function is injective, but not surjective because $0$ is never output.

## C.1

1. There are two answers that are accepted as correct, depending on whether you think a seven-digit number can start with a 0. (The number 0 is definitely even but you may not have considered something like 0127382 to be a "seven digit number".)
- If we allow a starting zero, then if we start with an even number, there are five choices for the first digit (0,2,4,6,8) and ten for the remaining six, for a total of $5 \cdot 10^6$ numbers. To end with an even number, there are the same number of choices. The number of numbers that *both* start *and* end in an even number is $5^2 \cdot 10^5$ since there are 5 choices for the start and end, and a free choice for the middle 5 digits. The Inclusion/Exclusion Principle then gives the total number we are counting as $5 \cdot 10^6 + 5 \cdot 10^6 - 5^2 \cdot 10^5 = 8523775$.
- If a starting zero is not allowed: There are $4 \cdot 10^6$ seven-digit numbers that start with an even number, and $9 \cdot 10^5 \cdot 5$ that end in an even number. And, there are $4 \cdot 10^5 \cdot 5$ that both start and end in an even number. Therefore the total amount we are counting is $4 \cdot 10^6 + 9 \cdot 10^5 \cdot 5 - 4 \cdot 10^5 \cdot 5 = 7500000$.

2. The total number of outfits is $3 \cdot 4 \cdot 2 = 24$.

## C.2

1. (a) $\binom{12}{8} = \frac{12!}{4! \cdot 8!} = 495$
(b) $\binom{120}{120} = 1$ because this is the number of 120-element subsets of a 120-element set.
(c) $\binom{120}{119} = \frac{120!}{1! \cdot 119!} = 120$

2. The number of ways to select 6 cards from a deck of 12 distinct cards is $\binom{12}{6} =\frac{12!}{6! \cdot 6!} = 924$.

## C.3

1. If we deal the cards out to six different people, the order of the selection matters. There are 12 ways for the first person to get a card; then 11 ways for the second person; and so on. The total number is $P(12,6) = \frac{12!}{6!} = 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 665280$.
2. There are $26 \cdot 25 \cdot 24$ ways to produce the letters and then $10 \cdot 9 \cdot 8$ ways to produce the digits, for a total of $P(26,3) \cdot P(10,3) = 15600 \cdot 720 = 11232000$ different license plates.

## C.4

1. This is a stars/bars problem with 10 stars, and since there are three children there are 2 bars. The total number of objects is 12, and 2 of those are bars, so the number of distributions is $\binom{12}{2} = 66$.
2. First give two books to each child, so there are 4 left over. There are now 4 stars and 2 bars, so the total number of distributions is $\binom{6}{2} = 15$.

## RI.1

1. $9, 21, 57, 165, 489, 1461, \dots$
2. $3, 1, -1, -3, -5, -7, \dots$
3. $2, 7, 20, 49, 110, 235, \dots$
4. $1, 2, 4, 8, 16, 32, \dots$

## RI.2

1. $5 + 8 + 11 + 14 = 38$
2. $2 \cdot 3^2 + 2 \cdot 3^3 + 2 \cdot 3^4 = 234$
3. $\sum_{n=1}^{50} 2n$
4. $\sum_{n=0}^4 2 \cdot 3^n$

Multiple correct answers are possible for 3 and 4.

## RI.3

Assume all indices start at 0 unless is says otherwise.

| Sequence | Type | Closed formula | Recursive formula |
| :----: | :----: | :------------: | :---------------: |
| $2, 6, 18, 54, 162, \dots$ | Geometric, ratio = 3 | $f(n) = 2 \cdot 3^n$ | $a_0 = 2$, $a_n = 3a_{n-1}$ if $n>0$ |
| $2, 6, 10, 14, 18, \dots$ | Arithmetic, amount = 4 | $f(n) = 2 + 4n$ | $a_0 = 2$, $a_n = a_{n-1} + 4$ if $n > 0$ |
| $2, 5, 8, 11, 14, \dots$ | Arithmetic, amount = 3 | $f(n) = 2 + 3n$ | $a_0 = 2$, $a_n = a_{n-1} + 3$ if $n > 0$ |
| $1, 0.1, 0.01, 0.001, \dots$ | Geometric, ratio = 0.1 | $f(n) = (0.1)^n$ | $a_0 = 1$, $a_n = 0.1a_{n-1}$ if $n > 0$ |

## RI.4

The function $f(n) = 2^{n+1} - 1$ **is a solution** to $a_n = 1 + 2a_{n-1}$ with initial condition $a_0 = 1$.

The initial condition is satisfied because $f(0) = 2^{0+1} - 1 = 2 - 1 = 1$.

For $n > 0$, check the expression $1 + 2a_{n-1}$ by replacing $a_{n-1}$ with $f(n-1)$:

$$\begin{align*}
1 + 2a_{n-1} &= 1 + 2 \left( 2^{(n-1) + 1} - 1 \right) \quad (\text{Replacement with} \ f(n-1))\\
&= 1 + 2\left( 2^n - 1 \right) \quad (\text{Simplify in the exponent}) \\
&= 1 + 2^{n+1} - 2 \quad (\text{Multiply the 2 through; raises the exponent})\\
&= 2^{n+1} - 1 \quad (\text{Subtract} \ 1-2)
\end{align*}$$
This equals $f(n)$, so the recurrence relation is satisfied.

## RI.5

The characteristic equation for this recurrence relation is $$r^2 - 7r + 10 = 0$$This factors into $(r-5)(r-2) = 0$, so the recurrence relation has two characteristic roots: $r=5$ and $r=2$. So the solution framework is
$$f(n) = c_1 5^n + c_2 2^n$$
The initial conditions say that $f(0) = 2$, so $2 = c_1 5^0 + c_2 2^0 = c_1 + c_2$. Likewise $f(1) = 1$, so $1 = c_1 5^1 + c_2 2^1 = 5c_1 + 2c_2$. So we have the linear system:
$$\begin{align*}
c_1 + c_2 & = 2 \\
5c_1 + 2c_2 &= 1
\end{align*}$$
multiplying both sides of the first equation by $-2$ gives
$$\begin{align*}
-2c_1 -2c_2 & = -4 \\
5c_1 + 2c_2 &= 1
\end{align*}$$
Adding the left and right sides of these gives $3c_1 = -3$, so $c_1 = -1$. Then since $c_1 + c_2 = 2$, we have $c_2 = 3$. Therefore the solution is
$$f(n) = -1 \cdot 5^n + 3 \cdot 2^n.$$