I am assessing the probability distribution on a running time of some algorithm that we've developed. I am looking for a family of probability mass functions $f_n$ with the following recurrence: $$ f_{n}(k)=qf_{n-1}(k)+p\sum_{i=1}^{k-1}f_{n-1}(i)f_{n-1}(k-i), $$ with the starting term $$ f_{0}(k)=\begin{cases} 1; & k=1,\\ 0; & \mbox{otherwise.} \end{cases} $$

In terms of generating function $F_{n}(x)=\sum_{i=0}^{\infty}f_{n}(i)\,x^{i}$ this simplifies to $$ F_{n}(x)=qF_{n-1}(x)+pF_{n-1}(x)^{2}, $$ but (as Ser B. pointed out) it looks like $F_n(x)$ does not seem to admit closed-form expression. That said, finding a value of $\frac{\partial F_n}{\partial x}$ where $x=1$ would also help, as this should equal to the expected value of $k$ in the space with probability mass function $f_n$.

As you might expect, we have $q=1-p$ and $ p,q \in [0,1]$. I have asked this question on M.SE, but received no response; I hope it is appropriate to post it here.

1more comment