1. Engineering
  2. Computer Science
  3. 4 explain why the proof below is incorrect this proof...

Question: 4 explain why the proof below is incorrect this proof...

Question details

4. Explain why the proof below is incorrect. This proof uses induction to prove the false claim that n2-O(n) Hint: plug k-1 (and maybe k2) into the inductive step and see where the argument breaks down (i.e., why it doesnt prove the formal definition). Proof. We prove that there exists some positive constant c such that n cn for all n 1 by induction on n (Base case: n 1) When 1,n2Hence, n2 cn for n1 and (inductive step) Suppose that there exists some positive c such that k2 < ck, for some k 1, and consider (k +1)2. Since c is positive, there are two possibilities: c>1/3 and cS 1/3 Case 1: c > 1/3) Note that since k1, k2k, so k Sk2. Also, since (k+1)2 k2 2k +1 k 2k2+1 3k2 +1 S 3(ck) k2 ck 1 5 3c K 3c(k 1)Hence, in the case where c > 1/3, there exists some positive constant c2 namely c2 3c, such that (k+1)2 S c2(k + 1). (Case 2: cs1/3) If c < 1/3: (k + 1)2 =k2 +2k + 1 cs 1/3 S k+1 Hence, in the case where c 1/3, there exists some positive constant o2 namely c2 1, such that (k +1)2 S c2(k +1) Since there exists some positive constant c2 such that (k+1)2 (k1) in both cases, there exists some positive constant c such that n2 cn for all n 2 1, by induction. Thus, there exists positive constants c and no such that n2 en for all n 2 no, namely c and no 1. By the formal definition of Big-Oh, this means that n2(

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution