The determination of

\(C_k\) is a standard kind of problem in combinatorics. One solution is by way of a recurrence relation. In fact, many problems in combinatorics are most easily solved by first searching for a recurrence relation and then solving it. The following observation will suggest the recurrence relation that we need to determine

\(C_k\text{.}\) If

\(k \geq 2\text{,}\) then every string of 0’s and 1’s with length

\(k\) and no two consecutive 0’s is either

\(1s_{k-1}\) or

\(01s_{k-2}\text{,}\) where

\(s_{k-1}\) and

\(s_{k-2}\) are strings with no two consecutive 0’s of length

\(k - 1\) and

\(k - 2\) respectively. From this observation we can see that

\(C_k= C_{k-2}+C_{k-1}\) for

\(k\geq 2\text{.}\) The terms

\(C_0=
1\) and

\(C_1 = 2\) are easy to determine by enumeration. Now, by iteration, any

\(C_k\) can be easily determined. For example,

\(C_5 = 21\) can be computed with five additions. A closed form expression for

\(C_k\) would be an improvement. Note that the recurrence relation for

\(C_k\) is identical to the one for

The Fibonacci Sequence. Only the basis is different.