The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

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