a(n) = n*Fibonacci(n-2) + ((-1)^n + 1)/2.

Terms

a(0) =1a(1) =1a(2) =1a(3) =3a(4) =5a(5) =10a(6) =19a(7) =35a(8) =65a(9) =117a(10) =211a(11) =374a(12) =661a(13) =1157a(14) =2017a(15) =3495a(16) =6033a(17) =10370a(18) =17767a(19) =30343a(20) =51681a(21) =87801a(22) =148831a(23) =251758a(24) =425065a(25) =716425a(26) =1205569a(27) =2025675a(28) =3399005a(29) =5696122