Discrete Math Practice

The negation of $\forall n\, P(n)$ is $\exists n\, \neg P(n)$.

Here $P(n)$ is the implication "if $n$ is prime, then $n$ is odd." The negation of an implication is:

so its negation is:

Therefore the negation is:

Equivalently, there exists an integer $n$ that is prime and even.

For a statement $p \to q$, the contrapositive is $\neg q \to \neg p$.

Here:

• $p$: $n$ is divisible by $4$

• $q$: $n$ is even

So the contrapositive is:

Since integers are either even or odd, this can also be written as:

By De Morgan's law,

So the simplified form is:

The elements common to both sets are $3$ and $5$, so:

The union contains every element that appears in either set:

A set with $n$ elements has $2^n$ subsets.

Here $n=4$, so the number of subsets is

The function is not injective because different inputs can give the same output:

The function is surjective because both elements of the codomain are hit:

So $f$ is surjective but not injective.

For finite sets,

So

Check the three conditions:

• Reflexive: $(1,1)$, $(2,2)$, and $(3,3)$ are all in $R$.

• Antisymmetric: there is no pair $(a,b)$ and $(b,a)$ with $a \neq b$.

• Transitive: $(1,2)$ and $(2,3)$ imply $(1,3)$, and the other required transitive cases are also present.

So $R$ is a partial order.

We need the multiplicative inverse of $2$ modulo $5$.

Since

the inverse of $2$ mod $5$ is $3$. Multiply both sides by $3$:

For a tree with $n$ vertices, the number of edges is

So with $n=14$,

The negation of $\forall n\, P(n)$ is $\exists n\, \neg P(n)$.

The negation of $p \to q$ is $p \land \neg q$.

So the negation is:

Congruence modulo $4$ is:

• Reflexive, because $a \equiv a \pmod 4$

• Symmetric, because if $a \equiv b \pmod 4$, then $b \equiv a \pmod 4$

• Transitive, because if $a \equiv b \pmod 4$ and $b \equiv c \pmod 4$, then $a \equiv c \pmod 4$

So it is an equivalence relation.

The class of $7$ is all integers congruent to $7$ mod $4$, which is the same as all integers congruent to $3$ mod $4$:

Use the contrapositive: prove that if $n$ is odd, then $n^2$ is odd.

If $n$ is odd, then $n = 2k+1$ for some integer $k$. Then

which is odd.

So the contrapositive is true, and therefore the original statement is true.

Base case $n=1$:

so the formula holds.

Inductive step: assume the formula holds for $n=k$:

Then

Factor out $(k+1)$:

This is exactly the formula with $n=k+1$. Therefore the statement holds for all $n \ge 1$.

If one student must be included, choose the other $2$ committee members from the remaining $7$ students.

The number of ways is

Use conditional probability:

In counting form, this is

So the probability is $\frac{4}{7}$.

Use the Euclidean algorithm:

The last nonzero remainder is

So

Compare the ratio:

This ratio grows without bound as $n$ increases, so $n^2$ grows faster.

Equivalently,

but $n^2$ is not $O(n \log n)$.

Count all committees, then subtract those with no captains.

Total committees:

Committees with no captains are chosen from the other $8$ students:

So the number with at least one captain is

There are $12$ months, so there are $12$ boxes.

To avoid having $3$ students in any one month, you can place at most $2$ students in each month:

One more student forces some month to contain at least $3$ students.

So the smallest number is

The probability of rolling an even number is $\frac{1}{2}$, and the probability of rolling an odd number is $\frac{1}{2}$.

So the expected value is

So the expected value is \$1.50.

Days of the week repeat every $7$ days, so compute

So $100$ days from Wednesday is $2$ days later:

Thursday.

The recurrence is

This is a geometric recurrence, so the explicit formula is

Now evaluate at $n=4$:

We use strong induction.

Base case: $n=2$. The number $2$ is prime, so it is already a product of primes.

Inductive step: assume every integer from $2$ through $k$ can be written as a product of primes. We prove the claim for $k+1$.

• If $k+1$ is prime, then it is already a product of primes.

• If $k+1$ is composite, then

for some integers $a,b$ with

By the strong inductive hypothesis, both $a$ and $b$ can be written as products of primes. Multiplying those factorizations gives a product of primes for $k+1$.

Therefore every integer $n \ge 2$ can be written as a product of primes.

Use inclusion-exclusion.

Counts of multiples:

Subtract overlaps:

Add back the triple overlap:

So the total is

First add the degrees:

By the handshaking lemma,

so

A tree with $6$ vertices must have

edges. Since this graph has $6$ edges, it cannot be a tree.

A good loop invariant is:

After the loop has processed the numbers $1,2,\dots,k$, the variable total equals $1+2+\cdots+k$.

Why it works:

• Before the loop starts, total = 0, which matches the sum of no terms.

• Each iteration adds the next integer, so if the invariant is true before an iteration, it remains true after that iteration.

• When the loop finishes, $k=n$, so total equals

Therefore the algorithm is correct.