Formal MethodsKey to Homework Assignment 7, Part 2March 21, 20071. Prove by induction that for each natural numb er n, each of the following is true.(a) 2 + 4 + 6 + · · · + 2n = n(n + 1).Although this isn’t part of the proof, we first identify the statements Pn:P1: 2 · 1 = 1(1 + 1)P2: 2 · 1 + 2 · 2 = 2(2 + 1)P3: 2 · 1 + 2 · 2 + 2 · 3 = 3(3 + 1)...Pn: 2 · 1 + 2 · 2 + 2 · 3 + · · · + 2n = n(n + 1)....Proof. The proof is by induction on n. The base case is n = 1, and we need tosee that that 2 · 1 = 1(1 + 1). But this is completely straightforward arithmetic:both the left- and right-hand sides are 2. So2 + 4 + 6 + · · · + 2n = n(n + 1),when n = 1.The induction step consists of two parts:– A statement of the induction hypothesis (Pn).– A proof that the induction hypothesis implies the “next” statement (Pn+1).We assume that n is a positive integer such that2 + 4 + 6 + · · · + 2n = n(n + 1).We want to show that this implies that2 + 4 + 6 + · · · + 2n + 2(n + 1) = (n + 1)[(n + 1) + 1].1We start with the left-hand side of this equation. (Note that we do not start byassuming Pn+1! We only work with one side of Pn+1.) We have2 + 4 + 6 + · · · + 2n + 2(n + 1) = n(n + 1) + 2(n + 1) (by the IH)= (n + 1)(n + 2) (by the distributive law)= (n + 1)[(n + 1) + 1] (by the associative law).So by the Principle of Mathematical Induction (PMI), we can conclude that2 + 4 + 6 + · · · + 2n = n(n + 1),for all positive integers n.(e) 2 + 5 + 8 + · · · + (3n − 1) = n(3n + 1)/2Once again we start by identifying the Pn:P1: 3 · 1 − 1 = 1(3 · 1 + 1)/2P2: (3 · 1 − 1) + (3 · 2 − 1) = 2(3 · 2 + 1)/2P3: (3 · 1 − 1) + (3 · 2 − 1) + (3 · 3 − 1) = 3(3 · 3 + 1)/2...Pn: (3 · 1 − 1) + (3 · 2 − 1) + (3 · 3 − 1) + · · · + (3n − 1) = n(3n + 1)/2...Proof. The proof is by induction on n. The base case is n = 1. In this case, weneed to see that 3 · 1 − 1 = 1(3 · 1 + 1)/2. But this is just basic arithmetic: theleft-hand side and the right-hand side are both 2. So2 + 5 + 8 + · · · + (3n − 1) = n(3n + 1)/2,when n = 1.For the induction step, we assume that n is a positive integer such that2 + 5 + 8 + · · · + (3n − 1) = n(3n + 1)/2.We need to see that2 + 5 + 8 + · · · + (3n − 1) + [3(n + 1) − 1] = (n + 1)[3(n + 1) + 1]/2.Starting with the left-hand side of this equation, we have2 + 5 + 8 + · · · + (3n − 1) + [3(n + 1) − 1] =n(3n + 1)2+ (3n + 2) (by the IH)=n(3n + 1) + 2(3n + 2)2=3n2+ 7n + 42=(n + 1)(3n + 4)2=(n + 1)[3(n + 1) + 1]2.2So by the PMI we can conclude that2 + 5 + 8 + · · · + (3n − 1) = n(3n + 1)/2,for all positive integers n.(g) 1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) = n(n + 1)(n + 2)/3As usual, we first identify the Pn:P1: 1(1 + 1) = 1(1 + 1)(1 + 2)/3P2: 1(1 + 1) + 2(2 + 1) = 2(2 + 1)(2 + 2)/3P3: 1(1 + 1) + 2(2 + 1) + 3(3 + 1) = 3(3 + 1)(3 + 2)/3...Pn: 1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) = n(n + 1)(n + 2)/3...Proof. For the base case, we need to see that 1(1 + 1) = 1(1 + 1)(1 + 2)/3, andthis is straightforward: both the left- and right-hand sides are 2. So we see that1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) = n(n + 1)(n + 2)/3,when n = 1.So suppose that n is a positive integer such that1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) = n(n + 1)(n + 2)/3.We need to see that1(1+1)+2(2+1)+3(3+1)+· · ·+n(n+1)+(n+1)[(n+1)+1] = (n+1)[(n+1)+1][(n+1)+2]/3.Applying the Induction Hypothesis to the left-hand side, we get1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) + (n + 1)[(n + 1) + 1]=n(n + 1)(n + 2)3+ (n + 1)(n + 2)=n(n + 1)(n + 2) + 3(n + 1)(n + 2)3=(n + 1)(n + 2)(n + 3)3=(n + 1)[(n + 1) + 1][(n + 1) + 2]3So by the PMI, we see that1(1 + 1) + 2(2 + 1) + 3(3 + 1) + · · · + n(n + 1) = n(n + 1)(n + 2)/3,for all positive integers n.3(k) xn− ynis divisible by x − y, where x and y are any two distinct integers.Recall that a is divisible by b iff there exists an integer k such that a = kb. So thePncan be written asP1: There exists an integer k1such that x1− y1= k1(x − y).P2: There exists an integer k2such that x2− y2= k2(x − y).P3: There exists an integer k3such that x3− y3= k3(x − y)....Pn: There exists an integer knsuch that xn− yn= kn(x − y)....Note that it would be technically incorrect to just say “there exists an integer k,”since this would imply that the same integer would work for each positive integern, and it’s easy to see that this can’t be correct. For example, if x = 2 and y = 1,when n = 1, x1− y1= 1(x − y). But when n = 2, x2− y2= 3(x − y).Proof. Suppose that x and y are integers such that x 6= y. If n = 1, we need tosee that there is an integer k1such that x1− y1= k1(x − y). Clearly, k1= 1 willdo the job. So if n = 1, there exists an integer knsuch thatxn− yn= kn(x − y).Suppose then that n is a positive integer such that there exists an integer knwiththe property thatxn− yn= kn(x − y).We need to see that there is an integer kn+1such thatxn+1− yn+1= kn+1(x − y).By the induction hypothesisxn= kn(x − y) + yn.Thusxn+1− yn+1= x · xn− yn+1= x[kn(x …