a(n) = (5*n/18 + 19/54)*2^n - (-1)^(n-1)*(3*n + 4)/27.

Terms

a(0) =1a(1) =4a(2) =9a(3) =24a(4) =55a(5) =130a(6) =293a(7) =660a(8) =1459a(9) =3206a(10) =6977a(11) =15096a(12) =32463a(13) =69482a(14) =148061a(15) =314332a(16) =665067a(17) =1402958a(18) =2951545a(19) =6194368a(20) =12971271a(21) =27107634a(22) =56545429a(23) =117751204a(24) =244823075a(25) =508287510a(26) =1053857713a(27) =2182280840a(28) =4513692479a(29) =9325646586