EECE 320 Chapter Notes -Binary Search Algorithm, Liquid Oxygen

• School: UBC
• Department: Electrical and Computer Engineering
• Course: EECE 320
• Professor: All

Document Summary

P(n) : i=0 i3 = 0 =(cid:0) 0 i=0 i(cid:1)2 i=0 (cid:33)2 i (cid:32) n i=0 (cid:33)2 i (cid:32) n i=0. Induction step: we want to show that p(k + 1) is true. Thus the proposition is true for the (cid:33)2 i (cid:33) (cid:32)k+1 i=0 (cid:32) k i i=0. P(k + 1) : k+1 i=0 (i)3 = (cid:33)2 (cid:32) k i=0 (cid:33) (cid:32) k. Therefore, to establish p(k + 1) we need to show that: (k + 1)3 + k i=0 (i)3 = i. 1 (c) prove that for all integers n 1: n k=1. Base case: p(1) : 1 2 1 = 1. Induction step: we would like to establish p(m + 1). k2 2 1. P(m + 1) : m + 1 m+1. Using p(m), we would like to show that. 1 m(m + 1) and in turn we need to show that.