Let $f:\mathbb{N}\rightarrow\mathbb{R}, h:\mathbb{N}\rightarrow\mathbb{R}$ be two functions satisfying $f(0)=h(0)=1$ and: $$f(n) = \sum_{i=0}^{n}h(i)h(n-i)$$ Find a closed form for $h(n)$ in terms of $f(1), f(2)...f(n)$.
Calculating the first ones gives:
$h(1) = f(1)/2$
$h(2) = f(2)/2-f(1)^2/8$
$h(3) = f(3)/2-f(1)f(2)/4+f(1)^3/16$.
It's obvious that it's some kind of sum over the partitions but the coefficients are a mystery. Any ideas?
Consider construction this formal series $F = \sum _{i = 0}^{\infty}f(i)x^i$ and $H = \sum _{i = 0}^{\infty}h(i)x^i$, then if you consider $$H^2 = \sum _{n = 0}^{\infty}\left (\sum _{i = 0}^nh(i)h(n-i)\right )x^n,$$ this is Cauchy's convolution. This means that you relation is $F = H^2$, and so $$H = F^{1/2} = ((F-1)+1)^{1/2} = \sum _{k = 0}^{\infty}\binom{1/2}{k}(F-1)^k,$$ this last equality is Generalized Binomial Theorem. The "partitions" you are looking at are doing Cauchy $k$ times in $(F-1)^k$ and the coefficients you are looking at are $$\binom{1/2}{k}=\frac{\left (\frac{1}{2}\right )\left (\frac{1}{2}-1\right )\cdots \left (\frac{1}{2}-(k-1)\right )}{k!},$$ so that, for example, for $k = 3$, you get $$\binom{1/2}{3}=\frac{(1/2)\cdot (-1/2)\cdot (-3/2)}{6}=\frac{3}{8\cdot 6}=\frac{1}{16},$$ which is the number you are seeing when computing $h(3)$.
