1.Show that for any natural number n, 7 | n^ 7 - n. 2. Show that for any natural

Question

1.Show that for any natural number n, 7 | n^ 7 - n.

2. Show that for any natural number n, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6

3. Show that if f:X -->Y and g: Y --> Z are injective functions, then g o f is injective. Prove the same assertion for surjective and bijective functions.

4. (a) Show that (P -->Q) & <-->(not Q --> not P)

(b) Show that A subset of B if and only if B^c subset of A^c.

Explanation / Answer

1) If n = 1, then 7 | 1^7 - 1. Assume for some k, 7 | k^7 - k. Then (k+1)^7 - (k+1) = k^7 + 7k^6 + 21k^5 + 35k^4 + 35k^3 + 21k^2 + 7k + 1 - k - 1 (binomial expansion) = [k^7 - k] + 7(k^6 + 3k^5 + 5k^4 + 5k^3 + 3k^2 + k) = 7m + 7(k^6 + 3k^5 + 5k^4 + 5k^3 + 3k^2 + k) for some natural number m since 7 divides k^7 - k = 7(m+ k^6 + 3k^5 + 5k^4 + 5k^3 + 3k^2 + k) Therefore for any natural number n, 7 | n^7 - n 2) Let n = 1, then 1^2 = 1 and 1(1+1)(2*1 + 1)/6 = 1. So the base case holds. Assume for some k, 1^2 + 2^2 + ... + k^2 = k(k+1)(2k+1)/6. Then 1^2 + 2^2 + ... + k^2 + (k+1)^2 = k(k+1)(2k+1)/6 + (k+1)^2 = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)[2k^2 + k + 6k + 6]/6 = (k+1)[2k^2 + 7k + 6]/6 = (k+1)(k+2)(2k+3)/6 = (k+1)((k+1)+1)(2(k+1)+1)/6 Therefore by induction, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6 for any natural number n. 3) Let x,y be in X. Assume g(f(x)) = g(f(y)) Then f(x) = f(y) since g is injective. Then x = y since f is injective. Therefore gof is injective. For all z in Z, there exists y in Y such that g(y) = z since g is surjective. Then there exists x in X such that f(x) = y since f is surjective. Thus g(f(x)) = z and therefore gof is surjective. Composition of bijective functions is bijective just follows from the composition of injective & surjective functions being injective & surjective, respectively. 4) (a) Assume P => Q and ~Q. Assume P, then we get Q by modus ponens. This is a contradiction since we have Q and ~Q, therefore we get ~P. Therefore ~Q => ~P. Now assume ~Q => ~P and P. Assume ~Q, then we get ~P by modus ponens. This is a contradiction since we have ~p and P, therefore we get Q. Therefore P => Q and hence (P => Q) (~Q => ~P) ^This is called the contrapositive (b) Assume A ? B. Let x be in B^c. Then x can't be in B implying that x can't be in A since A ? B. Therefore x is in A^c and we get B^c ? A^c. Now assume B^c ? A^c. Let y be in A. Then y can't be in A^c implying that y can't be in B^c since B^c ? A^c. Therefore y is in B and we get A ? B. Therefore A ? B if and only if B^c ? A^c

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.