Solve Recursive Function I have this recursive equation and I need to write a solution for $E_x$ in terms of $x$ and $n$.
I have tried expanding it for some iterations to see if I could simplify it, but the terms don't simplify. The solutions for non-homogenous recurrence relations don't apply to this either, because of the $E_{\frac{x}{2}}$ term. Is there a math genius who can help me with this? 
$
E_x = (1-\frac{x}{n}) (E_{x-1} + 1) + \frac{x}{n} (E_{\frac{x}{2}}+1)  
$
$
E_1=1
$
 A: That $E_{\frac{x}{2}}$ is the hard part here, I got that for
$E_x = (1-\frac{x}{n}) (E_{x-1} + 1) + \frac{x}{n}+1$
$$E_x=\prod_{k=2}^{x}\left(1-\frac{k}{n}\right)+\sum^{x-1}_{l=2}\left(\left(1+\frac{l}{n}\right)\prod_{m=l+1}^{x}\left(1-\frac{m}{n}\right)\right)+\left(1+\frac{x}{n}\right)$$
And if you still want to fit that $E_{\frac{x}{2}}$;
$$E_x=\prod_{k=2}^{x}\left(1-\frac{k}{n}\right)+\sum^{x-1}_{l=2}\left(\left(1+\frac{lE_{l/2}}{n}\right)\prod_{m=l+1}^{x}\left(1-\frac{m}{n}\right)\right)+\sum_{p=1
}^{z-1}\left(\frac{1}{2^{T(p)}}\left(f\left(\frac{x}{2^p}\right)+1\right)\left(\frac{x}{n}\right)^p\right)+\frac{1}{2^{T(z)}}\left(\frac{x}{n}\right)^z+0^{z-1}$$
Where $z=\lfloor\log_2x\rfloor$ and $T(x)$ is the $x$th triangular number,  but here:
$$T(x)=\frac{x(x-1)}{2}$$
And $$f(x)=\prod_{k=2}^{x}\left(1-\frac{k}{n}\right)+\sum^{x-1}_{l=2}\left(\left(1+\frac{lE_{l/2}}{n}\right)\prod_{m=l+1}^{x}\left(1-\frac{m}{n}\right)\right)$$
All I'm saying is that even if we try to do some simplification we get an ugly monster like this, which is not even an exact formula! There is just an another extention of the recursive formula. Its like the same case of partitions, something where we can come up with recursive relations but a closed form will not be possible using existing mathematical operators.
