Question

组合数学问题

将长度为n的、没有两个0或者两个1相连的三进制字符串（由0，1，2组成的字符串）的个数记为 。首先建立 的递推关系，然后求出 的通项公式。

Answer 1

将长度为n的开头为0的这样的个数记做a（n）
将长度为n的开头为1的这样的个数记做b（n）
将长度为n的开头为2的这样的个数记做c（n）
总数记做x（n）
则a（1）=b（1）=c（1）=1；x（1）=3，x（2）=7；
a（n）=b（n-1）+c（n-1）
b（n）=a（n-1）+c（n-1）
c（n）=a（n-1）+b（n-1）+c（n-1）=x（n-1）
三式相加x（n）=2x（n-1）+c（n-1）=2x（n-1）+x（n-2）
也就是x（n）=2x（n-1）+x（n-2），x（1）=3，x（2）=7
有了初始项和递推公式，通项公式就按照公式求就行啦，带根号和n次方的，不好打出来~