Sum(C(j)*(n-j)*4^(n-j-1),j=0..n-1), C = Catalan numbers.

Terms

a(0) =0a(1) =1a(2) =9a(3) =58a(4) =325a(5) =1686a(6) =8330a(7) =39796a(8) =185517a(9) =848830a(10) =3827230a(11) =17053356a(12) =75249954a(13) =329353948a(14) =1431575220a(15) =6185613032a(16) =26589395581a(17) =113780713806a(18) =484945025942