a(1) = 1, a(2) = 2; a(2*k) = 2*a(2*k-1) - a(2*k-2), a(2*k+1) = 4*a(2*k) - a(2*k-1).

Terms

a(0) =1a(1) =2a(2) =7a(3) =12a(4) =41a(5) =70a(6) =239a(7) =408a(8) =1393a(9) =2378a(10) =8119a(11) =13860a(12) =47321a(13) =80782a(14) =275807a(15) =470832a(16) =1607521a(17) =2744210a(18) =9369319a(19) =15994428a(20) =54608393a(21) =93222358a(22) =318281039a(23) =543339720a(24) =1855077841a(25) =3166815962a(26) =10812186007a(27) =18457556052a(28) =63018038201a(29) =107578520350