Blog

Let the function f : ℕ → ℝ be defined recursively as follows…

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.

Prove the following statement using induction. “For all inte…

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

Complete your choice of one of the proofs given below.  PRO…

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