Ones Stick Together

Here's a quick, intuitive solution!

$P( n ) = \text{ The number of ways of making unique strings of 1s and 0s of length n such that any 1 in this string is next to another. }$ $= \text{ The number of ways that end in 0 1s + The number of ways that end in 2 1s + The number of ways that end in more than 2 1s. }$

But $\text{ The number of ways that end in 0 1s }$ is all the valid strings that end in a $0$ . The amount that satisfy this is $P(n-1)$ since if we remove the $0$ on the end, the other $n-1$ must satisfy the conditions of $P(n-1)$ .

Similarly we have $\text{ The number of ways that end in 2 1s }$ is just all the valid strings that end in $011$ . This is just $P(n-3)$ since if we take away the zero on the end, the other $n-3$ must satisfy the conditions of $P(n-3)$ .

Finally for $\text{ The number of ways that end in more than 2 1s }$ , all of these end in a $1$ . What happens if we remove that final $1$ ? We must still have some new string that ends in atleast $2$ $1$ s. So this is all the the strings of P(n-1) that end in a 1. How many have this property? It's $P(n-1) - P(n-2)$ , can you see why?

Finally, adding all of this together gives our desired relation that's valid for all $n \ge 4$ .

---

Bonus Questions

• Can you see another way to derive the correct answer?

• Can you find a closed form formula for $n$ ?

• Can you find any other reccurrence relations for this function?

• What happens if we change it so we have to have any 1s have to part of 3 in a row instead of 2?

• What happens if we add more numbers we are allowed to use with similar restrictions?

• Can you find any cool generating functions for this function?