首先

\[h_n=\sum_{i}h_ih_{n-i-1}\]

写出 \(h\) 的母函数 \(H(x)\)

那么

\[H(x)=H^2(x)x+1,H(x)=\frac{1-\sqrt{1-4x}}{2x}\]

(解二元一次方程取符号时候要看是否收敛)

引入牛顿二项式

\[(x+y)^{\alpha}=\sum_{k=0}^{\infty}\binom{\alpha}{k}x^{\alpha-k}y^{k}\]

其中

\[\binom{\alpha}{k}=\prod_{i=1}^{k}\frac{\alpha - i + 1}{i}\]

展开可以得到

\[H(x)=\frac{1-\sum_{k=0}^{\infty}\binom{\frac{1}{2}}{k}(-4x)^k}{2x}\]

\[=-\frac{1}{2}\sum_{k=0}^{\infty}\binom{\frac{1}{2}}{k+1}(-4)^{k+1}x^k\]

\[=2\sum_{k=0}^{\infty}\binom{\frac{1}{2}}{k+1}(-4x)^k\]

那么

\[h_n=2\binom{\frac{1}{2}}{n+1}(-4x)^n=2\frac{\prod_{i=0}^{n}(\frac{1}{2}-i)}{(n+1)!}(-1)^n2^{2n}\]

\[=\frac{\prod_{i=0}^{n}(1-2i)}{(n+1)!}(-1)^n2^n=\frac{\prod_{i=1}^{n}(2i-1)}{(n+1)!}2^n=\frac{(2n-1)!!}{(n+1)!}2^n\]

而

\[(2n-1)!!+2^nn!=(2n)!\]

所以

\[h_n=\frac{(2n)!}{n!(n+1)!}=\frac{1}{n+1}\binom{2n}{n}\]

完美解决