ECE103 Midterm: Induction

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE103
• Professor: Martin Pei

Document Summary

Let p(x) be a statement that depends on the variable x. Take the following steps to prove p(n): (a) (basis step) prove that p (1) is true (b)(induction hypothesis) assume that p(x) is true for all p(1) p(2) . P(3) p(n - 1) (c) (inductive step) prove that p (n 1) p (n) Then p(n) is true for all integer n. For (c) p (n 1) p (n) means somehow turn p (n 1) into p (n) Example: show that for n a positive integer. > 2n for all integers n 4. The tower of hanoi puzzle consists of a stand with 3 pegs, and n discs. All the discs are of different sizes and all have a hole in the centre so that the discs can be placed over the pegs. The discs are all stacked on one peg, in order of size, with the largest disc on the bottom and the smallest disc on the top.