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

Terms

a(0) =1a(1) =2a(2) =6a(3) =14a(4) =38a(5) =92a(6) =240a(7) =590a(8) =1510a(9) =3740a(10) =9476a(11) =23564a(12) =59372a(13) =147968a(14) =371636a(15) =927374a(16) =2324870a(17) =5805740a(18) =14538660a(19) =36322340a(20) =90898228a(21) =227153192a(22) =568235696a(23) =1420236524a(24) =3551943388a(25) =8878506392a(26) =22201466280a(27) =55498465400a(28) =138766221800a(29) =346895496200