Cho hai số nguyên dương $n\geq k$, gọi $S_k(n)$ là số chuỗi nhị phân có độ dài $n$ không chứa chuỗi gồm toàn số $0$ hoặc $1$ có độ dài $k$, $C_k(n)$ là số chuỗi nhị phân có độ dài $n$ không chứa chuỗi gồm toàn số $0$.
Chứng minh rằng: $S_{k+1}(n+1)=2C_k(n)$