$k = 12$ works.

Base cases (k = 12, 13, 14, 15): In all cases, there exist nonnegative integers $a$ and $b$ so that $k = 4a + 5b$: for 12, let $a=3$ and $b=0$ ($12 = 3 \cdot 4$); for 13, let $a=2$ and $b=1$ ($13 = 2 \cdot 4 + 5$); for 14, let let $a=1$ and $b=2$ ($14 = 4 + 2 \cdot 5$); and for 15, let $a=0$ and $b=3$ ($15 = 3 \cdot 5)$.

Inductive step: Let $k \ge 16$ and suppose any amount from 12 cents to $k-1$ cents can be made with 4- and 5-cent stamps. Then, since $12 \le k-4 \le k$ because $k \ge 16$, the inductive hypothesis says $k-4$ cents can be made with 4- and 5-cent stamps. Let $a$ and $b$ be the number of 4- and 5-cent stamps used to make $k-4$ cents (so $k-4 = 4a + 5b$ and $a,b \in \mathbb{N}$). Now $k$ cents can be made with $a+1$ 4-cent stamps and $b$ 5-cent stamps ($k = k-4+4 = 4a+5b+4 = 4(a+1)+5b$, where $a+1\in \mathbb{N}$ because $a,1\in \mathbb{N}$ and $\mathbb{N}$ is closed under addition).

Note that \begin{eqnarray} d_4 & = & 6 \cdot d_3 + 2 \cr & = & 6 \cdot ( 6 \cdot d_2 + 2) + 2 \cr & = & 6 \cdot 6 \cdot d_2 + 6 \cdot 2 + 2 \cr & = & 6 \cdot 6 \cdot (6 \cdot d_1 + 2) + 6 \cdot 2 + 2 \cr & = & 6 \cdot 6 \cdot 6 \cdot d_1 + 6 \cdot 6 \cdot 2 + 6 \cdot 2 + 2 \cr & = & 6 \cdot 6 \cdot 6 \cdot 3 + 6 \cdot 6 \cdot 2 + 6 \cdot 2 + 2 \cr & = & 6^3 \cdot 3 + \sum_{i=0}^2 (6^i \cdot 2) \cr \end{eqnarray}

We guess the general form \begin{eqnarray} d_n & = & 6^{n-1} \cdot 3 + \sum_{i=0}^{n-2} (6^i \cdot 2) \cr & = & 6^{n-1} \cdot 3 + 2 \cdot \sum_{i=0}^{n-2} 6^i \cr & = & 6^{n-1} \cdot 3 + 2 \cdot {6^{n-2+1} -1 \over 6-1} \cr & = & 6^{n-1} \cdot 3 + 2 \cdot {6^{n-1} -1 \over 5} \cr & = & {17 \over 5} \cdot 6^{n-1} - {2 \over 5} \cr \end{eqnarray}

We could prove that our formula is correct by induction, but for now we will merely check the first few terms: $d_1 = 3, d_2 = 20, d_3 = 122$ and ${17 \over 5} \cdot 1 - {2 \over 5} = 3$, ${17 \over 5} \cdot 6 - {2 \over 5} = 20$, ${17 \over 5} \cdot 36 - {2 \over 5} = 122$.

The recurrence is in the form $c_k = Ac_{k-1} + Bc_{k-2}$ where $A=5$ and $B=-6$ so we use the method of solving second-order linear homogeneous recurrences with constant coefficients. First, solve the characteristic equation $t^2 - At - B = 0$ which in this case is $t^2 - 5t + 6 = 0$, which has roots $r=2$ and $s=3$. So we know the formula is in the form $c_n = C \cdot 2^n + D \cdot 3^n$. We use the initial terms to solve for $C$ and $D$: \begin{eqnarray} c_0 & = & C \cdot 2^0 + D \cdot 3^0 \cr 8 & = & C + D \cr \end{eqnarray} \begin{eqnarray} c_1 & = & C \cdot 2^1 + D \cdot 3^1 \cr 21 & = & 2C + 3D \cr \end{eqnarray}

