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 and their content are not associated with the Climb Foundation unless otherwise specified. They are provided as is.

  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.$

Try to list all the correct sequences for n=1,2,3.

Focus on the first element of a sequence. What cases do you need to consider to reduce a problem to a smaller $n$?

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?

There are $L_{n-1}$ ways to finish a sequence that begins with a 1. What about a sequence that starts with a 0?

If the sequence begins with 0 what are possible values on the second element and how many ways are there to finish this sequence?

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!).

The content on this page is best viewed on a display wider than that of a phone, to avoid clipping long math expressions. If any math content looks wrong then please try another browser (e.g. Brave).