How do you write S_k in forms of r_s? How do you solve that recurrance relation? What would an algorithm be in O(log k)? What does an algorithm like that look like?

Question 2. (10 points) Very sparse numbers A positive integer is called sparse if its binary representation does not contain any consecutive 1's, n-69 ? 1000101 In this problem, we want to calculate the number of sparse integers with bit length exactly k denoted by Sk. Eg. for k 3, the only sparse numbers of bit length 3 are 4 ? 100,5 ? 101, which ives us that s3 2. Note 2.1. 0 is not a sparse number. 1. (3 points) Find a recurrence relation for sk and give a O(k) method to calculate sk Hint 2.1. Observe that the leading digit of any number has to be 1. Now try to find the position of the next 1. 2. (2 points) Let rk be the number of sparse binary strings with length less than or equal to k. Write sk in terms of 1 Hint 2.2. Observe that the leading digit of a string does not need to be 1. 3. (3 points) Find a closed form solution for rk (which means to first get a recurrence relation and then solve the recurrence) Hint 2.3. Write down the first 5 to 10 values of rk 4. (2 points) Give an algorithm to calculate sk in O(log k)