Which yields $C=3$ and $D=5$. So the formula is $c_n = 3 \cdot 2^n + 5 \cdot 3^n$. Again, a formal proof that the formula is correct would use induction but here we merely check a few terms: $c_0 = 8$, $c_1 = 21$, $c_2 = 57$ and $3 \cdot 2^0 + 5 \cdot 3^0 = 8$, $3 \cdot 2^1 + 5 \cdot 3^1 = 3 \cdot 2 + 5 \cdot 3 = 21$, and $3 \cdot 2^2 + 5 \cdot 3^2 = 3 \cdot 4 + 5 \cdot 9 = 57$.

Let $x \in A \cup (A \cap B)$. Then either $x \in A$ or $x \in A \cap B$ by definition of $\cup$. In the former case we immediately have $x \in A$. In the latter case, $x \in A$ and $x \in B$ by definition of $\cap$. So in either case $x \in A$. Therefore $A \cup (A \cap B) \subseteq A$.

Let $x \in A$. Then $x \in A \vee x \in A \cap B$, so by definion of $\cup$, $x \in A \cup (A \cap B)$. Therefore $A \subseteq A \cup (A \cap B)$.

Since $A \cup (A \cap B) \subseteq A$ and $A \subseteq A \cup (A \cap B)$, $A = A \cup (A \cap B)$.

Let $A$, $B$, $C$, and $D$ be sets such that $C \subseteq A-B$ and $D \subseteq B-A$. Suppose $C$ and $D$ are not disjoint. Then, by definition of disjoint, there exists $x \in C \cap D$, so $x \in C$ and $x \in D$. Now, since $C \subseteq A-B$ and $x \in C$, $x \in A-B$. Similarly, $x \in B-A$. Therefore, by definion of set difference, $x \in A$ and $x \not\in B$ and $x \in B$ and $x \not\in A$, which is a contradiction. Therefore $C$ and $D$ are disjoint.

Counterexample: let $A = \{1, 2\}$ and $B = \{2\}$. Then ${\cal P}(A-B) = {\cal P}(\{1\}) = \{\emptyset, \{1\}\}$ and ${\cal P}(A) - {\cal P}(B) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} - \{\emptyset, \{2\}\} = \{\{1\}, \{1, 2\}\}$.

There are $26\cdot26\cdot10\cdot10\cdot10$ plates of the first kind and $10^5\cdot 4 \cdot 26$ of the second kind (choose digits, then choose position for letter, then choose the letter) for a total of 11076000.

There are $13 \cdot {4 \choose 2} \cdot {12 \choose 2} \cdot 4 \cdot 4 = 82368$ one pair hands (choose the rank of the pair, choose the two suits of of four for that pair, choose the ranks of the other two cards, and choose the suit of one of them and then the other).

There are fewer than $13 \cdot 12 \cdot 11 \cdot 10 = 17160$ melting pot hands (choose the rank of the spade, the rank of the heart, the rank of the diamond, and the rank of the club; this total includes some straights hence the qualifier "fewer than"). So melting pot should beat one pair.

${9 \choose 4}$

$f$ is not one-to-one because, for example, $f(1) = f(-2) = f(-3) = 0$. $f$ is onto: $\lim_{x \rightarrow \infty} = \infty$ and $\lim_{x \rightarrow -\infty} = -\infty$, and $f$ is continuous, so, by the intermediate value theorem for any $y$ there is an $x$ such that $f(x) = y$. (Intuitively: $f$ is a cubic and so goes to positive and negative inifinity, so it intersects every horizontal line at least once.)

$f$ is not 1-1 because, for example, $f(1001) = f(110011) = 2$. $f$ is not onto because there is no $s$ such that $f(s) = -1$ since the length of the longest sequence of 0's in $s$ can never be negative.

We can describe any such function $f$ by giving the value $f$ takes on at 0, and all the points where the value of $f$ changes (for all $n \ge 1$ where $f(n) \ne f(n-1)$, give $n$ and $f(n)$). These descriptions are finite sequences of natural numbers because there can be at most 99 places where $f$ increases in value. The set of all finite sequences of natural numbers is countably infinite, and the set of those sequences that describe our functions is an infinite subset of the set of all finite sequences of natural numbers, so is itself countably infinite, and hence countable.

