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

Terms

a(0) =1a(1) =5a(2) =14a(3) =37a(4) =90a(5) =213a(6) =490a(7) =1109a(8) =2474a(9) =5461a(10) =11946a(11) =25941a(12) =55978a(13) =120149a(14) =256682a(15) =546133a(16) =1157802a(17) =2446677a(18) =5155498a(19) =10835285a(20) =22719146a(21) =47535445a(22) =99265194a(23) =206918997a(24) =430615210a(25) =894784853a(26) =1856678570a(27) =3847574869a(28) =7963585194