a(n) = Sum_{k=0..floor(n/4)} C(n-2*k,2*k) * 3^k.

Terms

a(0) =1a(1) =1a(2) =1a(3) =1a(4) =4a(5) =10a(6) =19a(7) =31a(8) =55a(9) =109a(10) =220a(11) =424a(12) =793a(13) =1489a(14) =2845a(15) =5473a(16) =10480a(17) =19954a(18) =37963a(19) =72391a(20) =138259a(21) =263989a(22) =503608a(23) =960400a(24) =1831969a(25) =3495505a(26) =6669865a(27) =12725425a(28) =24276892a(29) =46314874