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

Terms

a(0) =1a(1) =2a(2) =4a(3) =10a(4) =32a(5) =104a(6) =324a(7) =1000a(8) =3136a(9) =9992a(10) =32064a(11) =103168a(12) =332816a(13) =1077152a(14) =3497024a(15) =11381920a(16) =37121280a(17) =121285760a(18) =396922944a(19) =1300906112a(20) =4269367296a(21) =14028169344a(22) =46143475712a(23) =151932559360a(24) =500710965504