InductionInduction is the basic method of proof for facts involving natural numbers. It allowsus to obtain, in a finite number of steps, proofs of statements about all the numbersin the infinite set N.Induction comes in various formulations. Here is the best-known version.Theorem 1 (Induction). Fix an integer n0 and let P(n) be a statement which makessense for every integer n ? n0. Then P(n) is true for all n ? n0, if the following twostatements are true:(a) P(n0) is true; and(b) for all k ? n0, if P(k) is true then P(k +1) is true.When using induction to prove a theorem, proving (a) is called the base case,and proving (b) is called the induction step.You have almost certainly seen this principle used before, perhaps in calculus, inevaluating sums arising in connection with the definite integral.Here is a simple example.Example 1. For all n ? 1,1+3+5+Β + (2n?1) = n2.Proof. Let P(n) be the statement1+3+5+Β + (2n?1) = n2,or in words, Βthe sum of the firs
t n odd numbers is n2Β. Thus P(1) is the statement1 = 12,P(2) is the statement1+3 = 22,P(5) is the statement1+3+5+7+9= 52,and so on. All of these are clearly true, but just looking at P(n) for many specificvalues of n does not suffice to prove P(n) for every natural number n ? 1. So we letn0 = 1 and use induction to prove P(n) for all n ? 1.The base case P(1) is true, since 1 = 12.For the induction step, let k be some unspecified number ?1, and assume thatP(k) is true, that is,1+3+Β + (2k ?1) = k2.We want to show that then P(k +1) is true, that is,1+3+Β + (2k ?1)+(2k +1)=(k +1)2.To do so, we can add (2k +1) to both sides of the equation P(k) to get1+3+Β + (2k ?1)+(2k +1) = k2 + (2k +1). (2.1)The left side of (2.1) is the left side of the statement P(k+1), and, since k2+2k+1=(k +1)2, the right side of (2.1) is equal to (k +1)2, the right side of P(k +1). Thusassuming P(k) is true, it follows that P(k +1) is true.By induction, P(n) is true for all n ? 1.