Formal MethodsHomework Assignment 10, Part 1April 13, 200751. Prove by induction that for each natural number n,nXk=12k−1= 2n− 1.Proof. If n = 1,nXk=12k−1= 21−1= 20= 1,and 2n− 1 = 21− 1 = 1. So if n = 1,nXk=12k−1= 2n− 1.Suppose then that n is a positive integer such thatnXk=12k−1= 2n− 1.We need to show thatn+1Xk=12k−1= 2n+1− 1.Since n ≥ 1, n + 1 ≥ 2. Son+1Xk=12k−1= nXk=12k−1!+ 2(n+1)−1= 2n− 1 + 2n= 2 · 2n− 1= 2n+1− 1.So by the PMI,nXk=12k−1= 2n− 1,for all positive integers n.152. Prove by induction that for each natural number n,nXk=112k= 1 −12nProof. If n = 1nXk=112k=121=12,and1 −12n= 1 −121=12.So if n = 1,nXk=112k= 1 −12nSuppose then that n is a positive integer such thatnXk=112k= 1 −12n.We want to see thatn+1Xk=112k= 1 −12n+1.Since n ≥ 1, n + 1 ≥ 2. Son+1Xk=112k="nXk=112k#+12n+1= 1 −12n+12n+1= 1 −12n+12n+1= 1 +−22n+1+12n+1= 1 +−12n+1= 1 −12n+1So by the PMInXk=112k= 1 −12n,for each positive integer n.253. Let x ∈ R such that x 6= 1. Prove by induction that for each natural number n,nXk=1xk−1=xn− 1x − 1.Note that if x = 0, the first term on the left-hand side is 00, which is undefined. So inaddition to assuming x 6= 1, we assume x 6= 0.Proof. If n = 1,nXk=1xk−1= x1−1= x0= 1,provided x 6= 0. Also, if n = 1,xn− 1x − 1=x1− 1x − 1=x − 1x − 1= 1,provided x 6= 1. So if x 6= 0 and x 6= 1,nXk=1xk−1=xn− 1x − 1,when n = 1.So suppose that x is a real number other than 0 or 1 and n is a positive integer suchthatnXk=1xk−1=xn− 1x − 1.We need to see thatn+1Xk=1xk−1=xn+1− 1x − 1.Since n ≥ 1, n + 1 ≥ 2. Son+1Xk=1xk−1= nXk=1xk−1!+ x(n+1)−1=xn− 1x − 1+ xn=xn− 1x − 1+xn(x − 1)x − 1=xn− 1 + xn(x − 1)x − 1=xn− 1 + xn+1− xnx − 1=xn+1− 1x − 13So by the PMI, if x is a real number other than 0 or 1, thennXk=1xk−1=xn− 1x − 1,for each positive integer n.67. Let f1, f2, f3, . . . be the Fibonacci numbers. Prove by induction that for each naturalnumber n,nXi=1f2i= fnfn+1.Proof. If n = 1,nXi=1f2i= f21= 12= 1,and fnfn+1= f1f2= 1 · 1 = 1. So if n = 1nXi=1f2i= fnfn+1.Suppose then that n is a positive integer such thatnXi=1f2i= fnfn+1.We need to see thatn+1Xi=1f2i= fn+1f(n+1)+1.Since n ≥ 1, n + 1 ≥ 2 andn+1Xi=1f2i= nXi=1f2i!+ f2n+1= fnfn+1+ f2n+1= fn+1(fn+ fn+1).Since n ≥ 1, n + 2 ≥ 3. So fn+2= fn+ fn+1, andn+1Xi=1f2i= fn+1(fn+ fn+1)= fn+1fn+2= fn+1f(n+1)+1.4So by the PMInXi=1f2i= fnfn+1,for all positive integers n.4. Sketch the graph of each of the following relations. For each relation, state its domainand its range.(a) S = {(x, y) ∈ R × R : x2+ y2= 16}The graph of S is a circle, centered at the origin with radius 4. Its domain is[−4, 4]. Its range is also [−4, 4].(b) S = {(x, y) ∈ R × R : y2= 2x}The graph of S is a parabola that opens to the right. Its domain is (0, ∞) andits range is R.(c) S = {(x, y) ∈ R × R : x2= 2y2}The graph of S is the union of two lines, one with positive slope (x =√2y) andone with ne gative slope (−x =√2y). Its domain and its range are both R.5. For each of the relations in 4, evaluate S[1].(a) S[1] = {√15, −√15}.(b) S[1] = {√2, −√2}.(c) S[1] = {1/√2, −1/√2}.6. Let S = {1, 2}. List all the relations on S.Relations on S are subsets of S × S. So we just need to list all the subsets ofS × S = {(1, 1), (1, 2), (2, 1), (2, 2)}.Since this is a 4-element set, it has sixteen subsets:• No elements: ∅• 1 element:{(1, 1)}, {(1, 2)}, {(2, 1)}, {(2, 2)}• 2 elements:{(1, 1), (1, 2)}, {(1, 1), (2, 1)}, {(1, 1), (2, 2)},{(1, 2), (2, 1)}, {(1, 2), (2, 2)}, {(2, 1), (2, 2)}• 3 elements:{(1, 1), (1, 2), (2, 1)}, {(1, 1), (1, 2), (2, 2)},{(1, 1), (2, 1), (2, 2)}, {(1, 2), (2, 1), (2, 2)}• 4 elements:{(1, 1), (1, 2), (2, 1), (2,