Mandatory Assignment 01 Solutions

lOMoARcPSD|5343815
Mandatory Assignment 01 - Solutions
Introduction to Theory of Computation (Carleton University)
StuDocu is not sponsored or endorsed by any college or university

Downloaded by Nzm Ay ([email protected])
lOMoARcPSD|5343815
COMP 3803 - Assignment 1 Solutions
January 30, 2015
1. Q: Prove that the sum of n real numbers if rational if all of them are
rational. Is the converse true? Prove or disprove that the product of
n real numbers is rational (resp. irrational) if all of them are rational
(resp. irrational).
A: We will prove the first part by induction. Of course, the base case is
trivial: the sum of a single rational number is clearly rational. Then,
suppose that the sum of n rational numbers is always rational. Given
n + 1 rational numbers ab11 , ab22 , . . . , abn+1
n+1
, their sum is:
a1 a2 an an+1
+ + ... + +
b1 b2 bn bn+1
By the induction hypothesis, the sum of the first n of these numbers
is some rational number pq , so the above expression is:
p an+1 pbn+1 + qan+1
= + =
q bn+1 qbn+1
which is rational. So by induction, the sum of n rational numbers is
rational.
The converse is not necessarily true, i.e. if a number is rational,
√ it
√ is
not necessarily only a sum of rational numbers, e.g. 0 = − 2 + 2.
Finally, a product of rational numbers is clearly rational (by multi-
plying all numerators together and all denominators together), but
a√ product
√ of irrational numbers need not be irrational. Indeed,
2 ∗ 2 = 2.
2. Q: Prove that if n is a positive integer, then n is odd if and only if 5n + 6
is odd.

lOMoARcPSD|5343815
A: First, suppose that n is an odd positive integer, so n = 2k + 1 for

some integer k ≥ 0. Then:
5n + 6 = 5(2k + 1) + 6 = 10k + 11 = 2(5k + 5) + 1
So 5n + 6 has the form 2ℓ + 1 for some integer ℓ – in other words,

5n + 6 is odd.
Conversely, suppose that 5n + 6 is odd, so 5n + 6 = 2k + 1 for some
integer k ≥ 0. Then:
2k
5n + 6 = 2k + 1 ⇒ 5n = 2k − 5 ⇒ n = −1
5
k
Since n is known to be an integer, then 5|2k, so 5|k, and 5
= ℓ is an
integer, whereby n = 2ℓ − 1 is odd.
3. Q: Show by induction that n5 − n is divisible by 5 for all n ≥ 0.

A: For the base case, n = 0, 05 − 0 = 0 is divisible by 5.
Suppose n5 − n is divisible by 5 for some n ≥ 0 – in other words,
n5 − n = 5k for some integer k. Then:
(n + 1)5 − (n + 1) = (n5 + 5n4 + 10n3 + 10n2 + 5n + 1) − (n + 1)

= (n5 − n) + 5(n4 + 2n3 + 2n2 + n)
= 5k + 5(n4 + 2n3 + 2n2 + n)
which is clearly divisible by 5. Thus, by induction, n5 − n is divisible

by 5 for all n ≥ 0.
4. Q: Show by induction that n3 − n is divisible by 3 for all n ≥ 0.

A: The solution is identical to that of the previous problem. For the base
case, n = 0, 03 − 0 = 0 is divisible by 3.
Suppose n3 − n is divisible by 3 for some n ≥ 0 – in other words,
n3 − n = 3k for some integer k. Then:
(n + 1)3 − (n + 1) = (n3 + 3n2 + 3n + 1) − (n + 1)

= (n3 − n) + 3(n2 + n)
= 3k + 3(n2 + n)

lOMoARcPSD|5343815
which is clearly divisible by 3. Thus, by induction, n3 − n is divisible

