SC/MATH 1019B - HOMEW ORK 3
DUE NOVEMB ER 20, 2024
Solutions to the problems below must be brought to class on November 20, 2018.
Solutions may by typed or neatly hand written. You must clearly indicate which
problem you are solving. All solutions must be fully justified.
# 1. Let Σ = { a, b, c . Find a recurrence for the number of length n strings in Σ∗
that do not contain
} any two consecutive a’s, b’s, nor c’s (i.e. none of aa, bb, nor cc
are in the string).
Let sn denote the number of string which do not contain any two consecutive a’s,
b’s, nor c’s. For any such string of length n − 1
• if it ends in an a, I can add either b or c;
• if it ends in a b, I can add either a or c;
• if it ends in a c, I can add either a or c;
Thus any string of length n − 1 can be extended to a string of length n in
two possible ways and so an = 2an−1.
# 2. Solve the recurrence an = 5an−1 − 6an−2 where a0 = 2 and a1 = 5.
The characteristic equation is r2 — 5r + 6 = (r −2)(r −
3). So, the solution of the
recurrence is
A2n + B3n
for some constants A and B. Using the initial conditions we find that
A+B =2
2A + 3B = 5
and so A = 1 and B = 1. Therefore an = 2n + 3n.
# 3. Consider the relation R on Z × (Z \ {0}) defined by
R = {((a, b), (c, d)) : ad =
bc}.
Prove that R is an equivalence relation. Does the relation R have any meaning to
you?
Since ab = ba for any (a, b) ∈ Z × (Z \ {0 } ) we find that ((a, b), (a, b)) R and R
is reflexive. ∈
Assuming that ((a, b), (c, d)) ∈ R we have that ad = bc. This also means cb = da
and so ((c, d), (a, b)) ∈ R and R is symmetric.
Assuming that ((a, b), (c, d)) ∈ R and ((c, d), (e, f )) ∈ R we have that
ad = bc cf = de.
Since b
0, d /= 0, and f /= 0 we see that
a c c e
= = .
b d d f
1
DUE NOVEMB ER 20, 2024
Solutions to the problems below must be brought to class on November 20, 2018.
Solutions may by typed or neatly hand written. You must clearly indicate which
problem you are solving. All solutions must be fully justified.
# 1. Let Σ = { a, b, c . Find a recurrence for the number of length n strings in Σ∗
that do not contain
} any two consecutive a’s, b’s, nor c’s (i.e. none of aa, bb, nor cc
are in the string).
Let sn denote the number of string which do not contain any two consecutive a’s,
b’s, nor c’s. For any such string of length n − 1
• if it ends in an a, I can add either b or c;
• if it ends in a b, I can add either a or c;
• if it ends in a c, I can add either a or c;
Thus any string of length n − 1 can be extended to a string of length n in
two possible ways and so an = 2an−1.
# 2. Solve the recurrence an = 5an−1 − 6an−2 where a0 = 2 and a1 = 5.
The characteristic equation is r2 — 5r + 6 = (r −2)(r −
3). So, the solution of the
recurrence is
A2n + B3n
for some constants A and B. Using the initial conditions we find that
A+B =2
2A + 3B = 5
and so A = 1 and B = 1. Therefore an = 2n + 3n.
# 3. Consider the relation R on Z × (Z \ {0}) defined by
R = {((a, b), (c, d)) : ad =
bc}.
Prove that R is an equivalence relation. Does the relation R have any meaning to
you?
Since ab = ba for any (a, b) ∈ Z × (Z \ {0 } ) we find that ((a, b), (a, b)) R and R
is reflexive. ∈
Assuming that ((a, b), (c, d)) ∈ R we have that ad = bc. This also means cb = da
and so ((c, d), (a, b)) ∈ R and R is symmetric.
Assuming that ((a, b), (c, d)) ∈ R and ((c, d), (e, f )) ∈ R we have that
ad = bc cf = de.
Since b
0, d /= 0, and f /= 0 we see that
a c c e
= = .
b d d f
1
