Interleave n+1 and 2n+1 and take binomial transform.

Terms

a(0) =1a(1) =2a(2) =5a(3) =13a(4) =32a(5) =76a(6) =176a(7) =400a(8) =896a(9) =1984a(10) =4352a(11) =9472a(12) =20480a(13) =44032a(14) =94208a(15) =200704a(16) =425984a(17) =901120a(18) =1900544a(19) =3997696a(20) =8388608a(21) =17563648a(22) =36700160a(23) =76546048a(24) =159383552a(25) =331350016a(26) =687865856a(27) =1426063360a(28) =2952790016a(29) =6106906624