Author: Anonymous

Consider the following proposition. “If no questions are dumb, then this question is smart.” Which of the following is the contrapositive of this statement? Only one statement is correct.  Note:  smart = not dumb

Let the function f : ℕ → ℝ be defined recursively as follows:      Initial Condition:  f (0) = 0Recursive Part:  f (n) = (2 * f (n-1)) + 1, for all n > 0 Consider how to prove the following statement about this given function f using induction. For all nonnegative integers n, f (n) = 2n- 1 Select the best response for each question below about how this proof by induction should be done.  Q1.  Which of the following would be a correct Basis step for this proof?   [Basis] A.  For n = k, assume f(k) = 2k – 1 for some integer k ≥ 0, so f(n) = 2n – 1 for n = k. B.  For n = 1, f(n) = f(1) = 2*f(0) +1 = 1; also 2n – 1 = 21 – 1 = 2 – 1 = 1, so f(n) = 2n – 1 for n = 1. C.  For n = k+1, f(k+1) = 2(k+1) – 1 when f(k) = 2k – 1 for some integer k ≥ 0, so f(n) = 2n – 1 for n = k+1. D.  For n = 0, f(n) = f(0) = 0; also 2n – 1 = 20 – 1 = 1 – 1 = 0, so f(n) = 2n – 1 for n = 0.  Q2.  Which of the following would be a correct Inductive Hypothesis for this proof?   [InductiveHypothesis] A.  Assume f(k+1) = 2(k+1) – 1 when f(k) = 2k – 1 for some integer k ≥ 0. B.  Assume f(k) = 2k – 1 for some integer k ≥ 0. C.  Prove f(k) = 2k – 1 for some integer k ≥ 0. D.  Prove f(k) = 2k – 1 for all integers k ≥ 0. Q3.  Which of the following would be a correct completion of the Inductive Step for this proof?   [InductiveStep] A.  f(k+1) = 2*f(k) + 1, which confirms the recursive part of the definition. B.  When f(k+1) = (2(k+1) – 1) = (2(k+1) – 2) + 1 = 2*(2k – 1) + 1; also f(k+1) = 2*f(k) + 1, so f(k) = (2k – 1), confirming the induction hypothesis. C.  When the inductive hypothesis is true, f(k+1) = 2*f(k) + 1 = 2*(2k – 1) + 1 = (2(k+1) – 2) + 1 = (2(k+1) – 1). D.  When the inductive hypothesis is true, f(k+1) = (2(k+1) – 1) = (2(k+1) – 2) + 1 = 2*(2k – 1) + 1 = 2*f(k) + 1, which confirms the recursive part of the definition. Q4.  Which of the following would be a correct conclusion for this proof?   [Conclusion] A.  By the principle of mathematical induction, f(n) = (2n – 1) for all integers n ≥ 0. B.  By the principle of mathematical induction, f(k) = f(k+1) for all integers k ≥ 0. C.  By the principle of mathematical induction, f(n+1) = (2*f(k)) + 1 for all integers n ≥ 0. D.  By the principle of mathematical induction, f(k) = (2k – 1) implies f(k+1) = (2(k+1) – 1) for all integers k ≥ 0.

There exists a simple graph with 4 vertices of degree 2 and 3 vertices of degree 3.

Prove the following statement using induction. “For all integers n ≥ 3, 2n + 1 ≤ 2n.” Use good proof technique.  Grading rubric:1 pt. State the basis step, then prove it.1 pt. State the inductive hypothesis.2 pt. Complete the proof of the inductive step.  [Hint:  The fact that 2k − 1 ≥ 0 when k ≥ 3 can be useful] 1 pt. State the final conclusion at the end of the proof.1 pt. Label each part: the basis step, inductive hypothesis, inductive step, and conclusion. Note: To avoid the need for typing superscript exponents, you may use the expression ‘2^n’ to represent 2n.  Also the ≥ symbol can be written as >=.

Use the Euclidean algorithm to determine the GCD(285, 266).  Show your work. Then express the GCD(285, 266) value you identify as a linear combination of 285 and 266.  Show your work.

Complete your choice of one of the proofs given below.  PROOF 1: Prove the following statement using a proof by cases.   [Hint: there are 3 cases] “For all positive integers n with 2 ≤ n ≤ 4, n!/2 ≤ 2n.” Use good proof technique.   Grading rubric:1 pt. State any givens and assumptions.3 pt. Clearly identify the cases and prove each case.1 pt. State the final conclusion at the end of the proof. Note:  Remember that n factorial, written as n!, is defined as n(n-1)…(2)1, the product of n times every positive integer less than n.   To avoid the need for typing superscript exponents, you may use the expression ‘2^n’ to represent 2n.  Also the ≤ symbol can be written as

For each positive integer k, let Ak = { x ∈ ℝ | 1/k  ≤  x  ≤  k  }. Which of the following sets is equal to ?

Use the Euclidean algorithm to determine the GCD(357, 156).  Show your work. Then express the GCD(357, 156) value you identify as a linear combination of 357 and 156.  Show your work.

The function f : ℕ ⟶ ℕ defined by f(n) = 3n2(log n) is O(n2log n).

Determine which of these set identities are supported by the entries in the membership table given below.  There may be more than one or none. Select ‘True’ if the identity is supported by this given membership table; otherwise select ‘False’. [1]  (A – B) – C ⊆ (A – B) [2]  (A – C) ≠ (A – C) – B [3]  (A – B) ⊂ (A – C) – B [4]  (A – C) – B ⊄ (A – B) [5]  (A – C) ⊈ (A – B) [6]  (A – B) – C = (A – C) – B A B C A – C A – B (A – C) – B (A – B) – C 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0