a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*Fibonacci(k+1).

Terms

a(0) =1a(1) =1a(2) =2a(3) =4a(4) =9a(5) =21a(6) =49a(7) =113a(8) =258a(9) =586a(10) =1329a(11) =3015a(12) =6845a(13) =15549a(14) =35330a(15) =80280a(16) =182413a(17) =414461a(18) =941669a(19) =2139477a(20) =4860898a(21) =11044006a(22) =25092157a(23) =57009871a(24) =129527609a(25) =294289401a(26) =668631458a(27) =1519143916a(28) =3451524785a(29) =7841931877