Formal MethodsHomework Assignment 9, Part 2April 2, 200717. Prove that for each natural number n ≥ 2,22− 122·32− 132· · · · ·n2− 1n2=n + 12n.Proof. We use the EPMI with base case n = 2. When n = 2,22− 122·32− 132· · · · ·n2− 1n2=22− 122=34,andn + 12n=2 + 12 · 2=34.So in this case22− 122·32− 132· · · · ·n2− 1n2=n + 12n.Suppose then that n is an integer ≥ 2 such that22− 122·32− 132· · · · ·n2− 1n2=n + 12n.Then22− 122·32− 132· · · · ·n2− 1n2·(n + 1)2− 1(n + 1)2=n + 12n·(n + 1)2− 1(n + 1)2=(n + 1)[(n + 1)2− 1]2n(n + 1)2=(n + 1)2− 12n(n + 1)=n2+ 2n + 1 − 12n(n + 1)=n(n + 2)2n(n + 1)=(n + 1) + 12(n + 1)1So by the EPMI22− 122·32− 132· · · · ·n2− 1n2=n + 12n,for all integers n ≥ 2.20. Prove that for each natural number n ≥ 6, (n + 1)2≤ 2n.Proof. We use the EPMI with base case n = 6. When n = 6,(n + 1)2= (6 + 1)2= 49, and 2n= 26= 64.So in this case (n + 1)2≤ 2n.Suppose then that n is an integer ≥ 6 such that (n + 1)2≤ 2n. Then2n+1= 2 · 2n≥ 2 · (n + 1)2= 2n2+ 4n + 2= n2+ 4n + (2 + n2)Since n ≥ 6, n2≥ 2. So2n+1≥ n2+ 4n + (2 + n2)≥ n2+ 4n + (2 + 2)= n2+ 4n + 4= (n + 2)2= [(n + 1) + 1]2So by the EPMI, (n + 1)2≤ 2n, for all integers n ≥ 6.23. Prove that for each natural number n ≥ 3, (1 + 1/n)n< n.Proof. Once again we use the EPMI, this time with base case n = 3. When n = 3,1 +1nn=1 +133=4333=6427= 2 +1027< 3.So in this case (1 + 1/n)n< n.Suppose then that n is an integer ≥ 3, such that (1 + 1/n)n< n. Then1 +1n + 1n+1=1 +1n + 11 +1n + 1n2Now since n ≥ 3, 1/n > 1/(n + 1). Thus1 +1n + 1n+1<1 +1n + 11 +1nn<1 +1n + 1n= n +nn + 1< n + 1So by the EPMI (1 + 1/n)n< n, for all integers n ≥ 3.29. (a) For n ≥ 2, find a formula for1 −141 −191 −116· · ·1 −1n2.We look at a few examples:1 −14=341 −141 −19=34·89=231 −141 −191 −116=23·1516=581 −141 −191 −1161 −125=58·2425=351 −141 −191 −1161 −1251 −136=35·3536=7121 −141 −191 −1161 −1251 −1361 −149=712·4849=47There seem to be two different formulas: one when n is even and one when n isodd. If we definepn=1 −141 −191 −116· · ·1 −1n2,then it appears that for k ≥ 1,p2k=2k + 14k, andp2k+1=k + 12k + 1.3(b) Use the EPMI to prove that your formula holds.Proof. We use (basic) induction to prove the first formula. We’ll derive thesecond formula as a corollary to the first.First formula. We consider the case in which n = 2k is even. If k = 1,p2k= 1 −1(2k)2=34,and2k + 14k=2 · 1 + 14 · 1=34.So in this case,p2k=2k + 14k.Suppose then that k is a positive integer such thatp2k=2k + 14k.We want to see thatp2(k+1)=2(k + 1) + 14(k + 1).From the de finition, we havep2(k+1)= p2k+2=1 −14· · ·1 −1(2k)21 −1(2k + 1)21 −1(2k + 2)2= p2k1 −1(2k + 1)21 −1(2k + 2)2=2k + 14k·(2k + 1)2− 1(2k + 1)2·(2k + 2)2− 1(2k + 2)2=4k2+ 4k4k(2k + 1)·4k2+ 8k + 3(2k + 2)2=4k(k + 1)4k(2k + 1)·(2k + 3)(2k + 1)4(k + 1)2=2k + 34(k + 1)=2(k + 1) + 14(k + 1)So it follows by the PMI that if k is a positive integer, thenp2k=2k + 14k.Second formula. We want to show that if k is a positive integer, thenp2k+1=k + 12k + 1.4This can be proved using the PMI. However, it’s a bit simpler to use the obser-vation thatp2k+1=1 −14· · ·1 −1(2k)21 −1(2k + 1)2= p2k1 −1(2k + 1)2.Substituting our formula for p2kgivesp2k+1= p2k1 −1(2k + 1)2=2k + 14k·(2k + 1)2− 1(2k + 1)2=4k2+ 4k + 1 − 14k(2k + 1)=4k(k + 1)4k(2k + 1)=k + 12k + 1This formula holds whenever the formula for p2kholds. So the formula applieswhenever k is a positive