by 3 for all n ≥ 0.
Remark. Just some extra information if you are curious! You don’t need to
know anything about this, but you may find it interesting.
The previous two questions hint at a pattern: is it true that nk −n is divisible
by k for every k ≥ 2 and n ≥ 0? We can easily verify that this is not always
the case: indeed, 24 − 2 = 14 which is not divisible by 4.
However, if p is prime, then np − n is always divisible by p. We only need a
basic algebraic fact to prove this – the so-called “freshman’s dream” – that
if p is prime, then for any integers x and y:
(x + y)p ≡ xp + y p (mod p)
Now, to show that np − n is divisible by p, we proceed by induction as before.

The base case is trivial, so we assume the induction hypothesis, and by the
“freshman’s dream”:
(n + 1)p − (n + 1) ≡ np + 1p − n − 1 = np − n (mod p)
Since we’ve assumed that np −n ≡ 0 (mod p), then we are done by induction.
This result is known as Fermat’s little theorem, and its more general form is
seen in Euler’s theorem.
5. Q: We had shown in class that the set of real numbers in the interval
[0, 1] is uncountable. What can you then say about the cardinality
of the set of real numbers in the interval [0.5, 0.6]? If it is countable,
why is it? If it is uncountable, present the arguments in the same
way we did the proof for the interval [0, 1]. Given what was taught
in class, could you have come up with an easier proof?
A: You are asked to present a similar argument to the one shown in class:
such an argument is called a diagonalisation, or a diagonal argument.
We proceed by contradiction. Suppose [0.5, 0.6] is countable. Then,
we can exhaustively enumerate its elements in a sequence s1 , s2 , . . ..

lOMoARcPSD|5343815
We represent each si in decimal as follows:

s1 = 0.5s11 s12 s13 . . .
s2 = 0.5s21 s22 s23 . . .
s3 = 0.5s31 s32 s33 . . .
..
.
Then, I claim that there exists an element t ∈ [0.5, 0.6] which is never
listed in the above sequence. Indeed, let:
t = 0.5t1 t2 t3 . . .
where t1 ̸= s11 , t2 ̸= s22 , . . ., and in general, tn is chosen so that
tn ̸= snn . It is a fact that t is never listed: suppose t = sn for some
n. Then t1 = sn1 , t2 = sn2 , . . ., tn = snn , but t was chosen precisely
so that tn ̸= snn .
So, in conclusion, if [0.5, 0.6] were countable, we could exhaustively
enumerate its elements, but this enumeration allows us to construct a
number in [0.5, 0.6] which could not possibly be listed in the enumer-
ation. Thus, by contradiction, [0.5, 0.6] must be uncountable.
Remark. There is a simpler proof: define the function f as follows:
f : [0, 1] → [0.5, 0.6]
x 7→ 0.1 ∗ x + 0.5
f is a bijection, so [0, 1] is uncountable if and only if [0.5, 0.6] is
uncountable.
6. Q: Let A be the set of all even natural numbers, and B be the set of
natural numbers divisible by 3. Prove that the set of fractions ab
where a ∈ A and b ∈ B is countable.
A: We will say C = { ab : a ∈ A, b ∈ B}. The task is to show that C is
countable.
Clearly A and B are countable as subsets of the natural numbers,
which by definition is a countable set. Thus, A × B is also countable.
Each pair (a, b) ∈ A × B exhaustively maps to an element ab ∈ C, so
C is countable. Formally, here we have constructed a surjection (or
surjective mapping, also sometimes called an onto mapping), A ×
B → C.

lOMoARcPSD|5343815
Remark. Again, a simple observation makes this a proof exceedingly

easy. Note that C is a subset of the rationals, which is a countable
set, so C must be countable.
7. Q: For arbitrary strings X and Y , show that (XY )R = Y R · X R , where,

by notation, V R is the string obtained by reversing the string V .
A: If X = x1 x2 . . . xi , Y = y1 y2 . . . yj , then:
X R = xi xi−1 . . . x1
Y R = yj yj−1 . . . y1
XY = x1 x2 . . . xi y1 y2 . . . yj
(XY )R = yj yj−1 . . . y1 xi xi−1 . . . x1
Y R X R = yj yj−1 . . . y1 xi xi−1 . . . x1
So (XY )R = Y R X R .
8. Q: For any language A, let AR be {X R : X ∈ A}. Then, for arbi-

