More generally, one can look for expressions of the form $f(k) = \sum_{j=1}^{\lfloor(n-1)/2\rfloor} a_j f(j) f(n+1-j)$. It seems to work for all odd $k$. For example:
$\eqalign{f \left( 3 \right) &= \left( f \left( 1 \right) \right) ^{2}\cr f \left( 5 \right) &=4\,f \left( 1 \right) f \left( 3 \right) -3\, \left( f \left( 2 \right) \right) ^{2}\cr f \left( 7 \right) &=6\,f \left( 1 \right) f \left( 5 \right) -15\,f \left( 2 \right) f \left( 4 \right) +10\, \left( f \left( 3 \right) \right) ^{2}\cr f \left( 9 \right) &=8\,f \left( 1 \right) f \left( 7 \right) -28\,f \left( 2 \right) f \left( 6 \right) +56\,f \left( 3 \right) f \left( 5 \right) -35\, \left( f \left( 4 \right) \right) ^{2}\cr f \left( 11 \right) &=10\,f \left( 1 \right) f \left( 9 \right) -45\,f \left( 2 \right) f \left( 8 \right) +120\,f \left( 3 \right) f \left( 7 \right) -210\,f \left( 4 \right) f \left( 6 \right) +126\, \left( f \left( 5 \right) \right) ^{2}\cr }$
Hmm, looks like $f(2k+1) = \frac{1}{2}\sum_{j=1}^{2k-1} (-1)^{j+1} {2k \choose j} f(j) f(2k-j) $
Ought to be easy to prove...
EDIT: yes, it is. By the binomial theorem
$ \sum_{j=1}^{2k-1} \sum_{q=1}^n \sum_{r=1}^n (-1)^{j+1} {2k \choose j} q^j r^{2k-j} = \sum_{q=1}^n \sum_{r=1}^n \left(r^{2k} + q^{2k} - (r-q)^{2k}\right)$ and note that $\sum_{q=1}^n \sum_{r=1}^n (r-q)^{2k} = \sum_{s=1}^n 2 (n-s) s^{2k} = 2 n f(2k) - 2 f(2k+1)$