关于长度为n的最多含两个连续相同位的比特串递推关系验证

首先，我们先通过小例子验证你的递推是否合理：

• 当n=1时，符合条件的比特串是0、1，共2个，所以T(1)=2；
• 当n=2时，符合条件的串是00、01、10、11，共4个，T(2)=4；
• 当n=3时，我们不能有000或111，所以符合条件的串是001、010、011、100、101、110，共6个。

如果用你的递推式T(n)=2T(n-1)+T(n-2)，计算n=3的话，结果是2*4+2=10，这和实际的6个明显不符，所以这个递推关系是错误的。

正确的递推关系推导 #

我们可以通过状态转移的方法来推导：
定义四个状态，用来区分串的结尾情况：

• f(n,0,1)：长度为n，以1个连续0结尾的串的数量；
• f(n,0,2)：长度为n，以2个连续0结尾的串的数量；
• f(n,1,1)：长度为n，以1个连续1结尾的串的数量；
• f(n,1,2)：长度为n，以2个连续1结尾的串的数量；

总数量T(n) = f(n,0,1) + f(n,0,2) + f(n,1,1) + f(n,1,2)。

接下来推导状态转移规则：

1. 要得到以1个0结尾的串，前一个字符必须是1（不管前一个串结尾是1个还是2个连续1），所以：f(n,0,1) = f(n-1,1,1) + f(n-1,1,2)；
2. 要得到以2个连续0结尾的串，前一个串必须是以1个0结尾的，加一个0即可：f(n,0,2) = f(n-1,0,1)；
3. 同理，以1个1结尾的串，前一个字符必须是0：f(n,1,1) = f(n-1,0,1) + f(n-1,0,2)；
4. 以2个连续1结尾的串，前一个串必须是以1个1结尾的：f(n,1,2) = f(n-1,1,1)；

现在把T(n)用上面的转移式展开：

T(n) = [f(n-1,1,1)+f(n-1,1,2)] + f(n-1,0,1) + [f(n-1,0,1)+f(n-1,0,2)] + f(n-1,1,1)

整理后可以发现：

• 第一部分f(n-1,1,1)+f(n-1,1,2)+f(n-1,0,1)+f(n-1,0,2)就是T(n-1)；
• 第二部分f(n-1,0,1)+f(n-1,1,1)，代入n-2的状态转移，会发现这部分等于T(n-2)；

最终得到正确的递推关系：
$$T(n) = T(n-1) + T(n-2)$$
初始条件为T(1)=2，T(2)=4。

我们可以验证一下：

• T(3)=T(2)+T(1)=4+2=6（和实际一致）；
• T(4)=T(3)+T(2)=6+4=10（实际计数也为10）；
• T(5)=10+6=16（实际计数正确）；

这样就完全符合实际情况了。

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