Practice Exam 3

$S=\{2,5,8,11,14,\dots \}$: three applications of the rule take $2\to 5\to 8\to 11$.

$7$ isn't a multiple of 3, $7-5=2$ isn't either, and there's no room for two 5s. That's why the 3/5 stamp proof starts at $n=8$.

$\mathbb{Z}$ itself (or the negative integers) has no least element. The well-ordering property is about nonnegative integers.

Symmetry: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-r}\right)$ and $12-9=3$.

Functions $A\to B$: $|B{|}^{|A|}=4^3=64$. ($81=3^4$ has the exponent backwards.)

13 people (pigeons), 12 months (holes). $13>12$.

$\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$.

Repetition allowed: $\left(\genfrac{}{}{0ex}{}{5+3-1}{3}\right)=\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$.

$f(1)=6-1=5$, $f(2)=15-1=14$, $f(3)=42-1=41$.

The set is $1,5,9,13,\dots$: start at 1, add the period 4. (A) gives all of ${\mathbb{Z}}^{+}$; (B) gives $1,4,16,\dots$; (D) gives $4,5,6,\dots$

Structural induction: 2 is even, and the sum and product of even numbers are even. (C) fails: $2+4=6\in S$. (D) fails: $2\cdot 2=4\in S$.

From the two structural-induction facts: $n(T)\le 2^{h+1}-1$ and $n(T)\ge 2h+1$.

• $h=2$: at most $2^3-1=7<9$ vertices. Impossible.
• $h=4$: need $9\ge 9$ ✓ (a "caterpillar" tree).
• $h=3$: e.g. a root with a complete height-2 subtree (7 vertices) and a single leaf: $1+7+1=9$ ✓.

