a(n) = 2a(n-1)+a(n-3)+1 with a(1)=1, a(2)=3, a(3)=8.

Terms

a(0) =1a(1) =3a(2) =8a(3) =18a(4) =40a(5) =89a(6) =197a(7) =435a(8) =960a(9) =2118a(10) =4672a(11) =10305a(12) =22729a(13) =50131a(14) =110568a(15) =243866a(16) =537864a(17) =1186297a(18) =2616461a(19) =5770787a(20) =12727872a(21) =28072206a(22) =61915200a(23) =136558273a(24) =301188753a(25) =664292707a(26) =1465143688a(27) =3231476130a(28) =7127244968a(29) =15719633625