SC/MATH 10 19B - HOMEW OR K 2
DUE OCTOB ER 23, 2024
Solutions to the problems below must be brought to class on October,23 2018. Solu-
tions may by typed or neatly hand written. You must clearly indicate which problem
you are solving. All solutions must be fully justified.
# 1.
(a) Given an example of a function f : N → N which is injective but not
surjective.
(a) Given an example of a function g : N → N which is surjective but not
injective.
An example of an injective but not surjective function is f : N → N by f (n) = n+5.
If f (n1) = f (n2), then n1 + 5 = n2 + 5 and so n1 = n2. Therefore f is injective.
To see that f is not surjective consider 1 ∈ N (the codomain). If f (n) = 1,
then n + 5 = 1 and n = −4. However, −4 /∈ N (the domain) so f is not
surjective.
An example of a surjective but not injective function is g : N → N by g(n) =
[n/2♩. Indeed for any n ∈ N (the codomain) take 2n ∈ N (the domain) and
g(2n) = n. The function g is not injective since g(2) = 1 = g(3) but 2 /= 3.
# 2. Let A, B, and C be nonempty sets. Let f : A → B and g : B → C be
functions. Show that if g ◦ f is one-to-one, then f must be one-to-one. Is it
true that g must also be one-to-one?
Let us use proof by contrapositive. Assume that f is not one-to-one. Then there
exists a1, a2 ∈ A with a1 /= a2 such that f (a1) = f (a2). This means
(g ◦ f )(a1) = g(f (a1)) = g(f (a2)) = (g ◦ f )(a2)
and g ◦ f is not one-to-one.
To see an example where g ◦ f is one-to-one, but that g is not one-to-one tkae
A = {0}, B = Z, and C = {0} with f (0) = 0 and g(n) = 0 for n ∈ Z. Then g is
not one-to-one since g(0) = 0 = g(1), but g ◦ f : {0} → {0} is one-to-one.
# 3. Solve the recurrence relation given by a1 = 2 and an = 2nan−1 for n > 1.
We claim that an = 2nn!. Indeed a1 = 2 = 211!. Assume that an = 2nn! for some
n ≥ 1, then
an+1 = 2(n + 1)an = 2n(2nn!) = 2n+1(n + 1)!.
1
DUE OCTOB ER 23, 2024
Solutions to the problems below must be brought to class on October,23 2018. Solu-
tions may by typed or neatly hand written. You must clearly indicate which problem
you are solving. All solutions must be fully justified.
# 1.
(a) Given an example of a function f : N → N which is injective but not
surjective.
(a) Given an example of a function g : N → N which is surjective but not
injective.
An example of an injective but not surjective function is f : N → N by f (n) = n+5.
If f (n1) = f (n2), then n1 + 5 = n2 + 5 and so n1 = n2. Therefore f is injective.
To see that f is not surjective consider 1 ∈ N (the codomain). If f (n) = 1,
then n + 5 = 1 and n = −4. However, −4 /∈ N (the domain) so f is not
surjective.
An example of a surjective but not injective function is g : N → N by g(n) =
[n/2♩. Indeed for any n ∈ N (the codomain) take 2n ∈ N (the domain) and
g(2n) = n. The function g is not injective since g(2) = 1 = g(3) but 2 /= 3.
# 2. Let A, B, and C be nonempty sets. Let f : A → B and g : B → C be
functions. Show that if g ◦ f is one-to-one, then f must be one-to-one. Is it
true that g must also be one-to-one?
Let us use proof by contrapositive. Assume that f is not one-to-one. Then there
exists a1, a2 ∈ A with a1 /= a2 such that f (a1) = f (a2). This means
(g ◦ f )(a1) = g(f (a1)) = g(f (a2)) = (g ◦ f )(a2)
and g ◦ f is not one-to-one.
To see an example where g ◦ f is one-to-one, but that g is not one-to-one tkae
A = {0}, B = Z, and C = {0} with f (0) = 0 and g(n) = 0 for n ∈ Z. Then g is
not one-to-one since g(0) = 0 = g(1), but g ◦ f : {0} → {0} is one-to-one.
# 3. Solve the recurrence relation given by a1 = 2 and an = 2nan−1 for n > 1.
We claim that an = 2nn!. Indeed a1 = 2 = 211!. Assume that an = 2nn! for some
n ≥ 1, then
an+1 = 2(n + 1)an = 2n(2nn!) = 2n+1(n + 1)!.
1
