フィボナッチ数が現れる問題（７）

フィボナッチ数が現れる問題（７）を紹介します。

（７）4種の数字(1,2,3,4)から数字列を作る。
　　　長さnの数字列s₁s₂…s_nにおいて、s₁=1,|s_i-s_i-1|=1(2≦i≦n)となる
　　　ただし、同じ数字を何回使ってもよい。
　　　数字列の個数g(n)はフィボナッチ数になる。

　　g(n)= g(n-1)+ g(n-2)　(n≧3)
　　g(1)=1, g(2)=1