1×n棋盘带着色限制的铺砖问题：递推关系的组合数学推导问询

我最近在解一个谜题的时候碰到了这么个问题：

给定一块1×n的棋盘，还有长度从1到n的瓷砖——除了1×1的瓷砖有两种颜色可选（红色和绿色），其他长度的瓷砖都是灰色的。请问一共有多少种不同的铺法？这里的“不同”既包括瓷砖组合方式的差异，也包含颜色选择的区别。

我用另一种思路解这个谜题时，发现答案满足这样的递推关系：
$x(n) = 2x(n-1) + \sum_{i=0}^{n-2}x(i)$
其中初始条件是 $x(0)=0$，$x(1)=1$。而且这个序列其实就是奇数项的斐波那契数列 $f(2n-3)$。

但我一直没法从组合计数的角度，直接推导出来为什么这个递推关系是成立的。我查了不少资料，也没找到类似的问题，自己深入琢磨的时候总觉得卡壳。如果有人能给我讲讲递推关系的组合意义、指出我可能忽略的关键点，或者给点思路上的提示，我真的会非常感激！

备注：内容来源于stack exchange，提问作者HG11