$l(T)=i(T)+1=11$ (5.3 #46).

$A(1,3)=A(0,A(1,2))=2A(1,2)$, $A(1,2)=A(0,A(1,1))=A(0,2)=4$, so $A(1,3)=8=2^3$.

$2^7+2^6-2^5=128+64-32=160$.

$\lfloor 120/4\rfloor +\lfloor 120/6\rfloor -\lfloor 120/12\rfloor =30+20-10=40$. Use $\mathrm{lcm}(4,6)=12$.

$k=4$ suits, $r=4$: $k(r-1)+1=4\cdot 3+1=13$. (12 cards could be 3 of each suit.)

Units: [AB], [CD], E, F, which is 4 units, so $4!=24$.

General term $\left(\genfrac{}{}{0ex}{}{5}{j}\right)(2x{)}^j(-1{)}^{5-j}$. With $j=3$: $\left(\genfrac{}{}{0ex}{}{5}{3}\right)\cdot 8\cdot (-1{)}^2=10\cdot 8=80$.

Give 2 to $x_1$ first, leaving 8 for 3 variables: $\left(\genfrac{}{}{0ex}{}{8+2}{2}\right)=\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$.

B×1, A×3, N×2: $\frac{6!}{3!2!}=\frac{720}{12}=60$.

Binomial theorem with $x=1$, $y=2$: $(1+2{)}^6=3^6=729$.

Let $P(n)$: "$n$ cents of postage can be formed using only 5¢ and 6¢ stamps."

(a) Basis step. The inductive step will add a 5¢ stamp, so we need 5 consecutive base cases:

• $20=5+5+5+5$
• $21=5+5+5+6$
• $22=5+5+6+6$
• $23=5+6+6+6$
• $24=6+6+6+6$

(b) Inductive hypothesis. Let $k\ge 24$ be arbitrary. Assume $P(j)$ is true for every integer $j$ with $20\le j\le k$.

(c) Inductive step. We show $P(k+1)$. Since $k\ge 24$, we have $20\le k-4\le k$, so by the IH $k-4$ cents can be formed. Adding one 5¢ stamp gives $(k-4)+5=k+1$ cents, so $P(k+1)$ is true.

By strong induction, $P(n)$ is true for every integer $n\ge 20$. ∎

Grading notes: −2 for fewer than 5 base cases; −2 if the IH is only $P(k)$; −1 for not justifying $k-4\ge 20$.

(a) $f(2)=2(3)+1=7$; $f(3)=2(7)+3=17$; $f(4)=2(17)+7=41$; $f(5)=2(41)+17=99$.

(b) Basis: $a_0=5^0+1=2$. Recursive step: $a_{n+1}=5^{n+1}+1=5\cdot 5^n+1=5(a_n-1)+1=5a_n-4$.
So $a_0=2$ and $a_{n+1}=5a_n-4$ for $n\ge 0$. (Check: $2\to 6\to 26\to 126$ ✓)

(c) The set is $1,2,3,5,6,7,9,10,11,\dots$ (period 4). Basis: $1,2,3\in S$. Recursive: if $x\in S$ then $x+4\in S$.

(a) First application: $(1,3)$, $(3,1)$.
Second application: from $(1,3)$: $(2,6)$, $(4,4)$; from $(3,1)$: $(4,4)$, $(6,2)$. New: $(2,6),(4,4),(6,2)$.

(b)

• Basis step: $(0,0)$: $0+0=0$ and $4\mid 0$. ✓
• Recursive step: Assume $(a,b)\in S$ and $4\mid (a+b)$ (IH). Check both rules:
  • $(a+1)+(b+3)=(a+b)+4$. Since $4\mid (a+b)$ and $4\mid 4$, $4$ divides the sum. ✓
  • $(a+3)+(b+1)=(a+b)+4$, divisible by 4 for the same reason. ✓

By structural induction, $4\mid (a+b)$ for all $(a,b)\in S$. ∎

(a) Basis: ${\lambda }^R=\lambda$. Recursive: for $w\in {\Sigma }^{\ast }$ and $x\in \Sigma$, $(wx{)}^R=x{w}^R$.

(b) Let $P(w)$: $l(w^R)=l(w)$.

• Basis: $l({\lambda }^R)=l(\lambda )$, since ${\lambda }^R=\lambda$. ✓
• Recursive step: assume $l(w^R)=l(w)$ (IH) and let $x\in \Sigma$. Then
  $$\begin{array}{rlrl}l((wx{)}^R)& =l(x{w}^R)& & \text{definition of reversal}\\ & =l(x)+l(w^R)& & l(uv)=l(u)+l(v)\\ & =1+l(w)& & l(x)=1\text{ and the IH}\\ & =l(wx)& & \text{definition of length}.\end{array}$$

By structural induction, $l(w^R)=l(w)$ for all strings $w$. ∎

(a) Titled positions, so order matters: $P(12,3)=12\cdot 11\cdot 10=1320$.

(b) $\left(\genfrac{}{}{0ex}{}{7}{3}\right)\left(\genfrac{}{}{0ex}{}{5}{2}\right)=35\cdot 10=350$.

(c) Complement (all-senior committees): $\left(\genfrac{}{}{0ex}{}{12}{5}\right)-\left(\genfrac{}{}{0ex}{}{7}{5}\right)=792-21=771$.

(d) Gap method: line up the 7 seniors ($7!$), creating 8 gaps; place the 5 juniors in 5 distinct gaps in order ($P(8,5)=8\cdot 7\cdot 6\cdot 5\cdot 4=6720$). Total $7!\cdot P(8,5)=5040\cdot 6720=33,868,800$.

(a) Pigeons: the 6 integers. Holes: the remainders mod 5, $\{0,1,2,3,4\}$, which is 5 holes. Since $6>5$, two integers $a,b$ have the same remainder $r$: $a=5q_1+r$, $b=5q_2+r$. Then $a-b=5(q_1-q_2)$ is divisible by 5. ∎

(b)

• (i) 3 colors: $3(2-1)+1=4$.
• (ii) $3(3-1)+1=7$. (Six socks could be 2 of each color.)
• (iii) Specific color, so think worst case: all 10 red and 6 green first (16), then 2 blue: $18$.

(a) General term $\left(\genfrac{}{}{0ex}{}{7}{j}\right)(3x{)}^{7-j}(-2y{)}^j$. With $j=2$:
$$\left(\genfrac{}{}{0ex}{}{7}{2}\right)3^5(-2{)}^2=21\cdot 243\cdot 4=20,412.$$

(b) Give 2 of each kind first ($12$ donuts), leaving $3$ to choose freely from 6 kinds: $\left(\genfrac{}{}{0ex}{}{6+3-1}{3}\right)=\left(\genfrac{}{}{0ex}{}{8}{3}\right)=56$.

(c) All solutions: $\left(\genfrac{}{}{0ex}{}{23}{3}\right)=1771$. Bad ones ($x_1\ge 5$): give 5 to $x_1$, leaving 15: $\left(\genfrac{}{}{0ex}{}{18}{3}\right)=816$. Answer: $1771-816=955$.

(a) By the binomial theorem, $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$. Set $x=1$, $y=2$:
$$3^n=(1+2{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})1^{n-k}{2}^k=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})2^k.$$ ∎

(b) T×1, E×4, N×2, S×2 (9 letters): $\frac{9!}{1!4!2!2!}=\frac{362,880}{96}=3780$.