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

Terms

a(0) =1a(1) =5a(2) =18a(3) =52a(4) =137a(5) =339a(6) =808a(7) =1874a(8) =4263a(9) =9553a(10) =21158a(11) =46416a(12) =101029a(13) =218447a(14) =469668a(15) =1004878a(16) =2140835a(17) =4543821a(18) =9611938a(19) =20272460a(20) =42642081a(21) =89478475a(22) =187345568a(23) =391468362a(24) =816491167a(25) =1700091209a(26) =3534400158a(27) =7337235784a(28) =15211342493