如何正式证明n≥4时长为n且不含子串10的比特串数Bₙ=n+1？

没问题，我来给你梳理这个结论的严谨正式证明，核心是先明确符合条件的比特串的唯一结构，再通过计数完成推导：

步骤1：刻画符合条件的比特串的结构 #

我们首先证明：长度为n的比特串不含子串"10"，当且仅当它的所有0都出现在所有1的前面（包含全0或全1的极端情况）。

必要性（正向推导） #

假设存在一个不含子串"10"的比特串，但它不满足“全0在前、全1在后”的结构。这意味着串中至少存在一个位置i（1≤i<n），使得第i位是1，第i+1位是0——这就直接构成了子串10，与“不含子串10”的前提矛盾。因此，所有符合条件的串必须是前面若干个0、后面跟着若干个1的结构。

充分性（反向推导） #

反过来，任意一个“前k个0，后n−k个1”（k为0到n之间的整数）的比特串，显然不会包含子串10：因为所有0都集中在串的前半部分，所有1集中在后半部分，不存在“1后面紧跟0”的情况。

步骤2：计数符合条件的比特串数量 #

对于长度为n的串，我们可以通过选择0的个数k来唯一确定每个符合条件的串：

• 当k=0时，串为11...1（n个连续的1）；
• 当k=1时，串为011...1（1个0，后面跟着n-1个1）；
• ...
• 当k=n时，串为00...0（n个连续的0）。

k的取值可以是0、1、2、...、n，一共n+1个不同的取值，每个取值对应唯一的一个符合条件的比特串，且所有符合条件的串都被完全覆盖（没有遗漏）。

最终结论 #

综上，长度为n（n≥1）的不含子串10的比特串数量Bₙ = n+1，该结论对所有n≥1都成立（不仅仅是n≥4，比如n=1时B₁=2=1+1，n=2时B₂=3=2+1，都符合规律）。

内容的提问来源于stack exchange，提问作者udpcon