element x in S 1 but not in S 2 . Then
so that
. The
complete expression can then not be equal to the empty set.
13. If x is in S 1 and x is in S 2 , then x is not in
. Because of this, a
necessary and sufficient condition is that the two sets be disjoint.
17. (c) Since
is the product of factors less than or equal to one. Therefore, n! = O(n n ).
30. An argument by contradiction works. Suppose that
were rational.
Then
gives
contradicting the fact that
is not rational.
33. By induction. Suppose that every integer less than n can be written as a
product of primes. If n is a prime, there is nothing to prove; if not, it can be
written as the product
n = n 1 n 2 ,
where both factors are less than n. By the inductive assumption, they both
can be written as the product of primes, and so can n.
Section 1.2
2. Many string identities can be proven by induction. Suppose that
for all u ∈ Σ * and all v of length n. Take now a string of
length n + 1, say w = va. Then