This set is uncountable. For suppose that it is countable. It is infinite (take $f_i(n) = i$ for any $i \in \mathbb{N}$ to form an infinite subset of the nondecreasing functions), and so countably infinite. By definition of countably infinite, there is then a 1-1, onto function $g$ from $\mathbb{N}$ to our set of functions. But we will construct a function $h$ in our set of functions so that $g(n) \ne h$ for any $n$, showing that $g$ is not onto: define $h:\mathbb{N} \rightarrow \mathbb{N}$ by $h(n) = \max(g(n)(n), h(0), \ldots, h(n-1)) + 1$. $h$ is nondecreasing because $h(n) \ge h(n-1) + 1$ for all $n \ge 1$, and so $h$ is in our set of functions. But for any $n$, $h(n) \ge g(n)(n)+1$, so $h(n) \ne g(n)(n)$ and hence $h \ne g(n)$, as promised. But the conclusion that $g$ is not onto contradicts the previous conclusion that $g$ is onto that arose from the assumption that our set of functions was countably infinite. So we reject that assumption: our set of functions is not countably infinite. Since it is not finite, it must be uncountable.

$R$ is not reflexive since $gcd(1,1) = 1$ and $1 R 1$ is false.

$R$ is symmetric since if $x R y$ then $gcd(x,y) \gt 1$ and $gcd(y,x) = gcd(x,y) \gt 1$ and therefore $y R x$.

$R$ is not antisymmetric since $gcd(8,2) = gcd(2,8)=2$ and so $2R8$ and $8R2$ but $2 \ne 8$.

$R$ is not transitive: $2 R 6$ and $6 R 3$ are both true but $2 R 3$ is false.

$R$ is not an equivalence relation because it is neither reflexive nor transitive.

$R$ is not an partial because it is neither reflexive nor antisymmetric, nor transitive.

$R$ is not a total order because it is not a partial order.

$S$ is reflexive: for any string $x$, $x$ is a substring of itself, so $xSx$.

$S$ is not symmetric: "be" is a substring of "bear" but "bear" is not a substring of "be".

$S$ is antisymmetric: if $xRy$ and $x \ne y$, then $y$ must be longer than $x$. But then $y$ can't be a substring of $x$, so it is not the case that $ySx$.

$S$ is transitive: suppose $x$ is a substring of $y$ and $y$ is a substring of $z$. Then there is an $a$ and $b$ such that y.substring(a,b).equals(z) and a $c$ and $d$ such that z.substring(c,d).equals(y). But then z.substring(c+a, c+b).equals(x), so $x$ is a substring of $z$.

$S$ is not an equivalence relation because it is not symmetric.

$S$ is a partial order because it is reflexive, antisymmetric, and transitive.

$S$ is not a total order because there are strings that are not comparable: for example, $baltimore$ is not a substring of $orioles$ and $orioles$ is not a substring of $baltimore$.

$T$ is reflexive: let $x \in {\bf Z}_{10}$. Then $x^3 -x^3 = 0$ and $3 | 0$ so $xTx$.

$T$ is symmetric: let $x,y \in {\bf Z}_{10}$ and suppose $xTy$. Then by definition of $T$, $3|(x^3-y^3)$ and by properties of divisibility $3 | (y^3-x^3)$ (use $a|b \wedge m\in{\bf Z} \Rightarrow a|bm$ with $a=3$, $b=(x^3-y^3)$ and $m=-1$). So $yTx$.

$T$ is transitive: let $x,y,z \in {\bf Z}_{10}$ and suppose $xTy$ and $yTz$. The by definition of $T$ we have $3|(x^3-y^3)$ and $3|(y^3-z^3)$. Now by properties of divisibility we have $3|(x^3-z^3)$ so $xTz$ (use $a|b \wedge a|c \Rightarrow a|(b+c)$ with $a=3$, $b = x^3-y^3$ and $c=y^3-z^3$).

The equivalence classes are $[0] = \{0, 3, 6, 9\}$, $[1] = \{1, 4, 7\}$ and $[2] = \{2, 5, 8\}$.

Suppose $\preccurlyeq$ is a partial order on a set $S$ and define $R$ as above. Then $R$ is also a partial order.

$R$ is reflexive because by definition, $xRx$ for all $x \in S$.

