CSCI 2824 Discrete Structures Instructor: Hoenigman Assignment 1 Due Date: 09/05/2013 (Thursday, at the beginning of class). Problem 1 (35 points) For this problem, you are asked to write down a **recurrence relation** and the **closed form** for each of the sequences described below. In each case the indices n are natural numbers and thus n = 0. 1. an = 1, 2, 4, 8, 16, . . . (the sequence of all powers of 2). 2. bn = 1, 3, 2, 9, 4, 27, 8, 81, . . . (altenating powers of 2 and 3). 3. cn = 0, 1, 3, 6, 10, 15, . . . (Hint: look at the differences between successive elements. That should immediately suggest a recurrence. ) 4. dn = 1, 0, 1, 0, 1, 0, 1, 0, . . . (sequence of alternating 1s and 0s). 5. en = 1, 1, 0, 0, 1, 1, 0, 0, . . . ( block of two ones, followed by a block of two zeros, followed by a block of two ones ...) Problem 2 (35 points) Write down recurrence equations for the sequences with the closed forms and summations given below. In each case assume n ? N. 1. pn = 2n+2 . 2. qn = n! (note that 0! = 1, by definition) 3. rn = 2n 2 - 3n + 5. 4. sn = n 2 n is even n+1 2 n is odd 5. tn = 1 n+1 . 6. un = Pn j=1(2j + 1) 7. vn = Qn j=1 2 n 1 Problem 3 (30 points) Let sn be a sequence for n ? N. Its first difference sequence dn is defined by dn = sn+1 - sn. Answer the following questions about the first difference sequences: 1. Take the sequence sn = 2n 2 + 3n + 2. Write down the first 5 elements of its first difference sequence. 2. Write down a closed form for the first difference sequence by noticing the pattern. 3. Write down the second difference sequence, which is the first difference of the first difference sequence.
Document Preview:
CSCI 2824 Discrete Structures Instructor: Hoenigman Assignment 1 Due Date: 09/05/2013 (Thursday, at the beginning of class). Problem 1 (35 points) For this problem, you are asked to write down a **recurrence relation** and the **closed form** for each of the sequences described below. In each case the indices n are natural numbers and thus n 0. 1. a = 1; 2; 4; 8; 16;::: (the sequence of all powers of 2). n 2. b = 1; 3; 2; 9; 4; 27; 8; 81;::: (altenating powers of 2 and 3). n 3. c = 0; 1; 3; 6; 10; 15;::: (Hint: look at the di erences between successive n elements. That should immediately suggest a recurrence. ) 4. d = 1; 0; 1; 0; 1; 0; 1; 0;::: (sequence of alternating 1s and 0s). n 5. e = 1; 1; 0; 0; 1; 1; 0; 0;::: ( block of two ones, followed by a block of two n zeros, followed by a block of two ones ...) Problem 2 (35 points) Write down recurrence equations for the sequences with the closed forms and summations given below. In each case assume n2N. n+2 1. p = 2 . n 2. q =n! (note that 0! = 1, by de nition) n 2 3. r = 2n 3n + 5. n n n is even 2 4. s = n n+1 n is odd 2 1 5. t = . n n+1 P n 6. u = (2j + 1) n j=1 Q n n 7. v = 2 n j=1 1Problem 3 (30 points) Let s be a sequence for n 2 N. Its rst di erence sequence d is de ned n n by d = s s . Answer the following questions about the rst di erence n n+1 n sequences: 2 1. Take the sequence s = 2n + 3n + 2. Write down the rst 5 elements of n its rst di erence sequence. 2. Write down a closed form for the rst di erence sequence by noticing the pattern. 3. Write down the second di erence sequence, which is the rst di erence of the rst di erence sequence. 2