# 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.. Please do not write to this address regarding general admissions or course queries. tasc@sulp.ecitcarp