---
tags: mth225
---

# Key for Learning Target Quiz 8, 2021-12-06

## CA.1

1. 1001101 and 4D
2. 191
3. 213
4. 10110000

## L.1

| Statement: | If I am not vaccinated, I will be disenrolled from my Winter semester courses. |
| ---- | ----- |
| Hypothesis: | I am not vaccinated |
| Conclusion: | I will be disenrolled from my Winter semester courses |
| Negation: | I am not vaccinated, and I was not disenrolled from my Winter semester courses. |
| Converse: | If I am disenrolled from my Winter semester courses, then I was not vaccinated. |
| Contrapositive: | If am not disenrolled from Winter semester courses, then I am vaccinated. |

## L.2

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

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

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

## L.3

1. False, False, False, True
2. (a) True, for example $x = 1$
(b) True, for example $x = 10$
(c) False, for example $x = 1$
3. There exists a rectangle whose opposite sides are not parallel. Or, *some rectangles have opposite sides not parallel*. There are more formulations.

## SF.1

1. (a) $\{0, 1, 2\}$ (No duplicates!)
(b) $\emptyset$ because the only solution to $x + 5 = 0$ is $x = -5$ which is not in $\mathbb{N}$.

2. For example: $\{ 3^n \, : \, n \in \mathbb{N}\}$ (Note the correction made in https://campuswire.com/c/GB1A69E25/feed/148)
3. (a) True
(b) False
(c) True
(d) True
(e) True
(f) False

## SF.2

1. $\{a,d,e,f,g,z\}$
2. $\{d\}$
3. $\{z\}$
4. $\{a,b,c,e,f,g\}$
5. $\{a\}$
6. 16
7. $\{\emptyset, \{a\}, \{z\}, \{a,z\}\}$

## SF.3

1. This is a function with domain $\{1,2,3\}$, codomain $\mathbb{N}$, and range $\{0, 10,100\}$.
2. This is not a function because there's no assignment for 4.
3. This is a function with domain equal to the set of all English words, and both codomain and range are $\{A,B,C,\dots,Z\}$.

## SF.4

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

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

For example, $f(3) = \lfloor \frac{3}{2} \rfloor + 1 = 1 + 1 = 2$. This function is neither injective (because $f(2) = f(3)$ for example) nor surjective (for example, $0$ is never output).

2.This is not injective, because for example $h(1011)$ and $h(1101)$ both equal 3. It is surjective however. (This doesn't require proof, but here's one anyway: Every element in the set $\{0,1,2,3,4\}$ has something mapping onto it, for example $g(0000)=0$, $g(0001) = 1$, $g(0011) =2$, $g(0111)=3$ and $g(1111)=4$.)

3. This function is injective, surjective and bijective.

## SF.5

1. $1$
2. $-2$
3. $2$
4. $-1$
5. $720$
6. $1$
7. $2$
8. $1$
9. $6$

## C.1

1. We need to **count the number of 16-bit strings with `10` in the leftmost two bits**, then **count the number of 16-bit strings with `0` in the rightmost bit**, then add those counts together then **subtract the number of 16-bit strings with both `10` on the left and `0` on the right**.

The number of 16-bit strings with `10` on the left is $2^{14}$ because the rightmost two bits are locked in, but the remaining 14 can be chosen freely with two options per choice.

Similarly the number of 16-bit strings with `0` on the right is $2^{15}$.

Similarly the number of 16-bit strings with both these properties is $2^{13}$ (the two leftmost and one rightmost bits are locked in, and there's a free choice for the other 13).

Therefore the number we want is $2^{14} + 2^{15} - 2^{13} = 40960$.

2. Choosing a wardrobe is a sequence of three choices, with 5 options for the first choice, 3 for the second, and 17 for the third. The Multiplicative Principle says the total number of choices is then $5 \times 3 \times 17 = 255$.

## C.2

1. We are selecting three items at random, without caring about ordering, from a set of 17. The number of choices is therefore the same as the number of 3-element subsets of a 17-element set, which is $\binom{17}{3} = 680$.
2. Assign each coin flip a bit, 1 for heads and 0 for tails. The number of ways to flip a coin 10 times and get 7 heads is therefore the same as the number of 10-bit strings with exactly 7 `1` bits, which is $\binom{10}{7} = 120$.

## C.3

1. There are 50 possible awards for first place, then 49 possible for second, then 48 possible for third. So the total count is $P(50,3) = 50 \times 49 \times 48 = 117600$.
2. This is simply the number of rearrangements of 11 "items", which is $11! = 39916800$.

## C.4

1. This is a standard stars-and-bars problem where we are distributing 20 "stars" to three different bins. There are two switches between bins, so a stars-and-bars diagram would have 22 objects, 2 of which are bars. The number of such diagrams is $\binom{22}{2} = 231$.
2. This is the same as the first problem, except to ensure each variable is greater than or equal to 3, we give out three stars to each bin. That's 9 stars given out, so now the total amount to distribute is 11. A stars-and-bars diagram will have 13 objects, 2 of which are stars. The number of such diagrams is $\binom{13}{2} = 78$.

:::info
**Bonus**: Execute the Python code below to actually see the solutions to the equation. Put `len( )` around a list to get its cardinality.

# First part 
[(x,y,z) for x in range(21) for y in range(21) 
 for z in range(21) if x+y+z == 20]

# Second part 
[(x,y,z) for x in range(3,21) for y in range(3,21) 
 for z in range(3,21) if x+y+z == 20]

:::

## RI.1

1. $12, 14, 16, 18, 20, 22$
2. $2, 0.2, 0.002, 0.0002, 0.00002, 0.000002$
3. $1, 2, 6, 15, 31, 56$
4. $2, 3, 9, 18, 45, 99$

## RI.2

1. $6 + 10 + 14 + 18 + 22 + 26 = 96$
2. $200 + 2000 = 2200$
3. $\sum_{n=0}^{99} \left(1 + 4n\right)$
4. $\sum_{n=0}^5 \left(4 \cdot (1.5)^n\right)$

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 |
| :----: | :----: | :------------: | :---------------: |
| $4, \, 6, \, 9, \, 13.5, \, 20.25, \, \dots$ | Geometric, ratio = $1.5$ | $f(n) = 4 \cdot (1.5)^n$ | $a_0 = 4$, $a_n = 1.5a_{n-1}$ if $n>0$ |
| $1, 5, 9, 13, 17, \dots$ | Arithmetic, amount = 4 | $f(n) = 1 + 4n$ | $a_0 = 1$, $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$ |
| $4, 8, 16, 32, 64, 128, 256, \dots$ | Geometric, ratio = $2$ | $f(n) = 4(2)^n$ | $a_0 = 4$, $a_n = 2a_{n-1}$ if $n > 0$ |

## RI.4

The function $f(n)= 4 - 3n$ is a solution to the recurrence relation $a_0 = 4$, $a_1 = 1$ and for $n > 1$, $a_n = 2a_{n-1} - a_{n-2}$.

First note that $f(0) = 4 - 3(0) = 4$ and $f(1) = 4 - 3(1) = 1$, so the initial conditions are met.

For $n > 1$, on the right side of the recurrence relation replace $a_{n-1}$ with $f(n-1)$ and $a_{n-2}$ with $f(n-2)$. These are, respectively,

\begin{align*}
f(n-1) &= 4 - 3(n-1) = 4 - 3n + 3 = 7 - 3n \\
f(n-2) &= 4 - 3(n-2) = 4 - 3n + 6 = 10 - 3n
\end{align*}

Now when we replace we get:
\begin{align*}
2a_{n-1} - a_{n-2} &= 2(7-3n) - (10-3n) \\
&= 14 - 6n - 10 + 3n \\
& = 4 - 3n
\end{align*}
This equals $a_n$ if a similar replacement is made, so the function solves the recurrence relation.

## RI.5

The characteristic equation for this recurrence relation is
$$r^2 + 6r + 9 = 0$$
The left side factors into $(r+3)^2$. So the characteristic equation has a single repeated root of $r = -3$.

The solution framework is
$$f(n) = c_1(-3)^n + c_2n(-3)^n$$
The initial conditions require $f(0)=3$ and $f(1) = -3$. Therefore we have
$$3 = c_1(-3)^0 + c_2(0)(-3)^0$$
which gives $c_1 = 3$. Also,
$$-3 = c_1(-3)^1 + c_2(1)(-3)^1$$
which gives the equation $-3 = -3c_1 - 3c_2$, which simplifies to $1 = c_1 + c_2$. Since we know $c_1 = 3$, we therefore have $c_2 = -2$.

Therefore the solution is
$$f(n) = 3\cdot (-3)^n - 2n(-3)^n$$.

## RI.6

* **Base case**: We want to show that $1 = 1^2$. This is obviously true. (The left side is a sum with one term.)

* **Induction hypothesis:** Assume that for some positive integer $k$,
$$1 + 3 + 5 + 7 + \cdots + (2k-1) = k^2$$

* **Proof step:** We now want to show that
$$1 + 3 + 5 + 7 + \cdots + (2(k+1)-1) = (k+1)^2$$
(Note the left side can be written $1 + 3 + 5 + 7 + \cdots + (2k+1)$.) A step we might take here is to group the first $k$ terms on the left together and then use the induction hypothesis.

:::info
**Bonus:** Here is a completed proof of this.

**Proof:** We first want to show that $1 = 1^2$. This is obviously true, so the base case holds.

Now assume that for some positive integer $k$,
$$1 + 3 + 5 + 7 + \cdots + (2k-1) = k^2$$

We then want to show that
$$1 + 3 + 5 + 7 + \cdots + (2k + 1) = (k+1)^2$$
The left side of this, with the next-to-last term written, is
$$1 + 3 + 5 + 7 + \cdots + (2k-1) + (2k + 1)$$
Group all but the last term together:
$$\left(1 + 3 + 5 + 7 + \cdots + (2k-1)\right) + (2k + 1)$$
The induction hypothesis lets us substitute $k^2$ for the sum that's been grouped off:
$$k^2 + (2k + 1)$$
This is $k^2 + 2k + 1$ which is equal to $(k+1)^2$ when factored. That's what we wanted to show, so the proof is done. :sunglasses:
:::