Question 1 :
Show by induction that for every value of n >= 2 and for every value d >= 2
d divide n(n + 1)(n + 2). . .(n + d − 1)
Question 2 :
Let us consider the following relations on Z. For each one of them, you must say if it is
reflexive, irreflexive, symmetrical, antisymmetric, transitive, of equivalant. You must justify.
R1 : {(a, b) | b = 0}
R2 : {(a, b) | |a| = |b|}
R3 : {(a, b) | a ≡ b (mod 11)}
R4 : {(a, b) | a = b + 7}
R5 : {(a, b) | (a = 0 b = 0) PGCD(a, b) = 5} ∧ ∨
Question 3 :
Let N + be the set of natural numbers different from 0 (also denoted N *). We
define the following relation R on the pairs N + × N +:
[(a, b),(c, d)] ∈ R if ad = bc
a) Give a detailed description of all the pairs (c, d) that are related to the pair (1, 2).
b) Demonstrate that the relation R is an equivalence relation.
c) What is the number of equivalence classes generated by the relation R? What is the size
of each equivalence class?
Question 4 :
Let S be the set of strings on the alphabet A = {R, O, N} defined recursively by the following
rules where x and y are (potentially empty) strings on A
(r0) RO S ∈
(r1) Si xO S alors xON S ∈ ∈
(r2) Si Rx S alors Rxx S ∈ ∈
(r3) Si xOOOy S alors xNy S ∈ ∈
(r4) Si xNNy S alors xy S ∈ ∈
- String construction of S
Step 1. What are the new strings obtained by applying all possible rules to RO? For
each one , indicate the rule used to obtain it.
Step 2. What are the new strings obtained by applying all the possible rules to the
strings created in step 1? For each one, indicate the rule used to obtain it.
Step 3 What are the new strings obtained by applying all the possible rules to the
strings created in step 2? For each one, indicate the rule used to obtain it.
2.
a. With the strings obtained in Step 3, which are the ones on which Rule 3 applies?
b. What are the strings obtained by applying rule 3 to 2) strings a. ?
c. Apply, when it’s possible, rule 4 to the strings obtained in 2) b. What do we notice?
3.
Show that the string RNOON S indicating which rules should be applied to obtain ∈
this chain.
4.
Show by induction that the number of O’s in a non-empty string belonging to S is never
a multiple of 3. Use this result to determine if RN belongs to S.