Blog

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

Let the function f : ℕ → ℝ be defined recursively as follows:      Initial Condition:  f (0) = 18Recursive Part:  f (n + 1) = 1/9 * f (n), for n > 0 Consider how to prove the following statement about this given function f using induction. For all nonnegative integers n, f (n) = 2/9(n-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 = 0, f(n) = f(0) = 18; also 2/9(n-1) = 2/9-1 = 2*9 = 18, so f(n) = 2/9(n-1) for n = 0. B.  For n = k, assume f(k) = 2/9(k-1) for some integer k ≥ 0, so f(n) = 2/9(n-1) for n = k. C.  For n = k+1, f(k+1) = 2/9(k+1-1) when f(k) = 2/9(k-1) for some integer k ≥ 0, so f(n) = 2/9(n-1) for n = k+1. D.  For n = 1, f(n) = f(1) = 1/9*f(0) = 1/9*18 = 2; also 2/9(n-1) = 2/90 = 2, so f(n) = 3n for n = 1. Q2.  Which of the following would be a correct Inductive Hypothesis for this proof?   [InductiveHypothesis] A.  Prove f(k) = 2/9(k-1) for some integer k ≥ 0. B.  Assume f(k+1) = 2/9(k) when f(k) = 2/9(k-1) for some integer k ≥ 0. C.  Prove f(k) = 2/9(k-1) for all integers k ≥ 0. D.  Assume f(k) = 2/9(k-1) for some integer k ≥ 0. Q3.  Which of the following would be a correct completion of the Inductive Step for this proof?   [InductiveStep] A.  f(k+1) = 1/9*f(k), which confirms the recursive part of the definition. B.  When the inductive hypothesis is true, f(k+1) = 1/9*f(k) = 1/9*2/9(k-1) = 2/9(k-1)+1 = 2/9(k) = 2/9(k+1)-1 C.  When the inductive hypothesis is true, f(k+1) = 2/9(k) = 2/9(k+1)-1 = 1/9*2/9(k-1) = 1/9*f(k), which confirms the recursive part of the definition. D.  When f(k+1) = 2/9(k+1)-1 = 2/9(k) = 1/9*2/9(k-1); also f(k+1) = 1/9*f(k), so f(k) = 2/9(k-1), confirming the induction hypothesis. Q4.  Which of the following would be a correct conclusion for this proof?   [Conclusion] A.  By the principle of mathematical induction, f(n+1) =1/9* f(n) 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) = 2/9(n-1) for all integers n ≥ 0. D.  By the principle of mathematical induction, f(k) = 2/9(k-1) implies f(k+1) = 2/9(k) for all integers k ≥ 0.  

Consider the following problem:  1391(mod 11) = _________ Sh…

Consider the following problem:  1391(mod 11) = _________ Show how Fermat’s Little Theorem can be used to solve this problem. Express your answer as a non-negative integer less than the modulus. Note:  To avoid the need for typing superscript exponents, you may use the notation ‘x^n’ or the expression ‘x to the nth’ (with numbers in place of x and n), to represent xn.

Prove, or provide a counterexample to disprove, the followin…

Prove, or provide a counterexample to disprove, the following statement:             “The function f : ℝ ⟶ ℤ defined by f(x) = ⌊ 2x ⌋ is a bijection.” Use good proof technique.  Remember that a bijection is both one-to-one (injective) and onto (surjective).  To prove, you must demonstrate both properties are true; to disprove, you only need a counterexample that shows one of the properties is not valid. Grading rubric:1 pt.  Indicate whether you will be proving or disproving the assertion.  Also, if proving, state both definitions, one-to-one and onto; if disproving, state the definition you plan to disprove.  1 pt.  State any givens and assumptions.1 pt.  Clearly explain your reasoning.1 pt.  Remember to state the final conclusion at the end of the proof. Note:  To avoid the need for typing special symbols, instead of using the floor symbols in the function definition ⌊ 2x ⌋ you may use the expression ‘floor of ( 2x )’.