# There are $6$ digits containing $1$ and $0$, only problem is that $0$'s can't be next to each other

Mathematics Asked by Yağız Alp Ersoy on November 29, 2020

Imagine this: There are $$6$$ digits which can contain either $$1$$ or $$0$$. For example: $$100110$$
Only problem is that $$0$$‘s can’t be next to each other. For example, $$101101$$ is fine.
How many combinations are there that is a no-no and how many combinations that are fine?

Let $$a_n$$ be the number of sequences of length $$n$$ ending in $$1$$ and $$b_n$$ be the number of sequences of length $$n$$ ending in $$0$$. Suppose my sequence ends in $$1$$. Then I could add either a $$0$$ or a $$1$$. However, if my sequence ends in $$0$$, I can only add a $$1$$. So

$$a_{n+1} = a_n + b_n,$$ $$b_{n+1} = a_n.$$ Now if we know $$a_1 = 1$$, $$b_1 = 1$$, let's determine $$a_6$$. We have

$$a_2 = 2, b_2 = 1, a_3 = 3, b_3 = 2, a_4 = 5, b_4 = 3, a_5 = 8, b_5=5, a_6 = 13, b_6=8.$$

Here's a question: Can you tell me what $$a_n$$ and $$b_n$$ are for any $$n$$?

Regardless, the total number of admissable sequences will be $$a_6 + b_6 = 21$$. The total number of sequences will be $$2^6$$ (why?) so the total number of nonadmissable sequences will be $$2^6 - 21 = 43$$.

Here's another way to think about it: Let $$A = begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix} = begin{pmatrix} a(1) & b(1) \ a(1) & 0 end{pmatrix}.$$ Then $$A begin{pmatrix} 1 \ 1 end{pmatrix} =begin{pmatrix} a(1) + b(1) \ a(1) end{pmatrix} = begin{pmatrix} a(2) \ b(2) end{pmatrix}.$$

By inducting, we see

$$A^{n-1} begin{pmatrix} 1 \ 1 end{pmatrix} = begin{pmatrix} a(n) \ b(n) end{pmatrix}.$$ Let $$|(a,b)^T| = a + b.$$ Then

$$|A^{n-1} cdot (1,1)^T| = text{ total number of admissable sequences}.$$

Correct answer by User203940 on November 29, 2020