Discrete Mathematics

MATH 2203: Discrete Mathematics Winter 2015 Assignment 5 Due in class, Wednesday, March 18 1. Prove each of the following statements by mathematical induction. (a) For any integer n ≥ 0, 1 + 3n ≤ 4 n . (b) For any integer n ≥ 1, 8n − 3 n is divisible by 5. (c) If r 6= 1 is a fixed real number, then for any integer n ≥ 0, Xn i=0 r i = 1 − r n+1 1 − r . 2. What is wrong with the “proof” of the following statement? Theorem. All dogs are of the same colour. “Proof.” We will prove by induction that in any collection of n ≥ 1 dogs, they all have the same colour. Basis step. If there is only one dog, then clearly it has the same colour as itself. Inductive step. Induction hypothesis: Suppose that for some integer k ≥ 1, any k dogs all have the same colour. Now suppose we have k + 1 dogs. Pick out a dog, who we’ll call Fido. By the induction hypothesis, the other k dogs must all have the same colour. Now pick out a second dog, who we’ll call Rover. The remaining k dogs, which include Fido (but not Rover) must also all have the same colour (again by the induction hypothesis). So Fido, Rover and the other k − 1 dogs all have the same colour. Therefore, any set of k + 1 dogs have the same colour. By the Principle of Mathematical Induction, for any integer n ≥ 1, any collection of n dogs all have the same colour. 3. Given integers a and b, find integers q and r with 0 ≤ r < |b| such that a = qb + r. (a) a = 123, b = 5 (b) a = 1357, b = −7 (c) a = −912, b = 19 (d) a = −423, b = −16 (e) a = 123, b = −4567 4. Let n > 1 be a fixed integer. Define f : Z → Z + ∪ {0} to be the function that associates with each a ∈ Z its remainder when divided by n. That is, if a = qn + r where 0 ≤ r < n, then f(a) = r. (a) Is f one-to-one? Why or why not? (b) Is f onto? Why or why not? 1