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

Terms

a(0) =1a(1) =3a(2) =8a(3) =21a(4) =54a(5) =138a(6) =350a(7) =885a(8) =2230a(9) =5610a(10) =14088a(11) =35346a(12) =88596a(13) =221952a(14) =555738a(15) =1391061a(16) =3480870a(17) =8708610a(18) =21783680a(19) =54483510a(20) =136254964a(21) =340729788a(22) =852000828a(23) =2130354786a(24) =5326563004a(25) =13317759588a(26) =33296999120a(27) =83247698100a(28) =208129274400a(29) =520343244300