Math 116: Midterm Study Guide (Part II)

2.4 Orders of magnitude

Exercise 1 Show that $2^n=O(n!)$ .

Note that for $n=4$ ,

$2^4=2\cdot 2\cdot 2 \cdot 2 \cdot 2 = 1 \cdot 2 \cdot 2 \cdot 4 \leq 1 \cdot 2 \cdot 3 \cdot 4 =4!$

When $n>4$ ,

$\begin{align*} 2^n &= 2^{n-4}\cdot 2^4 \leq 2^{n-4}\cdot 4! \\ &= 2\cdot \cdots \cdot 2 \cdot 4! \leq n \cdot (n-1) \cdot \cdots \cdot 5 \cdot 4! \\ &= n! \end{align*}$

Therefore, $2^n \leq n!$ for all $n \geq 4$ , i.e. $2^n=O(n)$ .

Exercise 2 Show that $n^2=O(2^n)$ .

We must show that $n^2\leq c 2^n$ for some constant $c$ and for all $n\geq k$ for some natural number $k$ . Suppose, I choose an arbitrary $n$ , say $n=3$ , then

$\begin{align*} 3^2 & \leq c2^3 \\ 9 \leq 8 c \end{align*}$

Thus, choose $c\geq \frac{9}{8}$ , say $c=\frac{9}{8}$ . Then, we show by induction $n^2 \leq \frac{9}{8}2^n$ . The base case is given by $9=3^2\leq \frac{9}{8}2^3=9$ . Assume $k^2 \leq \frac{9}{8}2^k$ , then

$(k+1)^2=k^2+2k+1\leq \frac{9}{8}2^k + 2k+1$

Note that $2k+1 < \frac{9}{8}2^k$ for all $k>3$ as $2k+1\leq k^2$ for $k>3$ . Thus

$\begin{align*} k^2+2k+1 &\leq \frac{9}{8}2^k+2k+1 \\ &\leq \frac{9}{8}2^k + \frac{9}{8}2^k \\ &= 2\left( \frac{9}{8}2^k\right) = \frac{9}{8}2^{k+1} \end{align*}$

Therefore, $n^2=O(2^n)$ .

Exercise 3 Let $p(x)=a_nx^n+a_{n-1}x^{n-1} + \cdots + a_1x+a_0$ be a polynomial with non-negative coefficients (with $a_n\not=0$ ). Show that $p(x)=O(x^n)$ . You may use $x^i=O(x^{i+1})$ .

Note that

$p(x)=a_nx^n+a_{n-1}x^{n-1} + \cdots + a_1x+a_0 \leq (a_n+\cdots + a_0)x^n$

Therefore, $p(x)=O(x^n)$ .

Exercise 4 Let $p(x)=a_nx^n+a_{n-1}x^{n-1} + \cdots + a_1x+a_0$ be a degree $n$ polynomial (i.e. $a_n\not=0$ ). Show that $p(x)=o(x^{n+1})$ .

Note that

