---
tags: mth225
---

# Key for Learning Target quiz 6, 2021-11-12

## CA.1, CA.2, and SF.5

You can check these using calculators:

- [Base conversion calculator](https://www.rapidtables.com/convert/number/base-converter.html)
- [Binary arithmetic calculator](https://www.calculator.net/binary-calculator.html)
- [Wolfram|Alpha](https://wolframalpha.com) for the rest

## L.1

| Statement: | $A \rightarrow B$ | If I graduate from GVSU, I will get a great job. |
| --- | --- | --- |
| Hypothesis | $A$ | I graduate from GVSU |
| Conclusion | $B$ | I will get a great job |
| Negation | $A \wedge (\neg B)$ | I graduated from GVSU but did not get a great job |
| Converse | $B \rightarrow A$ | If I get a great job, then I graduated from GVSU. |
| Contrapositive | $(\neg B) \rightarrow (\neg A)$ | If I do not get a great job, then I did not graduate from GVSU. |

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

## L.2

1.
| $P$ | $Q$ | $Q \rightarrow P$ | $(\neg P)$ | $(\neg P) \wedge Q$ |
| --- | --- | ---------- | -----------------| ---- |
| T | T | T | F | F |
| T | F | T | F | F |
| F | T | F | T | T |
| F | F | T | T | T |

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

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

## L.3

1. False, False, True, False
2. (a) False, example: $n = 111$.
(b) True, for example: $n = 142$.
(c) True, because for example $Q(1)$ is true. (In fact this is the one and only value of $x$ in the positive integers that makes this predicate true.)
3. Every GVSU graduate is employed.

## SF.1

1. (a) $\{1,9,25,49\}$
(b) $\{3,5,7\}$
(c) $\{1,3,5,7,9\}$

2. Two possible correct answers:
- $\{10^{-n} \, : \, x \in \mathbb{N}\}$
- $\{x \in \mathbb{N} : x \ \text{is a power of 0.1} \}$
There are lots of others.

3. (a) False (for example $-1 \not \in \mathbb{N}$)
(b) True
(c) True (The empty set is a subset of every set)
(d) False ($\sqrt{2}$ is not an integer, therefore not a natural number)
(e) True
(f) False ($1$ is in the first set but not in the second)

## SF.2

1. $\emptyset$ (the sets are disjoint)
2. $\{0,1,2,3,4,5,9\}$
3. $\{0,1,2,3\}$
4. $\{0,1,2,6,7,8,10\}$
5. $\{0,1,2,4,5,9\}$
6. 8
8. $\{\emptyset, \{5\}, \{9\}, \{5,9\}\}$

## SF.3

1. This is a not a function because $2$ maps to two things.
2. This is a function with domain $\{1,2,3,4\}$, codomain = $\{x,y,z,t\}$, and range $\{x,y,t\}$.
3. This is a function domain $\{1,2,3,4\}$, codomain = $\{x,y,z,t\}$, and range $\{t,x,z\}$.

## SF.4

1. This function is bijective. (Make a table of outputs to see.)
2. This function is injective, but not surjective because for example nothing maps to 2. Therefore not bijective.
3. This function is injective, but not surjective because for example nothing maps to 2. Therefore not bijective.

## C.1

1. There are 16 choices (0..9 or A..F) for each of the five digits, so the total number is $16^5 = 1048576$.
2. The number of 4-bit strings with a 1 in the leftmost bit is $2^3 = 8$ because the other bits can be chosen freely. The number with 10 in the rightmost two bits is $2^2 = 4$ because the left two bits can be chosen freely. The number with *both* properties is 2 --- namely the strings 1010 and 1110. So the number with either the first property or the second is $8 + 4 - 2 = 10$.

## C.2

$\binom{15}{10} = \dfrac{15!}{10! \cdot 5!} = \dfrac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{120} = 3003$

$\binom{15}{15} = 1$ because this is the number of 15-element subsets of a 15-element set.

$\binom{15}{1} = 15$ because there are 15 ways to choose one item from a set of 15.

The number of 5-element subsets of $\{1,2,\dots,20\}$ is $\binom{20}{5} = \dfrac{20!}{15! \cdot 5!} = \dfrac{20 \cdot 19 \cdot 18 \cdot 17 \cdot 16}{120}= 15504$.

## C.3

1. There are 22 ways to elect the chair, and then 21 ways to elect the assistant chair, so the total number is $22 \cdot 21 = 462$. (This is also $P(22,2)$.)
2. There are no repeated letters here, so the number of rearrangements is $7! = 5040$.

## C.4

1. We are distributing 10 items to four distinct bins. There are three switches between bins. A stars-and-bars diagram would therefore consist of 13 objects, 3 of which are bars. The number of distributions is therefore $\binom{13}{3} = 286$.
2. Give one piece of candy to each kid first to make sure everybody gets at least one. There are six pieces left over to distribute freely. They are identical and being given to four different kids, therefore three switches between the kids. A stars-and-bars diagram would therefore have 9 objects, three of which are bars. The number of distributions is therefore $\binom{9}{3} = 84$.

## RI.1

1. 5, 11, 23, 47, 95, 191 (Notice indexing starts at 1)
2. -1, 3, 7, 11, 15, 19
3. 2, 7, 23, 72, 220, 665
4. 1, 2, 5, 12, 29, 70

## RI.2

1. 86
2. 21
3. $\sum_{n = 0}^4 (3n+1)$
4. $\sum_{n = 1}^{10} 2^n$

There are mutiple right answers for the third and fourth items.

## RI.3

Note, we will assume all indexing starts at zero.

1. This is an arithmetic sequence with common amount added equal to 3 and initial value 1. Therefore $f(n) = 3n + 1$ is a closed formula, and $a_0 = 1$ and $a_n = a_{n-1} + 3$ is a recursive formula.
2. This is a geometric sequence with common ratio 2 and initial value 2. Therefore $f(n) = 2 \cdot 2^n$ (or $f(n) = 2^{n+1}$) is a closed formula, and $a_0 = 2$ and $a_n = 2a_{n-1}$ is a recursive formula.
3. This is an arithmetic sequence with common amount added equal to 2 and initial value 2. Therefore $f(n) = 2n + 2$ is a closed formula, and $a_0 = 2$ and $a_n = a_{n-1} + 2$ is a recursive formula.
2. This is a geometric sequence with common ratio $0.1$ and initial value 1. Therefore $f(n) = (0.1)^n$ is a closed formula, and $a_0 = 1$ and $a_n = 0.1a_{n-1}$ is a recursive formula.

## RI.4

The function $f(n) = 4^n$ **is a solution** to the recurrence relation given by $a_0 = 1, a_1 = 4$ and $a_n = a_{n-1} + 12a_{n-2}$. Here are the checking steps:

**Checking the initial conditions**: $f(0) = 4^0 = 1$ and $f(1) = 4^1 = 4$. These equal to $a_0$ and $a_1$.

**Checking the recurrence relation**: Replace $a_n$ on the left side of the recurrence relation with $f(n)$. This gives $4^n$. Then replace $a_{n-1}$ with $f(n-1)$ and $a_{n-2}$ with $f(n-2)$ on the right side. These are equal to $4^{n-1}$ and $4^{n-2}$ respectively, which gives:

$$\begin{align*}
a_{n-1} + 12a_{n-2} &= 4^{n-1} + 12 \cdot 4^{n-2} \qquad (\text{Replacement}) \\
&= 4^{n-1} + 3 \cdot 4 \cdot 4^{n-2} \qquad (\text{Split off factor of 4})\\
&= 4^{n-1} + 3 \cdot 4^{n-1} \qquad (\text{Multiplication raises the exponent})\\
&= 4 \cdot 4^{n-1} \qquad (\text{Adding like terms})\\
&= 4^n \qquad (\text{Multiplication raises the exponent})
\end{align*}$$

This equals the computation of the left side, so the function satisfies the recurrence relation.