Report

Discrete Mathematics Math 6A Homework 9 Solution 3.4-2 f(0) = 3 a) f(1)=-2f(0)=-2*3=-6 f(2)=-2f(1)=-2*-6=12 f(3)=-2f(2)=-2*12=-24 f(4)=-2f(3)=-2*-24=48 f(5)=-2f(4)=-2*48=-96 b) f(1)=3f(0)+7 = 3*3 + 7 = 16 f(2)=3f(1)+7 = 3*16 + 7 = 55 f(3)=3f(2)+7 = 3*55 + 7 = 172 f(4)=3f(3)+7 = 3*172 + 7 = 523 f(5)=3f(4)+7 = 3*523 + 7 = 1576 c) f(1) = f(0)^2 - 2f(0) -2 = 3^2 – 2*3 -2 =1 f(2) = f(1)^2 - 2f(1) -2 = 1^2 – 1*3 -2 = -3 f(3) = f(2)^2 - 2f(2) -2 = -3^2 – 2*-3 -2 = 13 f(4) = f(3)^2 - 2f(3) -2 = 13^2 – 2*13 -2 = 141 f(5) = f(4)^2 - 2f(4) -2 = 141^2 – 2*141 -2 = 19,579 d) f(1)=3^{f(0)/3} = 3^{3/3} = 1 = f(0). In the same manner, f(n) = 3 for all n. 3.4-3 f(0) = -1 , f(1) =2 a) f(2) = f(1) + 3f(0) = 2 + 3*(-1) = -1 f(3) = f(2) + 3f(1) = -1 + 3*2 = 5 f(4) = f(3) + 3f(2) = 5 + 3*(-1) = 2 f(5) = f(4) + 3f(3) = 2 + 3*5 = 17 b) f(2) = f(1)^2*f(0) = 2^2 *(-1) = -4 f(3) = f(2)^2*f(1) = (-4)^2*2 = 32 f(4) = f(3)^2*f(2) = 32^2 *(-4) = --4096 f(5) = f(4)^2*f(3) = (-4096)^2 *32 = 536,870,912 c) f(2) = 3f(1)^2 - 4f(0)^2 = 3*2^2 - 4*(-1)^2 = 8 f(3) = 3f(2)^2 - 4f(1)^2 = 3*8^2 - 4*2^2 = 176 f(4) = 3f(3)^2 - 4f(2)^2 = 3*176^2 - 4*8^2 = 92,672 f(5) = 3f(4)^2 - 4f(3)^2 = 3*92672^2 - 4*176^2 = 25,764,174,8484 d) f(2) = f(0)/f(1) = -1/2 f(3) = f(1)/f(2) = 2/(-1/2) = -4 f(4) = f(2)/f(3) =(-1/2)/(-4) = 1/8 f(5) = f(3)/f(4) =(-4)/(1/8) = -32 3.4-13 Prove that f1+f3+...+f2n-1 = f2n whenever n is a pos. int. We prove this by induction. The base case is n=1, and in that case the statement to be proved in just f1=f2; this is true since both values are 1. Next we assume that inductive hypothesis, that f1+f3+...+f2n-1 = f2n , and try to prove the corresponding statement for n+1, namely, f1+f3+...+f2n-1+f2n+1 = f2n+2. We have f1+f3+...+f2n-1+f2n+1 = f2n + f2n+1 (by the inductive hypothesis) = f2n+2 (by the def. of the Fibonacci numbers) 3.4-22 Show that the set S defined by 1S and s+tS whenever sS and tS is the set of pos. ints. Clearly only pos. int. can be in S, since 1 is a pos. int. and the sum of two pos ints. is again a pos. int. To see that all pos. ints. are in S, we proceed by induction. Obviously 1S. Assuming that nS, we get that n+1 is in S by applying the recursive part of the def. w/ s=n and t=1. Thus S is precisely the set of pos. ints. 3.4-23 Give a recursive def. of the set of pos. ints. that are multiples of 5. We can define the set S={x|x is a pos. int. and x is a multiple of 5} by the base case requirement that 5S and the recursive requirement that if nS, then n+5S. Alternatively we can mimic Example 7, making the recursive part of the definition that x+yS whenever x and y are in S. 3.4-25 Give a recursive definition of a) the set of even integers. Since we can generate all the even ints. by starting w/ 0 and repeatedly adding or subtracting 2, a simple recursive way to define this set is as follows: 0S; and if xS then x+2S and x-2S. b) the set of pos. ints congruent to 2 modulo 3. The smallest pos. int. congruent to 2 mod 3 is 2. so we declare 2S. All the others can be obtained by adding multiples of 3, so our inductive step is that if xS, then x+3S. c) the set of pos. ints not divisible by 5. The pos. ints. not divisible by 5 are the ones congruent to 1,2,3, or 4 mod 5. Therefore we can proceed just as in part (b), setting 1S, 2S, 3S, and 4S as the base cases, and then declaring that if xS, then x+5S. 3.4-27 a) If we apply each of the recursive step rules to the only element given in the basis step, we see that (0,1), (1,1), and (2,1) are all in S. If we apply the recursive step to these we add (0,2), (1,2), (2,2), (3,2) and (4,2). The next round gives us (0,3),(1,3), (2,3), (3,3), (4,3), (5,3), and (6,3). And the fourth set of applications adds (0,4),(1,4),(2,4),(3,4),(4,4),(5,4),(6,4),(7,4), and (8,4). b) Let P(n) be the statement that a2b whenever the (a,b)S is obtained by n applications of the recursive step. For the basis step, P(0) is true, since the only element of S obtained w/ no applications of the recursive step is (0,0), and indeed 02*0. Assume the strong inductive hypothesis that a2b whenever (a,b)S is obtained by k or fewer applications of the recursive step, and consider an element obtained w/ k+1 applications of the recursive step. Since the final application of the recursive step to an element (a,b) must be applied to an element obtained w/ fewer application for the recursive step, we know that a2b. So we just need to check that this inequality implies a2(b+1), a+12(b+1), and a+22(b+1). But this is clear, since we just add 02, 12, and 22, respectively, to a2b yields a2(b+1), a+12(b+1), and a+22(b+1) . c) Structural Induction: This holds for the basis step, since 00. If this holds for (a,b), then it also holds for the elements obtained from (a,b) in the recursive step, since adding 02, 12, and 22, respectively, to a2b yields a2(b+1), a+12(b+1), and a+22(b+1). 6.1-11 a) Since the number of bacteria triples every hour, the recurrence relation should say that the number bacteria after n hours is 3 times the number of bacteria after n-1 hours. Letting bn denote the number of bacteria after n hours, this statement translates into the recurrence relation bn=3bn-1 b) The given statement is the initial condition b0=100. We solve the recurrence relation by iteration: bn = 3bn-1 = 32bn-2 = ... = 3nbn-n = 3nb0. Letting n=10 and knowing that 6.1-12 We are letting an be the population, in billion of people, n years after 2002. a) an=1.013an-1 with a0=6.2 b) an = 6.2(1.013)^n c) a20 = 6.2(1.013)20 8.0 billion people 6.1-23 the number of bit strings of length n that contain a pair of consecutive 0's a) Let an be the number of bit string of length n containing a pair of consecutive 0's In order to construct a bit string of length n containing a pair of consecutive 0's, we could start with •1 and follow with a string of length n-1 containing a pair of consecutive 0's, or •01 and follow with a string of length n-2 containing a pair of consecutive 0's, or •00 and follow with any string of length n-2 containing a pair of consecutive 0's These three cases are mutually exclusive and exhaust the possibilities for how the string might start. From this analysis we can immediately write down the recurrence relation, valid for all n2: an=an-1 + an-2 + 2n-2. (Recall that there are 2k bit strings of length k) b) There are no bit strings of 0 or 1 containing a pair of consecutive 0's, so the initial conditions are a0 = a1 = 0 c) We will compute a2 through a7 using the recurrence relation: a2 = a1 + a0 + 2^0 = 0 + 0+ 1 = 1 a3 = a2 + a1 + 2^1 = 1 + 0+ 2 = 8 a4 = a3 + a2 + 2^2 = 3 + 1+ 4 = 9 a5 = a4 + a3 + 2^3 = 8 + 3+ 8 = 19 a6 = a5 + a4 + 2^4 = 19 + 8+ 16 = 43 a7 = a6 + a5 + 2^5 = 43 + 19+ 32 = 94 Thus there are 94 bit strings of length 7 containing two consecutive 0's 6.1-24 the number of bit strings of length n that contain three consecutive 0's a) Let an be the number of bit string of length n containing a pair of consecutive 0's In order to construct a bit string of length n containing a pair of consecutive 0's, we could start with 1 and follow with a string of length n-1 containing three consecutive 0's, or 01 and follow with a string of length n-2 containing three consecutive 0's, or 001 and follow with a string of length n-3 containing three consecutive 0's 000 and follow with any string of length n-3 containing a pair of consecutive 0's These four cases are mutually exclusive and exhaust the possibilities for how the string might start. From this analysis we can immediately write down the recurrence relation, valid for all n3: an=an-1+ an-2 + an-3 + 2n-3. b) There are no bit strings of 0, 1 or 2 containing three consecutive 0's, so the initial conditions are a0 = a1 = a2 = 0 c) We will compute a3 through a7 using the recurrence relation: a3 = a2 + a1 + a0+ 2^0 = 0 + 0+ 0+ 1 = 1 a4 = a3 + a2 + a1+ 2^1 = 1 + 0+ 0+ 2 = 3 a5 = a4 + a3 + a2+ 2^2 = 3 + 1+ 0+ 4 = 8 a6 = a5 + a4 + a3+ 2^3 = 8 + 3+ 1+ 8 = 20 a7 = a6 + a5 + a4+ 2^4 = 20 + 8+ 3+ 16 = 47 Thus there are 47 bit strings of length 7 containing three consecutive 0's 6.2-3 a) r-2=0, r=2, an = 2n, (by Theorem 3 with k=1), a0=3, 3 = 2^0, =3, Therefore a_n=3*2^n b) r-1=0, r=1, a_n= 1^n= , a0=2, =2, Therefore an=2 for all n c) r^2 – 5r +6 = 0, r=2, 3, an= 12^n + 23^n, a0=1, 1= 1 + 2, since a1=0 0=21 + 32, 1=3 2=-2. Therefore an=3*2^n – 2*3^n d) r^2-4r+4=0, r=2, an= 12n + 2n2n, since a0=6 and a1=8 1=6, 8=21 + 22. 2=-2. Therefore an=6*2^n – 2*n*2^n e) r^2+4r+4=0, r=-2, an= (-2)n + n(-2)n, a0=0 and a1=1, 1=0, 1=-21 - 22, 2=1/2, Therefore an=(-1/2)n(-2)n = n(-2)n-1 f) r^2 -4 = 0, r=2, -2, an= 12n + 2(-2)n, 0= 1 + 2, and 4=21 - 22, 1=1, 2=-1. Therefore an=2^n – (-2)^n. g) r^2-1/4=0, r=1/2, -1/2. an= 1(1/2)^n + 2(-1/2)^n. 1= 1+ 2 and 0= 1/2 - 2/2. 1= 2=1/2 Therefore an=(1/2)(1/2)^n + (1/2)(-1/2)^n = (1/2)n+1 – (-1/2)n+1 6.2-4 a) r^2-r-6 = 0, r=2,3, an=1(-2)^n + 2*3^n , 3= 1+2, 6= -21+32, 1=3/5, 2=12/5. Therefore an=(3/5)(-2)^n + (12/5)3^n b) r^2-7r+10 = 0, r=2,5, an=1(2)^n + 2*5^n , 2= 1+2, 1= 21+52, 1=3, 2=1. Therefore an=3*2^n – 5^n c) r^2-6r+8 = 0, r=2,4, an=1(2)^n + 2*4^n , 4= 1+2, 10= 21+42, 1=3, 2=1. Therefore an=3*2^n + 4^n d) r^2-2r+1 = 0, r=1,1, an=1(1)^n + 2*n*1^n = 1 + 2*n , 4= 1, 1= 1+2, 1=4, 2=-3. Therefore an=4 – 3n e) r^2-1 = 0, r=-1,1, an=1(-1)^n + 2*1^n = 1(-1)^n + 2, 5= 1+2, -1= -1+2, 1=3, 2=2. Therefore an=3*(-1)^n + 2 f) r^2 + 6r + 9 = 0, r=-3,-3, an=1(-3)^n + 2*n*(-3)^n, 3= 1, -3= -31-32, 1=3, 2=-2. Therefore an=3(-3)^n – 2n(-3)^n = (3-2n)(-3)^n g) r^2+4r-5 = 0, r=-5, 1, an=1(-5)^n + 2*1^n = 1(-5)^n + 2, 2= 1+2, 8= 51+2, 1=-1, 2=3. Therefore an=-(-5)^n + 3