trary languages A and B, show that (AB)R = BR · AR , and that
(A ∪ B)R = AR ∪ BR . Your arguments must be brief but accurate.
A: For (AB)R , by definition:
(AB)R = {X R : X ∈ AB} = {(XY )R : X ∈ A, Y ∈ B}

= {Y R X R : X ∈ A, Y ∈ B}
= {Y R : Y ∈ B} · {X R : X ∈ A} = BR AR
For (A ∪ B)R , by definition:
(A ∪ B)R = {X R : X ∈ A ∪ B} = {X R : X ∈ A or X ∈ B}
= {X R : X ∈ A} ∪ {X R : X ∈ B} = AR ∪ BR
9. Q: If the languages A and B are countably infinite and we use the nota-
tion of Question 8, what can you say about the size of the language
obtained by concatenating (AB)R and (A∪B)R . Is the size of the set
(AB)R · (A ∪ B)R any larger or smaller than the size of the language
obtained by concatenating BR and AR ?

lOMoARcPSD|5343815
A: We first show that if the language A is countable, then AR is count-

able. Indeed, each string X ∈ A corresponds exactly to one string
X R ∈ A, so A is countable if and only if AR is countable. Moreover,
if either one is countably infinite, then so is the other.
Recall also that the concatenation of countably infinite languages
results in a countably infinite language.
So, from the previous problem, (AB)R is countably infinte since AB
is countably infinite. Similarly, (A ∪ B)R is countably infinite since
A ∪ B is countably infinite.
Since A and B are countably infinite, then by the above observations,
(AB)R · (A ∪ B)R is countably infinite and BR · AR is countably
infinite, so they are both of equal cardinality..

Mandatory Assignment 01 Solutions

Uploaded by

Copyright:

Available Formats

Mandatory Assignment 01 Solutions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mandatory Assignment 01 Solutions

Uploaded by

Copyright:

Available Formats

lOMoARcPSD|5343815

Mandatory Assignment 01 - Solutions

Introduction to Theory of Computation (Carleton University)

StuDocu is not sponsored or endorsed by any college or university

COMP 3803 - Assignment 1 Solutions

January 30, 2015

Downloaded by Nzm Ay ([email protected])

A: First, suppose that n is an odd positive integer, so n = 2k + 1 for

5n + 6 = 5(2k + 1) + 6 = 10k + 11 = 2(5k + 5) + 1

So 5n + 6 has the form 2ℓ + 1 for some integer ℓ – in other words,

3. Q: Show by induction that n5 − n is divisible by 5 for all n ≥ 0.

(n + 1)5 − (n + 1) = (n5 + 5n4 + 10n3 + 10n2 + 5n + 1) − (n + 1)

which is clearly divisible by 5. Thus, by induction, n5 − n is divisible

4. Q: Show by induction that n3 − n is divisible by 3 for all n ≥ 0.

(n + 1)3 − (n + 1) = (n3 + 3n2 + 3n + 1) − (n + 1)

Downloaded by Nzm Ay ([email protected])

which is clearly divisible by 3. Thus, by induction, n3 − n is divisible

Now, to show that np − n is divisible by p, we proceed by induction as before.

Downloaded by Nzm Ay ([email protected])

We represent each si in decimal as follows:

Downloaded by Nzm Ay ([email protected])

Remark. Again, a simple observation makes this a proof exceedingly

7. Q: For arbitrary strings X and Y , show that (XY )R = Y R · X R , where,

8. Q: For any language A, let AR be {X R : X ∈ A}. Then, for arbi-

(AB)R = {X R : X ∈ AB} = {(XY )R : X ∈ A, Y ∈ B}

For (A ∪ B)R , by definition:

Downloaded by Nzm Ay ([email protected])

A: We first show that if the language A is countable, then AR is count-

Downloaded by Nzm Ay ([email protected])

You might also like