Please type answers!! 1. Prove the following statements.[10 points each] (a) Let
ID: 3121249 • Letter: P
Question
Please type answers!!
1. Prove the following statements.[10 points each]
(a) Let A, B, C and D be four sets. If A B and C D then (A C) (B D).
(b) Prove that {14n : n Z} {2n : n Z} {7n : n Z}.
2. Prove by mathematical induction that 3 | (52m 1) for any integer m 0. [10 points]
3. [10 points] Prove, by induction, that for all intergers n 1, 1 · 2 + 2 · 3 + 3 · 4 + 4 · 5 + · · · + n(n + 1) = n(n + 1)(n + 2) 3
4. A sequence is defined by a1 = 6, a2 = 22 and an = 6an1 7an2 for each integer n 3. [10 points]
(a) Find a6.
(b) Using strong induction, prove that an = (3+ 2)n + (3 2)n for every positive integer n. 5. Each of the following statement is either true or false. If a statement is true, prove it. If a statement is false, disprove it. [10 points each] (a) Suppose a, b, c Z. If a|bc then a|b and a|c. (b) Let x, y R. If |x y| = |x + y|, then y = 0.
(c) There exists prime numbers p and q such that p q = 97.
(d) Every odd integer is the sum of three odd integers. (e) For every natural number n, the integer n 2 + 17n + 17 is prime.
6. Throughout this problem, x and y are both integers.[10 points]
(a) Is “x y, x2 + y 2 = 1” TRUE or FALSE? Explain briefly.
(b) Is “x y, x2 + y 2 = 1” TRUE or FALSE? Explain briefly.
(c) Is “x y, x2 + y 2 = 1” TRUE or FALSE? Explain briefly.
(d) Is “x y, x2 + y 2 = 1” TRUE or FALSE? Explain briefly
Explanation / Answer
Solution
Back-up Theory
To prove A B, we need to prove that x A => x B. ………………(1)
x A B <=> x A or x B or x A B …………….. (2)
If A B, by (1) and (2), x A B <=> x A …………….. (3)
x A B <=> x A and x B …………….. (4)
Now, to work out solution,
Q1 Part (a)
If A B and C D then, to prove (A C) (B D).
Let x A C. Then, [vide (2) and (3) under Back-up Theory], x A or x C
=> x B or x D [because A B and C D]
=> [vide (2) under Back-up Theory], x BD
=> [vide (1) under Back-up Theory], (A C) (B D) PROVED
Q1 Part (b)
Prove that {14n : n Z} {2n : n Z} {7n : n Z}.
Let A = {x: x = 14n, n Z}, B = {x: x = 2n, n Z} and C = {x: x = 7n, n Z}.
Let x A. => x is an integral multiple of 14 which in turn is a product of 2 and 7. Since 2 and 7 are co-prime, x is an integral multiple of 14 => x is an integral multiple of 2 and x is an integral multiple of 7
=> x B and x C => x B C [vide (4) under Back-up Theory]
i.e., {2n : n Z} {7n : n Z}. So, [vide (1) under Back-up Theory],
{14n : n Z} {2n : n Z} {7n : n Z} PROVED