Gọi \(c_n\) là số xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài.
Ta có: \(c_1=2; \ c_2=3.\)
Xét xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài có dạng \(a_{n}a_{n-1}a_{n-2}...a_{2}a_{1}.\)
Có hai trường hợp:
TH1: \(a_n=1. \) Khi đó \(a_{n-1}=0\) và \(a_{n-2}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-2\) thỏa điều kiện. Có \(c_{n-2}\) xâu như vậy, suy ra trường hợp này có \(c_{n-2}\) xâu.
TH2: \(a_n=0\). Khi đó \(a_{n-1}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-1\) thỏa điều kiện. Có \(c_{n-1}\) xâu như vậy, suy ra trường hợp này có \(c_{n-1}\) xâu.
Vậy tổng cộng xây dựng được \(c_{n-1}+c_{n-2}\) xâu hay \(c_n=c_{n-1}+c_{n-2}.\)
\(\Rightarrow c_n=\dfrac{\sqrt5-2}{\sqrt5} \begin{pmatrix} \dfrac{1-\sqrt5}{2} \end{pmatrix}^{n-1}+\dfrac{2-\sqrt5}{\sqrt5} \begin{pmatrix} \dfrac{1+\sqrt5}{2}\end{pmatrix}^{n-1}\)