61/2 Discrete Structures Homework 6 Due 2/22/17 Suggested Exercises from Section 7.1. (Do not hand in.) ? 19 21, 22 24 ?? 26 30, ? ? ? 31, 33, 56 66 Suggested Exercises from the book, end of Section 7.2. (Do not hand in.) ? 29 35, ?? 36 39, ? ? ? 51, 52. Problem 1 ? Let c(n) be the number of ways that we can place n 0s and 1s around a circle, without placing two 1s next to each other. (This is similar to counting the number of sequences without repeating 1s, except that we also do not allow the first and the last bit to both be 1.) Show that c(n) = Fib(n1)+Fib(n+1), for n 2. ......... Problem 2 ? Prove, by induction, that Fib(n + 1)Fib(n 1) Fib(n)2 = (1)n , for all n 2. ......... Problem 3 ?? We cut a cake using n cuts. Each cut is downwards (as you would usually cut a cake), and is a straight line all the way through. Each pair of cuts crosses in exactly one point, and no three cuts cross in the same point. Find a recurrence relation for d(n), the number of pieces of cake created by n cuts. Then, sum the recurrence equations in the following way: d(n) = d(n 1) = .. . d(2) = + and find an explicit formula for d(n). Start by showing that 1 + 2 + ... + n = n(n + 1) . 2 ......... Puck Rombach 61/2 Discrete Structures Problem 4 Homework 6 Due 2/22/17 ?? Let a(n) be the number of sequences of the form (x1 , x2 , x3 , . . . , xk ) such that 1 xi n, for 1 i k, and 2xi xi+1 for 1 i k 1. We allow k to be any nonnegative integer. So, the empty sequence is included for all n. As an example, the set of such sequences for n = 5 is {(), (1), (1, 2), (1, 2, 4), (1, 2, 5), (1, 3), (1, 4), (1, 5), (2), (2, 4), (2, 5), (3), (4), (5)}, and therefore a(5) = 14. Find a recurrence relation for a(n). ......... Puck Rombach