Logic, Proofs and Discrete Math: math test solutions, College – download the PDF

1 Logic / 3 pts

(a) (2 pts)

The last two columns agree in every row, so the statements are equivalent.

(b) (1 pt) “There exists a real number \(x\) such that for every integer \(n\), \(n\le x\).”

2 A proof / 3 pts

The contrapositive is: if \(n\) is even, then \(n^2\) is even. (1 pt)

If \(n=2k\), then \(n^2=4k^2=2(2k^2)\), which is even. (1 pt)

Since the contrapositive is true, the original statement is true. (1 pt)

3 Induction / 4 pts

Base (1 pt): for \(n=1\), the left side is 1 and the right side is \(\dfrac{1\cdot2\cdot3}{6}=1\).

Hypothesis (1 pt): assume the formula holds for some \(n\ge1\).

Step (1.5 pts): adding \((n+1)^2\) gives \(\dfrac{n(n+1)(2n+1)}6+(n+1)^2=\dfrac{(n+1)\,[\,n(2n+1)+6(n+1)\,]}6=\dfrac{(n+1)(2n^2+7n+6)}6=\dfrac{(n+1)(n+2)(2n+3)}6\), which is the formula for \(n+1\).

Conclusion (0.5 pt): the formula holds for all \(n\ge1\).

4 Sets and functions / 3 pts

(a) (1 pt) Multiples of 2: 6; multiples of 3: 4; multiples of 6: 2. So \(6+4-2=8\) integers.

(b) (1 pt) Each of the 3 inputs has 4 possible outputs: \(4^3=64\) functions.

(c) (1 pt) Injective: outputs must be distinct: \(4\cdot3\cdot2=24\) functions.

5 Counting and graphs / 4 pts

(a) (1 pt) Order matters: \(9\cdot8\cdot7=504\).

(b) (1 pt) \(C(9,4)=\dfrac{9\cdot8\cdot7\cdot6}{24}=126\).

(c) (1 pt) \(\dfrac{6\cdot5}2=15\) edges.

(d) (1 pt) The degree sum is \(3+3+3+3+2+2=16\), so the graph has \(16/2=8\) edges.

6 A recurrence / 3 pts

(a) (1 pt) \(a_1=5\), \(a_2=13\), \(a_3=29\).

(b) Base (0.5 pt): \(2^{2}-3=1=a_0\). Step (1 pt): if \(a_n=2^{n+2}-3\), then \(a_{n+1}=2(2^{n+2}-3)+3=2^{n+3}-3\). Conclusion (0.5 pt): the formula holds for all \(n\ge0\).