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

Terms

a(0) =1a(1) =2a(2) =5a(3) =11a(4) =25a(5) =55a(6) =121a(7) =263a(8) =569a(9) =1223a(10) =2617a(11) =5575a(12) =11833a(13) =25031a(14) =52793a(15) =111047a(16) =233017a(17) =487879a(18) =1019449a(19) =2126279a(20) =4427321a(21) =9204167a(22) =19107385a(23) =39612871a(24) =82021945a(25) =169636295a(26) =350457401a(27) =723284423a(28) =1491308089a(29) =3072094663