I have a recurrence relations of polynomials of the following form: \begin{align} h_0 & = x,\\\\ h_1 & = \frac{x + x^2}{2},\\\\ h_d & = \frac{h_{d-2}^2(x)}{2}(1 + h_{d-1}(x)) \qquad \qquad \forall d \geq 2 \end{align}
Say we write $h_d = \sum_{i \geq 0} c_{i, d}x^i$. I am interested in a closed-form expression for $c_{i, d}$ for all values of $i,d$. I would also be happy with the following "tail bound": Given $\epsilon \in [0,1]$ and a positive integer $d$, what is the smallest value of $i_0$ such that $\sum_{i \geq i_0}c_{i,d} \leq \epsilon$? Note that if the additive 1 in the expression for $h_d$ was missing, then I could have defined a linear recurrence $g_d = \log h_d$ and analyzed $g_d$ cleanly, but it doesn't look like this can be done cleanly here. Any help or suggestions would be appreciated.
Here I have collected some observations, but I have not found a closed formula.
The degree of $h_d$ is $2^d$. This is true if $d\in \{0,1\}$ and the recurrence relation implies that it holds for all $d\ge 0$ (one can use induction).
In the other direction, let the order of a polynomial $f(x)=\sum_{i=0}^n a_ix^i$ be the least $i$ such that $a_i\ne 0$. Write $v(f)$ for the order of $f$.
Now the order of $h_d$ starts out as $1,1$ and one can show from the recurrence that $v(h_d)=2v(h_{d-2})$ so that
$$v(h_{2d})=v(h_{2d+1})=2^d$$
Therefore, the non-zero coefficients of $h_{2d}$ are coefficients of $x^p$ only for $2^d\le p\le 2^{2d}$, and the non-zero coefficients of $h_{2d+1}$ are coefficients of $x^p$ only for $2^d\le p\le 2^{2d+1}$.
As you noted in a comment, the sum of all coefficients is one. The sum of coefficients of a polynomial $f$ is just $f(1)$, and in this case $h_d(1)=1$ for $d\in \{0,1\}$ and the recurrence implies that it will remain so for $d\ge 0$.
\begin{align*} h_0&=x\\ h_1&=\frac{x+x^2}{2}\\ h_2&=\frac{2x^2+x^3+x^4}{4}\\ h_3&=\frac{4x^2+8x^3+6x^4+5x^5+5x^6+3x^7+x^8} {32}\\ h_4&=\frac{128 x^4 + 128 x^5 + 176 x^6 + 112 x^7 + 108 x^8 + 92 x^9 + 90 x^{10} + 77 x^{11} + 57 x^{12} + 34 x^{13} + 16 x^{14} + 5 x^{15} + x^{16}}{1024}\\ &\vdots \end{align*}
The recursion also implies that the leading coefficient is two to the power of $$\frac{((-1)^{n + 1} + 2^{n + 2} - 3)}{6}$$.