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

Terms

a(0) =1a(1) =4a(2) =13a(3) =36a(4) =93a(5) =228a(6) =541a(7) =1252a(8) =2845a(9) =6372a(10) =14109a(11) =30948a(12) =67357a(13) =145636a(14) =313117a(15) =669924a(16) =1427229a(17) =3029220a(18) =6407965a(19) =13514980a(20) =28428061a(21) =59652324a(22) =124897053a(23) =260978916a(24) =544327453a(25) =1133394148a(26) =2356266781a(27) =4891490532a(28) =10140895005a(29) =20997617892