Solving a Binomial Recurrence Related to this problem: Expected Homogenization Time
When calculating the expected number of iterations for that problem, in terms of $N$, I get the recurrence $E(N)=1+\dfrac{1}{2^N}\displaystyle\sum_{k=0}^N\binom{N}{k}E(k)$. Does this recurrence have a nice closed form solution?
 A: Quite surprisingly, yes. Take $f_E(x)$ as:
$$ f_E(x) = \sum_{j\geq 0}\frac{x^j}{j!}E(j).$$
Then:
$$ e^x f_E(x) = \sum_{N\geq 0}\frac{x^N}{N!}\sum_{k=0}^{N}\binom{N}{k}E(k) $$
so the recurrence gives:
$$f_E(x) = e^x-1+e^{x/2}f_E(x/2).\tag{1}$$
By setting $g(x)=f_E(x)\,e^{-x}$ it follows that:
$$ g(x) = 1-e^{-x}+ g(x/2),\tag{2} $$
$$ g'(x) = e^{-x}+\frac{1}{2}g'(x/2),\tag{3} $$
so:
$$ g'(x) = \sum_{h=0}^{+\infty}\frac{1}{2^h e^{\frac{x}{2^h}}},\qquad g(x)=\sum_{k=0}^{+\infty}\left(1-e^{-x/2^k}\right) $$
and:
$$ f_E(x) = e^x \sum_{k=0}^{+\infty}\left(1-e^{-x/2^k}\right). \tag{4}$$
Since:
$$ 1-e^{-x/2^k}=\sum_{n=1}^{+\infty}\frac{(-1)^{n+1}}{2^{kn}n!}x^n $$
we have:
$$ g(x) = \sum_{n=1}^{+\infty}\frac{(-1)^{n+1}2^n}{(2^n-1)n!}x^n\tag{5}$$
and so:
$$ E(N)=\sum_{k=1}^{N}\frac{(-1)^{k+1}2^k}{(2^k-1)}\binom{N}{k}.\tag{6}$$
By expanding $\frac{2^k}{2^k-1}$ as a geometric series and using the binomial theorem, we get the alternative representation:
$$ E(N) = 1+\left(1-\left(\frac{1}{2}\right)^n\right)+\left(1-\left(\frac{3}{4}\right)^n\right)+\left(1-\left(\frac{7}{8}\right)^n\right)+\ldots\tag{7}$$
from which it follows that $E(N)$ grows like $\frac{4}{3}+\log_2 N$.
