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

Terms

a(0) =1a(1) =4a(2) =16a(3) =46a(4) =124a(5) =310a(6) =748a(7) =1750a(8) =4012a(9) =9046a(10) =20140a(11) =44374a(12) =96940a(13) =210262a(14) =453292a(15) =972118a(16) =2075308a(17) =4412758a(18) =9349804a(19) =19748182a(20) =41593516a(21) =87381334a(22) =183151276a(23) =383079766a(24) =799713964a(25) =1666536790a(26) =3467291308a(27) =7203018070a(28) =14942907052a(29) =30959555926