$\begin{align*} \lim\limits_{x \to \infty} \frac{p(x)}{x^{n+1}}&= \lim\limits_{x \to \infty} \frac{a_nx^n+a_{n-1}x^{n-1} + \cdots + a_1x+a_0}{x^{n+1}} \\ &\stackrel{\text{L'H}}{=}\lim\limits_{x \to \infty} \frac{na_nx^{n-1}+(n-1)a_{n-1}x^{n-2} + \cdots + a_1}{(n+1)x^{n}} \\ &\stackrel{\text{L'H}}{=} \cdots \stackrel{\text{L'H}}{=} \lim\limits_{x \to \infty}\frac{n!a_n}{(n+1)!x} = 0 \end{align*}$

Therefore, $p(x)=o(x^{n+1})$ .

Exercise 5 Let $S(n)=\sum\limits_{i=1}^n i$ . Show that $S(n)=O(n^2)$ .

Note that

$S(n)= \sum\limits_{i=1}^ni=\frac{n(n+1)}{2} =\frac{1}{2}n^2+n+\frac{1}{2}$

By (4), $S(n)=O(n^2)$ .

Exercise 6 Let $S(n)=\sum_{i=1}^n i^2$ . Show that $S(n)=O(n^3)$ .

Note that

$S(n)= \sum\limits_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6} =\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n$

By (4), $S(n)=O(n^3)$ .

2.5 Different ways of counting

Exercise 1 Let $X=\{1,2,3,4\}$ . The number of labelled families of subsets of $X$ is $2^{2^4}=65536$ . Determine which of the unlabeled families of subsets are the same:

(a) $\{\{1\},\{2\},\{3,4\}\}$ and $\{\{1\},\{3\},\{2,4\}\}$ .

The permutation $(2\;3)$ in $S_4$ provides a bijection between the labeling, thus they are the same unlabeled family.

(b) $\{\{1\},\{2\},\{3,4\}\}$ and $\{\{1\},\{3\},\{3,4\}\}$ .

Note that $\{3,4\}$ is contained in both families, thus any permutation designating a bijection between the two families must fix $3$ and $4$ . But $\{2\}$ and $\{3\}$ implies that the permutation must also switch $2$ and $3$ , which is impossible. Therefore, they are different unlabeled families.

(c) $\{\{1,2\},\{2,3\}\}$ and $\{\{3,4\},\{2,3\}\}$ .

The permutation $(1\;2\;3\;4)$ in $S_4$ provides a bijection between the two families. Therefore, they are the same unlabeled family.

(d) $\{\{1,2\},\{3,4\}\}$ and $\{\{1,2\},\{2,3\}\}$ .

Note that the first collection contains all unique elements of $X$ and the second does not, this tells us there does not exist a bijection (otherwise there is a bijection between a set with 3 and 4 elements). Therefore, they are different unlabeled families.

Exercise 2 Let $X=\{1,2,3,4\}$ . How many distinct unlabeled families of subsets are there which consist of a $1$ -set and $2$ -set?

There are only two distinguishable cases, when the $1$ -set and $2$ -set share an element of $X$ and when the $1$ -set and $2$ -set don’t share any elements. Thus, there are two unlabeled families.

Exercise 3 How many labeled graphs are there on four vertices?

A graph is determined by its vertices and edges. In this case, the number of vertices is fixed. Note that any edge can be determined by a choice of two vertices (in which order does not matter). Therefore, there are $\frac{4\cdot 3}{2!}=6$ . We can then ask if each of the edges are in the graph or not, thus we have $2^6$ graphs.

Exercise 4 How many unlabeled graphs are there on four vertices and 2 edges?

Begin by selecting any edge. Then, either we can select another edge which does not share an vertex with our first choice or we can select the second edge which shares one vertex. Therefore, there are only two unlabeled graphs when the graph has four vertices and two edges.

2.6 Double counting

Exercise 1 True or False: If the same set is counted in two different ways, the answers are the same.

True. (Imagine if this was not true, we could never give a well-defined answer)

2.7 Appendix on set notation

Let $A=\{1,2,3,4,5\}$ and $B=\{3,4,5,6,7,8\}$ . Find the following:

Exercise 1 $A \cup B$

$A \cup B=\{1,2,3,4,5,6,7,8\}$

Exercise 2 $A \cap B$

$A \cup B=\{3,4,5\}$

Exercise 3 $A \setminus B$

$A \setminus B=\{1,2\}$

Exercise 4 $B \setminus A$

$A \setminus B=\{6,7,8\}$

Exercise 5 $A \triangle B$

$A \setminus B=\{1,2,6,7,8\}$

Exercise 6 $(A \cap B) \times (A \setminus B)$

$(A \cap B) \times (A \setminus B)=\{(3,1),(3,2),(4,1),(4,2),(5,1),(5,2)\}$

Exercise 7 $\vert A \times B \vert$

$\vert A\times B\vert=\vert A \vert \cdot \vert B \vert = 5\cdot 6 = 30$

Exercise 7 $\vert B^n \vert$

$\vert B^n\vert=\vert B \vert ^n = 6^n$

Exercise 8 $\mathcal{P}(A\cap B)$

$\mathcal{P}(A\cap B)=\{\emptyset, \{3\},\{4\},\{5\},\{3,4\},\{3,5\},\{4,5\},A\cap B\}$

Exercise 9 $\vert\mathcal{P}(A\cup B)\vert$

$\vert\mathcal{P}(A\cup B)\vert=2^{\vert A \cup B \vert} = 2^8$

3.1 Subsets

Recall that if $X=\{0,1,\dots,n-1\}$ , then a function $f:X\rightarrow \{0,1\}$ can be represented by an ordered $n$ -tuple $(f(0),f(1),\dots, f(n-1))$ . Therefore, we can associate a base 2 integer to each subset of $X$ . Let $N=f(n-1)\cdot 2^{n-1} + \cdots + f(1)\cdot 2^1 + f(0)\cdot 2^0$ , then we can define $X_N=\{i \in X\;:\; f(i)=1\}$ .

Exercise 1 Let $X=\{0,1,2,3\}$ , which integers represent subsets which contain $X_4$ .

$\begin{align*} 4 &= 2^3\cdot 0 +2^2\cdot 1 + 2^1\cdot 0 + 2^0\cdot 0 \\ 5 &= 2^3\cdot 0 +2^2\cdot 1 + 2^1\cdot 0 + 2^0\cdot 1 \\ 6 &= 2^3\cdot 0 +2^2\cdot 1 + 2^1\cdot 1 + 2^0\cdot 0 \\ 7 &= 2^3\cdot 0 +2^2\cdot 1 + 2^1\cdot 1 + 2^0\cdot 1 \\ 12 &= 2^3\cdot 1 +2^2\cdot 1 + 2^1\cdot 0 + 2^0\cdot 0 \\ 13 &= 2^3\cdot 1 +2^2\cdot 1 + 2^1\cdot 0 + 2^0\cdot 1 \\ 14 &= 2^3\cdot 1 +2^2\cdot 1 + 2^1\cdot 1 + 2^0\cdot 0 \\ 15 &= 2^3\cdot 1 +2^2\cdot 1 + 2^1\cdot 1 + 2^0\cdot 1 \end{align*}$

Therefore, $4,5,6,7,12,13,14$ and $15$ are integers which represent subsets that contain $X_4$ .

3.2 Subsets of fixed size

Exercise 1 Which subset is counted by $\binom{n}{0}$ ?

The empty set $\emptyset$ since we are selecting $0$ elements from a set of $n$ objects.

Exercise 2 Which subset is counted by $\binom{n}{n}$ ?

The whole set since we are selecting $n$ elements from a set of $n$ objects.

Exercise 3 Algebraically prove the following identities:

(a) $\binom{n}{k}=\binom{n}{n-k}$

$\begin{align*} \binom{n}{k}&=\frac{n!}{k!(n-k)!} \\ &=\frac{n!}{(n-k)!k!} \\ &= \binom{n}{n-k} \end{align*}$

(b) $k\binom{n}{k}=n\binom{n-1}{k-1}$

$\begin{align*} k\binom{n}{k}&=k\cdot \frac{n!}{k!(n-k)!} \\ &= \frac{n(n-1)!}{(k-1)!(n-k)!} \\ &= n\cdot \binom{n-1}{k-1} \end{align*}$

(c) $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$

$\begin{align*} \binom{n}{k-1}+\binom{n}{k} &= \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!} \\ &= \frac{k\cdot n!}{k(k-1)!(n-k+1)!} + \frac{n!(n-k+1)}{k!(n-k)!(n-k+1)} \\ &= \frac{k\cdot n! + (n-k+1)\cdot n!}{k!(n-k+1)!} \\ &=\frac{n!\cdot (k+n-k+1)}{k!(n-k+1)!} \\ &= \frac{(n+1)!}{k!(n-k+1)!}=\binom{n+1}{k} \end{align*}$

Exercise 4 Compute:

(a) $\sum\limits_{k=1}^4 \binom{5}{k}$

$\begin{align*} \sum\limits_{k=1}^4 \binom{5}{k}&= -1+\binom{5}{0} + \sum\limits_{k=1}^4 \binom{5}{k} + \binom{5}{5}-1 \\ &= \sum\limits_{k=0}^5\binom{5}{k}-2=2^5-2 \end{align*}$