Show your working and give full explanations for all questions.
(1) Define a sequence of integers a1,a2,a3,... by
a1 = 4, a2 = 12, and an = 10an−1 − 12an−2 for each integer n ≥ 3.
Prove by strong induction that 2n divides an for all integers n ≥ 1.
(2) Let R, S and T be sets defined as follows
R = {x : x ∈ Z and either x ≤ −4 or x ≥ 3} S = {−6,−5,−3,3,4,5}
T = {x : x ∈ Z and x ≥ 0}.
Find the following.
(i) R ∩ S
(ii) R − T
(iii) R4S
(iv) P(R) ∩ {{−6,−5,3},{2,3},{5},{},{−5,1,4}}
(v) |P(P(S ∩ T))|
No explanation is required for (i)–(iv). Give some explanation for (v).
(3) (i) Is (A ∪ B) × C = (A × C) ∪ (B × C) true for all sets A, B and C? If so, prove it. If not, give an example of sets A, B and C for which it is false.
(ii) Is P(A)4P(B) = P(A4B) true for all sets A and B? If so, prove it. If not, give an example of sets A and B for which it is false.
Hint: A good way to prove that two sets are equal is to use laws of logic to show that they have exactly the same elements.
