non-negative integers

DMTH237 Assignment 4 DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE , E6A 109 Tutor: Daniel Linssen DMTH237 S114 Discrete Mathematics II Assignment 4 Due 12:00 noon, Wednesday 21 May Please sign the declaration below, and staple this sheet to the front of your solutions. Your assignment must be submitted at the Science Centre, E7A Level 1. Your assignment must be STAPLED, please do not put it in a plastic sleeve. PLAGIARISM Plagiarism involves using the work of another person and presenting it as one’s own. For this assignment, the following acts constitute plagiarism: a) Copying or summarizing another person’s work. b) Where there was collaborative preparatory work, submitting substantially the same final version of any material as another student. Encouraging or assisting another person to commit plagiarism is a form of improper collusion and may attract the same penalties. STATEMENT TO BE SIGNED BY STUDENT 1. I have read the definition of plagiarism that appears above. 2. In my assignment I have carefully acknowledged the source of any material which is not my own work. 3. I am aware that the penalties for plagiarism can be very severe. 4. If I have discussed the assignment with another student, I have written the solutions independently. SIGNATURE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Consider the equation a+b+c+d+e = 73 in which the variables all represent non-negative integers. (a) How many solutions are there with a ≥ 7 , b ≤ 23 , and 9 ≤ c ≤ 19 ? (b) How many solutions are there in which the variables are all at most 20? 2. In each of the following cases, find a0 , a1 , a2 , and a recurrence relation for an . (a) an is the number of words of length n (in the usual, 26-letter alphabet) in which the string ‘dog’ does not appear as consecutive letters. (b) an is the number of words of length n in the alphabet { a, b, c } in which c appears an odd number of times. 3. Solve each of these (related) recurrence relations for the sequence {an : n ≥ 0}. First downloaded: 19/5/2014 at 3:5::58 1 (a) an − 5 an−1 − 14 an−2 = 0 with a0 = 3 and a1 = 4 . (b) an − 5 an−1 − 14 an−2 = 4 × 3 n with a0 = 4 and a1 = 3 . 4. Find the general solution of each of the following recurrences. (a) an − 5 an−1 − 5 an−2 = 0 (b) an − 6 an−1 + 10 an−2 = 0 (c) an − 12 an−2 + 16 an−3 = 0 (d) an − 6 an−1 = 15 n (e) an + 5 an−1 = cos n (f) an − 4 an−1 = (2 n) 5n (g) an − 5 an−1 + 6 an−2 = 7 × 3 n (h) an − 3 an−2 + 2 an−3 = 3 n (i) an + an−2 = cos nπ 2 5. Design a Turing Machine to construct the function f(n) = 3 b 1 3 nc + 2, (that is, 2 more than 3× the integer part of 1 3 n) for n ∈ N. Do not just produce a TM, but also describe briefly how it works. There is a TM in the Cooper notes that does almost this. Modify it to produce the required TM. 6. Prove by induction on n that if the following TM is started with a blank tape, after 10 n + 2 steps the machine will be in state [4] with the tape reading . . . 0(1110)n110 ↑ 0 . . . 0 1 0 1R2 0L5 1 0R0 1R1 2 1R4 1R5 3 0R1 1L3 4 1L3 1L5 2