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

Terms

a(0) =1a(1) =1a(2) =1a(3) =1a(4) =3a(5) =7a(6) =13a(7) =21a(8) =35a(9) =63a(10) =117a(11) =213a(12) =379a(13) =671a(14) =1197a(15) =2149a(16) =3859a(17) =6911a(18) =12357a(19) =22101a(20) =39563a(21) =70847a(22) =126845a(23) =227045a(24) =406371a(25) =727391a(26) =1302101a(27) =2330901a(28) =4172443a(29) =7468767