6. [5 marks] A CPSC 121 student who was feeling bored during the three days between midterm #1 and the release of assignment #3 wrote a program to generate all sequences of n bits that do not contain two consecutive O's. The student found that there were 2 such sequences for n = 1 (the sequences are "0" and "1"), 3 for n = 2 (the sequences "01", "10" and "11"), and 5 for n = 3. He then hypothesized that the number S(n) of these sequences satisfies the equation: S(n) = n+1 if n 3 S(n-1) + S(n - 2) One of the student's friends (a MATH major) then confirmed this, and told him that S(n) is approx- imately equal to a. [3 marks] The student's program generates 50 sequences per seconds. Fill in the following table with the largest value of n for which his program terminates for each duration indicated. Duration Largest value of n || DurationLargest value of n 1 second 1 minute 1 hour 1 day 1 month 1 year 10 years 100 years b. [2 marksOne of the CPSC 121 TAs then tells the student a C version of the program would run 50 times faster than the Dr. Racket version the student wrote. Will the C version help the student solve the problem for a much larger value of n than the Dr. Racket version, when the program is allowed to run for 100 years? Why or why not? 6. [5 marks] A CPSC 121 student who was feeling bored during the three days between midterm #1 and the release of assignment #3 wrote a program to generate all sequences of n bits that do not contain two consecutive O's. The student found that there were 2 such sequences for n = 1 (the sequences are "0" and "1"), 3 for n = 2 (the sequences "01", "10" and "11"), and 5 for n = 3. He then hypothesized that the number S(n) of these sequences satisfies the equation: S(n) = n+1 if n 3 S(n-1) + S(n - 2) One of the student's friends (a MATH major) then confirmed this, and told him that S(n) is approx- imately equal to a. [3 marks] The student's program generates 50 sequences per seconds. Fill in the following table with the largest value of n for which his program terminates for each duration indicated. Duration Largest value of n || DurationLargest value of n 1 second 1 minute 1 hour 1 day 1 month 1 year 10 years 100 years b. [2 marksOne of the CPSC 121 TAs then tells the student a C version of the program would run 50 times faster than the Dr. Racket version the student wrote. Will the C version help the student solve the problem for a much larger value of n than the Dr. Racket version, when the program is allowed to run for 100 years? Why or why not