binaire rijen

Zij $A_n$ de verzameling van binaire rijen van lengte $n$ die geen drie opeenvolgende termen bevat gelijk aan 0,1,0 (in die volgorde).
Zij $B_{n+1}(k)$ de verzameling binaire rijen van lengte $n+1$ die geen vier opeenvolgende termen bevat gelijk aan $0,0,1,1$ of $1,1,0,0$ heeft (in die volgorde) en begint met de digit $k \in \{0,1\}$.

We claimen nu dat voor vaste $k \in \{0,1\}$ geldt dat $\mid A_n \mid = \mid B_{n+1}(k) \mid,$ waaruit $b_{n+1}=2a_n$ volgt.
Dit doen we door een bijectie te construeren tussen $ B_{n+1}(k)$ en $A_n$.

We beelden een rij $(y_1,y_2,\dots,y_n,y_{n+1}) \in B_{n+1}(k)$ af op een rij $(x_i)_{ 1 \le i \le n}$ waarbij $x_i\equiv y_{i+1}+y_i\mod2$ voor elke $i,$ dit via afbeelding $f$.
We construeren ook een afbeelding $g$ die $(x_i)_{ 1 \le i \le n} \in A_n$ afbeeldt op een rij $(y_1,y_2,\dots,y_n,y_{n+1}) \in\{0,1\}^n$ met $y_1=k$ en recursief via $y_{i+1}=y_i+x_i \pmod 2.$

Dat dit een bijectie tussen de $2$ verzamelingen geeft, volgt uit volgende twee lemma's.
Lemma 1
Merk ten eerste op dat $f \circ g$ en $g \circ f$ de identieke functies zijn.

Bewijs
Bekijk $f \circ g$ in iedere index, $y_1=k$ is duidelijk en $y_{i+1}=y_i+x_i =y_i+(y_{i+1}+y_i) \pmod 2.$ Analoog voor $g \circ f$.

Lemma 2
Het beeld van $f$ ligt in $A_n$ en het beeld van $g$ ligt in $B_{n+1}(k).$

Bewijs
Indien het beeld van $f$ niet in $A_n$ ligt, zijn er $y_i,y_{i+1},y_{i+2},y_{i+3}$ met
$y_i+y_{i+1} \equiv 0 \pmod 2, y_{i+2}+y_{i+1} \equiv 1 \pmod 2$ en $y_{i+2}+y_{i+3} \equiv 0 \pmod 2$ waaruit we vinden dat die $4$ termen gelijk moeten zijn aan $0,0,1,1$ of $1,1,0,0$, contradictie met de definitie van $B_{n+1}(k).$
Analoog voor $g$.