The Computer Laboratory

Practice Paper 1 Question 17

Given a sequence of zeros and ones of length \(n\), let \(L_n\) be the number of sequences that have no adjacent zeros. Give a recursive formula for \(L_n\).

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Let \(f_n = 2^n\). Give a recursive formula for \(f_n\).
  2. Let \(G_1 = 1\) and \(G_n = G_{n-1}+3.\) Give a non-recursive expression for \(G_n.\)

Hints

  • Hint 1
    Try to list all the correct sequences for n=1,2,3.
  • Hint 2
    Focus on the first element of a sequence. What cases do you need to consider to reduce a problem to a smaller \(n\)?
  • Hint 3
    If there is a 1 in the first position of a sequence, how many ways (in terms of \(L\)) are there to finish the sequence?
  • Hint 4
    There are \(L_{n-1}\) ways to finish a sequence that begins with a 1. What about a sequence that starts with a 0?
  • Hint 5
    If the sequence begins with 0 what are possible values on the second element and how many ways are there to finish this sequence?

Solution

We are essentially asked to find the relation between the problem of size \(n\) and problems of smaller sizes. Consider the possibilities for the first element of a sequence:

  • If it begins with a \(1\) it can be followed by any sequence of length \(n-1\) with no adjacent 0s. There are \(L_{n-1}\) such words.
  • If it begins with a 0 it has to be followed by a \(1\) and then any word of length \(n-2\) with no adjacent 0s. There are \(L_{n-2}\) such words.

These 2 cases are mutually exclusive, so the total number of such words is \(L_n=L_{n-1}+L_{n-2}\) (hello Professor Fibonacci!).

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.