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

Terms

a(0) =1a(1) =4a(2) =13a(3) =34a(4) =85a(5) =202a(6) =469a(7) =1066a(8) =2389a(9) =5290a(10) =11605a(11) =25258a(12) =54613a(13) =117418a(14) =251221a(15) =535210a(16) =1135957a(17) =2402986a(18) =5068117a(19) =10660522a(20) =22369621a(21) =46836394a(22) =97867093a(23) =204122794a(24) =425022805a(25) =883600042a(26) =1834308949a(27) =3802835626a(28) =7874106709