Formal MethodsHomework Assignment 9, Part 3April 11, 200741. Let x1= 1, and for n > 1, let xn=√3xn−1+ 1. Prove that xn< 4 for all n ∈ N.Proof. We use the basic PMI. The base case is clear: if n = 1, xn= 1, which is lessthan 4. So xn< 4 when n = 1.Suppose then that n is a positive integer such that xn< 4. We need to see thatxn+1< 4. Since n ≥ 1, n + 1 > 1. So, by definition,xn+1=p3x(n+1)−1+ 1=√3xn+ 1Now the function y =√3x + 1 is an increasing function. So if a < b, then√3a + 1 ≤√3b + 1. Thus, since xn< 4,xn+1≤√3 · 4 + 1=√13<√16= 4So by the PMI, xn< 4, for all positive integers n.54. Let a1= 1, and for each natural number n > 1, let an= 3an−1−1. Prove that for eachnatural number n,an=123n−1+ 1.Proof. If n = 1, an= 1, and123n−1+ 1=12· 2 = 1.So if n = 1,an=123n−1+ 1.1Suppose then that n is a positive integer such thatan=123n−1+ 1.We need to show thatan+1=123(n+1)−1+ 1.Since n ≥ 1, n + 1 > 1. Soan+1= 3a(n+1)−1− 1= 3an− 1= 3123n−1+ 1− 1=12· 3 · 3n−1+32− 1=12· 3n+12=123(n+1)−1+ 1So by the PMIan=123n−1+ 1,for all positive integers n.55. Let a1= 1 and a2= 3, and for each natural number n > 2, let an= 3an−1− 2an−2.Prove that for each natural number n, an= 2n− 1.Proof. If n = 1, an= 1, and 2n− 1 = 2 − 1 = 1. So if n = 1, an= 2n− 1.[In the induction step, we would ordinarily assume that n is a positive integer such thatan= 2n−1, and then try to deduce that an+1= 2n+1−1. However, this would involvecases, because there are two possible formulas for an+1: the formula if n + 1 = 2 (i.e.,n = 1) and the formula if n + 1 > 2. To avoid this we could prove that a2= 22− 1directly, and then, in the induction step, instead of assuming n ≥ 1, we would assumen ≥ 2. Either approach is fine. I’ll use the second approach.]If n = 2, an= 3, and 2n− 1 = 22− 1 = 3. So in this case also, an= 2n− 1.[Now if n ≥ 2, the formula for an+1involves both anand an−1. So instead of using thebasic PMI, I’ll use the strong PMI.]Suppose then that n is an integer ≥ 2 such that ak= 2k+ 1, whenever k = 1, 2, . . . , n.Then, since n ≥ 2, n + 1 > 2. Soan+1= 3a(n+1)−1− 2a(n+1)−2= 3an− 2an−1= 3(2n− 1) − 2(2n−1− 1)2= 3 · 2n− 3 − 2 · 2n−1+ 2= 3 · 2n− 2n− 1= 2 · 2n− 1= 2n+1− 1So by the strong PMI, for each positive integer n, an= 2n− 1.57. Let a1= a2= a3= 1, and for each natural number n > 3, letan= an−1+ an−2+ an−3.Prove that for each natural number n > 1, an≤ 2n−2.Proof. By analogy with problem 55, we use the strong PMI and we prove three basecases. If n = 2, an= 1 and 2n−2= 1. If n = 3, an= 1, and 2n−2= 2. If n = 4,an= an−1+ an−2+ an−3= a3+ a2+ a1= 3,and 2n−2= 4. So if n = 2, 3, or 4, an≤ 2n−2.Suppose then that n is an integer ≥ 4 such that ak≤ 2k−2for k = 2, 3, . . . n. We wantto see that an+1≤ 2(n+1)−2. Since n ≥ 4, n + 1 > 5. Soan+1= a(n+1)−1+ a(n+1)−2+ a(n+1)−3= an+ an−1+ an−2Since n ≥ 4, n, n − 1, and n −2 are all ≥ 2. So the induction hypothesis applies to an,an−1, and an−2, andan+1= an+ an−1+ an−2≤ 2n−2+ 2n−3+ 2n−4≤ 2n−2+ 2n−3+ 2 · 2n−4= 2n−2+ 2 · 2n−3= 2n−2+ 2n−2= 2 · 2n−2= 2(n+1)−2So by the strong PMI, an≤ 2n−2for all integers n ≥