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](https://math.stackexchange.com/questions/1661527/searching-for-a-generating-function-of-a-probability-mass-function), but received no response; I hope it is appropriate to post it here. 



Solving recursion / finding generating function of a probability mass function
I do not think it is possible to get a closed-form of either $f\_n$ or $F\_n$.


For brevity, let's rewrite your recurrence equation for the generating function $a\_n:=F\_n(x)$ as $a\_n = q a\_{n-1} + p a\_{n-1}^2$ with the initial condition $a\_0=x$. Then, change of variables $b\_n = p a\_n + \frac{q}{2}$ will reduce this equation to $b\_n = \frac{(1+p)q}{4} + b\_{n-1}^2$ with $b\_0 = p x + \frac{q}{2}$, which is known as a quadratic map generating the Mandelbrot set and is not generally closed-form solvable. See [[1](http://mathworld.wolfram.com/QuadraticMap.html "Quadratic Map")], which gives more info on possible solutions; however, it will only get you so far that you can find $F\_n(x)$ for some specific points $x$. I guess this is of little interest in your situation.