$R$ is also antisymmetric, for suppose by way of contradiction, that $xRy$ and $yRx$ for some $x, y \in S$ with $x \ne y$. Then, by definition of $R$, we have $y \preccurlyeq x$ and $x \preccurlyeq y$. So $\preccurlyeq$ is not antisymmetic, and so not a partial order, which contradicts the initial choice of $\preccurlyeq$.

$R$ is transitive. For suppose that $xRy$ and $yRz$. There are three cases, and in each we will get $xRz$. 1) If $x=y$ then we have $xRz$ from $yRz$ and substitution. 2) If $y=z$ we have $xRz$ from $xRy$ and substitution. 3) Now suppose $x \ne y$ and $y \ne z$. Then by definition of $R$, $y \preccurlyeq x$ and $z \preccurlyeq y$. Because $\preccurlyeq$ is a partial order and hence transitive, and because $z \preccurlyeq y$ and $y \preccurlyeq x$, we have $z \preccurlyeq x$. And so, by definition of $R$, we have $xRz$.

Since $R$ is reflexive, antisymmetric, and transitive, it is by defintion a partial order.

$R$ is always reflexive since $uRu$ for all vertices $u$ by definition of $R$.

$R$ is always transitive since if $uRv$ and $vRw$, then there is a path on which $u$ precedes $v$; truncate that path to the part that goes from $u$ to $v$. There is also a path on which $u$ precedes $w$; truncate that path to the part that goes from $v$ to $w$. Concatenate the truncated paths to get a path from $u$ to $v$ and then on to $w$; $v$ precedes $w$ on that path and so $uRw$.

So the question becomes "under what conditions is $R$ antisymmetric?" We claim that $R$ is antisymmetric if and only if $G$ is acyclic. $\Rightarrow$ (contrapositive): Suppose that $G$ has a cycle. Pick two distinct vertices $u$ and $v$ on that cycle. The part of the cycle from $u$ to $v$ is a path on which $u$ precedes $v$, so $uRv$. The rest of the cycle is a path from $v$ back to $u$, and $v$ precedes $u$ on that path, so $vRu$. Now we have $uRv$, $vRu$, and $u \ne v$, so $R$ is not antisymmetric. $\Leftarrow$ (contrapositive): Suppose that $R$ is not antisymmetric. Then there are distinct vertices $u$ and $v$ with $uRv$ and $vRu$. By definition of $R$, there are paths $P_1$ and $P_2$ on which $u$ precedes $v$ and $v$ precedes $u$ respectively. Truncate them to the parts from $u$ to $v$ and $v$ to $u$ to get $P'_1$ and $P'_2$, and concatenate those together to get $P$, which is now a path from $u$ to $v$ and back to $u$. $P$ may be a closed walk rather than a cycle, but we can find a shortest subpath of $P$ that starts and ends at the same place (the well-ordering principle!); that subpath is a cycle in $G$, so $G$ is not acyclic.

For $n \ge 5$, we have \begin{array}{rcll} 3n^3-4n^2+10n-5 & \le & 3n^3 + 10n & \textrm{since } -5 \le 0 \textrm{ and } n^2\gt 0 \textrm { and hence } -4n^2 \le 0 \cr & \le & 3n^3 + 10n^3 & \textrm{since } n\gt 5\gt 1 \textrm{ and hence } 1 \le n \le n^2 \le n^3 \cr & = & 13n^3. & \end{array}

Also, for $n \ge 5$, we have $4n^2 \le 5n^2 \le n^3$, $10n\ge 0$, and $5 \le n \le n^3$. So for $n \ge 5$ we have \begin{array}{rcl} 3n^3-4n^2+10n-5 & \ge & 3n^3-n^3+10n-n^3 \cr & = & n^3+10n \cr & \ge & n^3. \end{array} We have shown that there exists an $n_0$ (namely 5) and a $c_1$ and $c_2$ (namely 1 and 13 respectively) so that $\forall n \gt n_0, c_1 \cdot n^3 \le 3n^3-4n^2+10n-5 \le c_2 \cdot n^3$. Therefore, by the definition of $\Theta$, $3n^3-4n^2+10n-5 \in \Theta(n^3)$.

Solution:

• $n$, $8n + 1$
• $n \log n$
• $n (\log n)^2$
• $n^2 + n + 400$
• $2^n$
• $4^n$