2.5. Recursion and Induction 31 might be proving some property P is true of all the natural numbers. To do so, you prove that P is true of 0, and then prove that if P is true of some n 0, then P is also true of n + 1. To recursively define a class of objects C, you give certain simple examples of objects in C, and then operations that combine or extend elements of C to give results still in C. They relate more deeply than just appearance, though. We’ll tackle induction, then recursion, then induction again. 2.5.1. Induction on N. The basic premise of induction is that if you can start, and once you start you know how to keep going, then you will get all the way to the end. If I can get on the ladder, and I know how to get from one rung to the next, I can get to the top of the ladder. Definition 2.5.1. The principle of mathematical induction, basic form, says the following. If S is a subset of the positive integers containing 1 such that n S implies n + 1 S for all n, then S contains all of the posi- tive integers. [We may need the beginning to be 0 or another value depending on context.] In general you want to use induction to show that some property holds no matter what integer you feed it, or no matter what size finite set you are dealing with. The proofs always have a base case, the case of 1 (or wherever you’re starting). Then they have the inductive step, the point where you assume the property holds for some unspecified n and then show it holds for n + 1. Example 2.5.2. Prove that for every positive integer n, 1 + 3 + 5 + . . . + (2n 1) = n2. Proof. Base case: For n = 1, the equation is 1 = 12, which is true. Inductive step: Assume that 1 + 3 + 5 + . . . + (2n 1) = n2 for some n 1. To show that it holds for n + 1, add 2(n + 1) 1 to each side, in the simplified form 2n + 1. 1 + 3 + 5 + . . . + (2n 1) + (2n + 1) = n2 + 2n + 1 = (n + 1)2 Since the equation above is that of the theorem, for n+1, by induction the equation holds for all n.
Previous Page Next Page