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

Terms

a(0) =1a(1) =3a(2) =7a(3) =17a(4) =39a(5) =89a(6) =199a(7) =441a(8) =967a(9) =2105a(10) =4551a(11) =9785a(12) =20935a(13) =44601a(14) =94663a(15) =200249a(16) =422343a(17) =888377a(18) =1864135a(19) =3903033a(20) =8155591a(21) =17010233a(22) =35418567a(23) =73633337a(24) =152859079a(25) =316902969a(26) =656175559a(27) =1357090361a(28) =2803659207a(29) =5786275385