Đang chuẩn bị liên kết để tải về tài liệu:
Lecture ECE 250 - Algorithms and data structures: Proof by induction

This topic gives an overview of the mathematical technique of a proof by induction: We will describe the inductive principle, look at ten different examples, four examples where the technique is incorrectly applied, well-ordering of the natural numbers, strong induction, geometric problems. | WATERLOO ENGINEERING University of Waterloo O Proof by Induction m Harder M.Math. L ctrical and Computer El Canada VATERLO ENGINEERING Proof by Induction 2 Outline This topic gives an overview of the mathematical technique of a proof by induction - We will describe the inductive principle - Look at ten different examples - Four examples where the technique is incorrectly applied - Well-ordering of the natural numbers - Strong induction - Geometric problems VATERLO ENGINEERING 1.4 Proof by Induction Definition Suppose we have a formula F n which we wish to show is true for all values n n0 - Usually n0 0 or n0 1 For example we may wish to show that n F n ấ k k 0 n n 1 2 for all n