See file
Combinatorics: BINARY NUMBERS WITH NEGATIVE BITS In this final assignment, we study a number system similar to binary numbers, but different in two respects. First of all, the numbers(bits), in addition to +1 (“positive on”) and 0 (“off”), also −1 (“negative on”). Then second, two bits must not be “on” next to each other (positive and/or negative). For example, the number 7, which we usually write in binary as 111 (or for example 00000111 if we look at 8-bit binary numbers), will now be are written as (1, 0, 0, −1), which stands for . And (−1, 0, 0, 1) correctly represents −7. In this exercise we introduce this number system and we prove with the help of combinatorics that we can use all integers (including the negative so) be able to display uniquely (except for leading zeros) So the possible bits are the numbers −1, 0 and 1. A row of bits is called correct if it satisfies the requirement that for all holds that 0 or. So (0, −1, 0, 0, 1, 0) is a correct sequence of 6 bits, but (−1, 0, 0, 1, −1, 0) neither and (1, 0, 1, 0, 1, 1) neither. Call the number of correct sequences of length . Exercise 1. (a) Check that ,and (b) Determine. (c) Prove that the sequence satisfies the recurrence relation (for ). (Don't do that based on a possible observed pattern in the previous section, but give a conclusive combinatorial argument.) (d) Using recursion, calculate how many correct sequences of length 10 there are. (e) Now solve for the recurring relation (so give a direct general formula for as a function of ). (And check this by calculating again) From a correct sequence of bits we now know the integer admit; we then call the sequence a neighborless notation of bits for. Thus (1, 0, 0, −1) and (0, 0, 0, 0, 1, 0, 0, −1) are neighborless notations of 4 respectively 8 bits for the number 7. Exercise 2. (a) Give all correct sequences of 4 bits. What numbers do these correspond to? (b) For given , what is the largest number you can get with bits (in terms of )? And what is the smallest (most negative) number ? How many numbers are there between and (including and itself)? (Distinguish the cases is even and is odd.) (c) Now prove that for every number with there is exactly one neighborless notation of bits for . Hint: Choose and suppose that = holds for two different correct sequences of bitsand . By removing equal initial bits, we may assume that, say . Now distinguish the cases for and and show that the largest number you can get with the first is smaller is then the smallest number you can get with the second.