Ones Stick Together

Let \( P : \mathbb{N} \rightarrow \mathbb{N} \) be the counting function such that \(P(n) \) denote the number of ways of making unique strings of 1's and 0's of length \(n\) such that any "1" in this string is next to another.

Eg \( P( 4 ) = 7 \) since the only valid ways of making the valid strings of length 4 are

\[ \begin{align*} &0000 \\ &0011 \\ &0110 \\ &0111 \\ &1100 \\ &1110 \\ &1111 \\ \end{align*} \]

Which of the following recursions relationships are true for all \(n \ge 4 \)?

Notation: \(\mathbb N \) denotes the set of natural numbers.

×

Problem Loading...

Note Loading...

Set Loading...