a(n) = a(n-1) + a(n-2) + 2 a([(n-1)/2]), where a(0) = 1, a(1) = 2, a(2) = 3.

Terms

a(0) =1a(1) =2a(2) =3a(3) =9a(4) =16a(5) =31a(6) =53a(7) =102a(8) =173a(9) =307a(10) =512a(11) =881a(12) =1455a(13) =2442a(14) =4003a(15) =6649a(16) =10856a(17) =17851a(18) =29053a(19) =47518a(20) =77185a(21) =125727a(22) =203936a(23) =331425a(24) =537123a(25) =871458a(26) =1411491a(27) =2287833a(28) =3704208a(29) =6000047