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

×