Question

Prove the following using the method suggested:
(a) Prove the following either by direct proof or by contraposition:
Let a ∈ Z, if a ≡ 3 (mod 5) and b ≡ 2 (mod 5), then ab ≡ 1 (mod 5).

(b) Prove the following by contradiction:
Suppose a, b ∈ Z. If a² + b²
is odd, then (2|a) ⊕ (2|b), where ⊕ is the exclusive disjuntion,
i.e. p ⊕ q = (p ∨ q) ∧ ¬(p ∧ q).

(d) Prove the following by cases: For all n ∈ Z, n
2 + 3(n + 1) is odd.

(e) Prove the following by induction:
For n ≥ 1,
1 × 2 + 2 × 3 + 3 × 4 + · · · + n(n + 1) = n/3
(n + 1)(n + 2)

Answer 1

(a) Given a, b Z, and a 3 (mod 5) and b 2 (mod 5) i.e. (a - 3) is divisible by 5 and (b - 2) is divisible by 5

(b) Given p q = (p ? q) ? ¬(p ? q), i.e. if p is true then q is false and if p is false then q true. Hence, p q is true only if both of p and q do not have same truth value (True or False) simultaneously.

By contradiction, assume that ² + ² is even when 2 divides and 2 does not divides or 2 does not divides and 2 divides . Therefore,  ² + ² = (2n)² + (2m+1)² = 4m² + 4n² + 4m +1 or  (2n+1)² + (2m)² = 4m² + 4n² + 4n +1, which is contradiction as in both cases it is even. Which proves the statement.

(d) Given problem statement is "For all n Z, P(n) : n² + 3(n + 1) is odd."

Basis step: For n = 1, 1² + 3 (1 + 1) = 7, which is odd, therefore P(1) is true.

Induction Step: Let for n = m, the property holds i.e. P(m) is true, therefore.

then for n = m+1, we have

Which is odd by equation (1), as 2 (m+2) is always even.

Therefore, by induction, P(n) : n² + 3(n + 1) is odd,. for all n Z

(e) Given problem statement is For n ? 1,

Basis step: For n = 1, P(1) = 1 x 2 = 2 and 1 (1+1) (2 + 1) = 2, therefore P(1) is true.

Induction Step: Let for n = m, the property holds i.e. P(m) is true, therefore.

then for n = m+1, we have

Which shows that P(m+1) is true.

Therefore, by induction, P(n): holds for all n Z