# 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\).

## Related topics

## Warm-up Questions

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

## Hints

- Hint 1Try to list all the correct sequences for n=1,2,3.
- Hint 2Focus on the first element of a sequence. What cases do you need to consider to reduce a problem to a smaller \(n\)?
- Hint 3If 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 4There are \(L_{n-1}\) ways to finish a sequence that begins with a 1. What about a sequence that starts with a 0?
- Hint 5If 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.[email protected]. Please do not write to this address regarding general admissions or course queries.