a(n) = (1/2) * Sum_{k=0..floor(n/3)} 2^k * binomial(2*n-4*k+2,2*k+1).

Terms

a(0) =1a(1) =2a(2) =3a(3) =8a(4) =25a(5) =62a(6) =139a(7) =340a(8) =877a(9) =2186a(10) =5311a(11) =13056a(12) =32497a(13) =80566a(14) =198595a(15) =490092a(16) =1212597a(17) =2999522a(18) =7411207a(19) =18311384a(20) =45265657a(21) =111902478a(22) =276579275a(23) =683566148a(24) =1689580733a(25) =4176276794a(26) =10322491919a(27) =25513684656a(28) =63061990401a(29) =155871106406