遞迴關係式

一個1*n的棋盤上,有紅色的,白色的,藍色的小方塊想要填滿整個棋盤
其中,紅色的小方塊數目是偶數,且至少要一個藍色的小方塊,請問其遞
迴關係式為何?
例如 : (r=紅色,b=藍色,w=白色)
n=1時,只有一種,就是 b
n=2時有三種,就是bw,wb或bb
n=3時有10種 (bbb,bbw,bwb,bww,wwb,wbw,wbb,rrb,rbr,brr)
n=4時有33種

[解]
設一個1*(n+1)的棋盤上填滿整個棋盤有 f(n+1) 個方法
(1) 若第1格塗白色，則接下去的1*n的棋盤上填滿整個棋盤有 f(n) 個方法
(2) 若第1格塗藍色，則接下去的1*n的棋盤上填滿整個棋盤有
C(n,0)×2^n +C(n,2)×2^(n-2) +C(n,4)×2^(n-4) +……個方法
(3) 若第1格塗紅色，則接下去的1*n的棋盤上填滿整個棋盤有
C(n,1)×(2^(n-1)-1)+C(n,3)×(2^(n-3)-1)+C(n,5)×(2^(n-5)-1)+……個方法
因此 f(n+1) = f(n) + C(n,0)×2^n +C(n,2)×2^(n-2) +C(n,4)×2^(n-4) +……
+ C(n,1)×(2^(n-1)-1)+C(n,3)×(2^(n-3)-1)+C(n,5)×(2^(n-5)-1)+……
= f(n) + C(n,0)×2^n +C(n,1)×2^(n-1) +C(n,2)×2^(n-2) + C(n,3)×2^(n-3)+….
- [C(n,1)+C(n,3)+C(n,5)+…….]
= f(n) + 3^n- (2^(n-1))
但 f(1) = 1，n為自然數，f(n+1) = f(n) + 3^n- (2^(n-1))