Indicate which of these listed graphs are bipartite. Select ‘True’ if the graph is bipartite; otherwise select ‘False’.  There may be more than one or none. [A]   K4 [B]   C6 [C]   Q3 [D]   W5

Given relation R defined on the set { 2, 4, 6, 8 } as follows: (m, n) ∈ R if and only if m|n. Determine which properties relation R exhibits.  Select ‘True’ if the property does apply to relation R; otherwise select ‘False’.  There may be more than one or none. [A]   reflexive [B]   irreflexive [C]   symmetric [D]   antisymmetric [E]   asymmetric [F]   transitive

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 >=.

The function f : ℝ ⟶ ℝ defined by f(x) = 5×3 + 3×2 – x + 7 is O(x4).

Indicate a reason for each assertion in the argument below. Choose your answers from the given list of Rules of inference and logical equivalences.  An item from the list may be used as a reason more than once. Assertion Reason Premise 1:   r  ˄ ( ¬s → ¬t  ) Given Premise 2:    t Given A.      r [Step3] B.      ( ¬s → ¬t  ) [Step4] C.      ( t  → s ) [Step5] D.      s [Step6] E.       s  ˄  r [Step7]

For all sets A, B, and C, if A ⊆ B ⋃ C then A ⊆ B and A ⊆ C.

The binary expansion of the decimal number 109 is ___________two. Only type the digits; do not include the base.

The decimal expansion of the hexadecimal number A416 is _______________ten. Only type the digits; do not include the base.

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.