The Fibonacci numbers are defined as follows: f_0 = 0, f_1 = 1, and f_n = f_n -

Question

The Fibonacci numbers are defined as follows: f_0 = 0, f_1 = 1, and f_n = f_n - 1 + f_n - 2 for n greaterthanorequalto 2. In class, we have seen that for any m greaterthanorequalto 1, the number of 00-free bitstrings of length m is equal to f_m + 2. (In class. I showed this for m greaterthanorequalto 2, but this result is also valid for m = 1.) Let n greaterthanorequalto 1 be an integer. For each question below, justify your answer. How many 00-free bitstrings of length n + 2 do not contain any 0? How many 00-free bitstrings of length n + 2 contain exactly one 0? How many 00-frce bitstrings of length n + 2 have the following property: The bitstring contains at least two 0's, and the second rightmost 0 is at position 1. How many 00-free bitstrings of length n + 2 have the following property: The bitstring contains at least two 0's, and the second rightmost 0 is at position 2. Let k be an integer with 3 lessthanorequalto k lessthanorequalto n. How many 00-free bitstrings of length n + 2 have the following property: The bitstring contains at least two 0's, and the second rightmost 0 is at position k. Let k be an element of {n + l, n + 2}. How many 00-free bitstrings of length n + 2 have the following property: The bitstring contains at least two 0's, and the second rightmost 0 is at position k. Use the previous results to prove that sigma^n_k = 1 (n - k + 1). f_k = f_n + 4 n - 3, n. f_1 + (n - 1). f_2 + (n - 2). f_3 +... +2. f_n - 1 + 1. f_n = f_n + 4- n - 3.

Explanation / Answer

1) The 00-bit string of length (n+2) that don't contain any 0 will be equal to 1

Since we have (n+2) spaces and we can only fill 1 number in that which is equal to one, hene the only possible string will be 1111...11(n+2) times

Hence the correct answer is 1

2) The 00-bit string of length (n+2) that contain exactly one 0

Since there is exactly one 0 hence we don't need to remove any 00-free bit strings, there are total of (n+2) spaces where 0 can be placed

Hence the number of combinations will be equal to (n+2)

3) We want the string with minimum two zeroes and the second rightmost zero should be at position 1

Hence the position 0 must also have a zero, but that string wouldn't be 00 free, hence the option is not possible

Therefore correct answer is zero

4)

We want the string with minimum two zeroes and the second rightmost zero should be at position 2

Hence the position 0 must also have a zero, but that string would be 00 free, hence the option is possible

Therefore correct answer is one

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.