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

Terms

a(0) =1a(1) =2a(2) =4a(3) =8a(4) =17a(5) =38a(6) =88a(7) =208a(8) =497a(9) =1194a(10) =2876a(11) =6936a(12) =16737a(13) =40398a(14) =97520a(15) =235424a(16) =568353a(17) =1372114a(18) =3312564a(19) =7997224a(20) =19306993a(21) =46611190a(22) =112529352a(23) =271669872a(24) =655869073a(25) =1583407994a(26) =3822685036a(27) =9228778040a(28) =22280241089a(29) =53789260190