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

Related Questions

Minimum of $n$ geometric random variables

3  Asked on December 15, 2021

Fundamental group of Klein Bottle

2  Asked on December 15, 2021 by jos-luis-camarillo-nava

Derivative of $h(x,t)=gleft(frac{x}{t^2}right)$

3  Asked on December 15, 2021 by charith

Lottery – Probability Discrepancy

2  Asked on December 15, 2021 by cannon444

prove the spectral theorem for commutative operators with guidance

0  Asked on December 15, 2021

Show numeric unstability of Cramer’s rule

1  Asked on December 15, 2021

Need an upper bound for a simple expectation involving Rademacher random variables.

1  Asked on December 15, 2021 by golabi

Question concerning prime ideals of $mathbb{C}[x,y]$

2  Asked on December 15, 2021

Why is the solution to a non-homogenous linear ODE written in terms of a general fundamental solution and not a matrix exponential?

1  Asked on December 15, 2021

$F=p_1times p_2$ a hyperbolic space?

0  Asked on December 15, 2021

How to prove that $(a^m)^n=a^{mn}$ where $a,m,n$ are real numbers and a>0?

3  Asked on December 15, 2021 by orlin-aurum

Find locus of point

0  Asked on December 15, 2021

Nonlinear dynamics and state space trajectories of networks with time-dependent architecture

0  Asked on December 15, 2021 by neuroguy

I don’t understand Gödel’s incompleteness theorem anymore

5  Asked on December 15, 2021

If $T(p(t)) = p(t+1)$ then find its minimal polynomial where $T$ is a linear operator from $Bbb{P_n} rightarrow Bbb{P_n}$

2  Asked on December 13, 2021

about the Laguerre square expansion Sin(x)

0  Asked on December 13, 2021 by charlessilva

If $p$ and $q$ are coprime positive integers s.t. $frac{p}{q}=sum_{k=0}^{100}frac1{3^{2^k}+1}$, what is the smallest prime factor of $p$?

1  Asked on December 13, 2021

Prove that a Tower of Height $H$ can be built if $H*(H+1)/2 = R + G$

2  Asked on December 13, 2021 by het

How can I find the solution around $r=1$ for this ODE?

0  Asked on December 13, 2021

Can I square both sides of inequality for these functions?

1  Asked on December 13, 2021 by user807688