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

Terms

a(0) =1a(1) =3a(2) =3a(3) =7a(4) =19a(5) =31a(6) =59a(7) =135a(8) =259a(9) =495a(10) =1035a(11) =2071a(12) =4051a(13) =8191a(14) =16475a(15) =32679a(16) =65443a(17) =131343a(18) =262059a(19) =523831a(20) =1049203a(21) =2097439a(22) =4192763a(23) =8389575a(24) =16779331a(25) =33550383a(26) =67108683a(27) =134226007a(28) =268427539a(29) =536862271