Is it possible to solve this recurrence relation?

Question

For any real $0<x\leq1$, let $E(x)=1$.

For any reals $0<a_1,a_2,\ldots,a_n\leq1$ with $a_1+a_2+\cdots+a_n\leq1$,

let $E(a_1,a_2,\ldots,a_n)=1+\displaystyle\sum_{k=1}^n\dfrac{a_k}{1-a_k} E(a_1,a_2,\ldots,a_{k-1},a_{k+1},a_{k+2},\ldots,a_n)$ for $n>1$.

For example, $E(a_1,a_2)=1+\dfrac{a_1}{1-a_1}E(a_2)+\dfrac{a_2}{1-a_2}E(a_1)=1+\dfrac{a_1}{1-a_1}+\dfrac{a_2}{1-a_2}$,

and $E(a_1,a_2,a_3)=1+\dfrac{a_1}{1-a_1}E(a_2,a_3)+\dfrac{a_2}{1-a_2} E(a_1,a_3)+\dfrac{a_3}{1-a_3}E(a_1,a_2)$ $=1+\dfrac{a_1}{1-a_1} \left(1+\dfrac{a_2}{1-a_2}+\dfrac{a_3}{1-a_3}\right)+\dfrac{a_2}{1-a_2} \left(1+\dfrac{a_1}{1-a_1}+\dfrac{a_3}{1-a_3}\right)+\dfrac{a_3}{1-a_3} \left(1+\dfrac{a_1}{1-a_1}+\dfrac{a_2}{1-a_2}\right)$

Is it possible to find the closed form of $E(a_1,a_2,\ldots,a_n)$ ?

Thanks in advance.

Answer 1

Let's denote $\frac{a_k}{1-a_k}=f(k)$ for brevity .

From the look of the recurrence I made the following nice combinatorial interpretation which instantly shows the answer:

We start forming a permutation of $1,2,\ldots ,k$ . At every step we may either choose a new element not already chosen or to say STOP at which the process terminates . We must say a STOP before forming a complete permutation .

I'll denote a STOP simply with an S .

For example for $n=3$ the possible sequences are :

$S$ ; $1,S$ ; $2,S$ ; $3,S$ ; $1,2,S$ ; $2,1,S$ ; $1,3,S$ ; $3,1,S$ ; $2,3,S$ and $3,2,S$

Now if one of the sequences is $x_1,\ldots , x_l,S$ then in the sum we will add :

$$f(x_1)f(x_2)\ldots f(x_l)f(S)$$ with the convention that $f(S)=1$ .

It's easy to see that this interpretation gives the same results as the sum (in the recurrence that $1$ represents the STOP and $f(k)$ the number $k$ that we choose if we don't stop .)

Now with this interpretation it's pretty simple to solve the problem :

Let's count how many times does a term $f(x_1)f(x_2)\ldots f(x_l)$ appears in the sum . It should be obvious that this term appears only for the sequences of the form :

$$\pi(1),\pi(2),\ldots,\pi(n),S$$ where $\pi$ is only a permutation of those $l$ numbers . There are $l!$ such permutations so such a term is to be found $l!$ times in the sum .

I don't think this can be simplified more than this .

To give a complete answer :

If $A=\left \{a_1,a_2,\ldots,a_n \right \}$ then your expression is :

$$\sum_{I \subset A} \mid I \mid ! \prod_{x \in A} \frac{x}{1-x}$$

Answer 2

For any integer $n \ge 1$, let $F_n$ be the $n$-ary function defined below. $$F_n(u_1,u_2,\ldots,u_n)\stackrel{def} = \int_0^\infty \left[ \prod_{k=1}^n(1 + tu_k) - t^n \prod_{k=1}^n u_k \right] e^{-t} dt\tag{*1}$$ In particular $F_2(u,v) = 1 + u + v$. Integrate the first piece of $(*1)$ by part, we find $$\begin{align} \verb/RHS/(*1) &= \left[- e^{-t} \prod_{k=1}^n(1+tu_k)\right]_{t=0}^\infty + \sum_{k=1}^n u_k \int_0^\infty \left[\prod_{\ell=1,\ne k}^n (1+tu_\ell)\right] e^{-t} dt - n! \prod_{k=1}^n u_k\\ &= 1 + \sum_{k=1}^n u_k \int_0^\infty \left[\prod_{\ell=1,\ne k}^n (1+tu_\ell) - t^{n-1}\prod_{\ell=1,\ne k}^n u_\ell\right] e^{-t}dt\\ &= 1 + \sum_{k=1}^n u_k F_{n-1}(u_1,\ldots,u_{k-1},u_{k+1},\ldots,u_n) \end{align} $$ Substitute $u_k$ by $\frac{a_k}{1-a_k}$, we find above relations reduces to the one satisfied by $E$. Notice $$F_2\left(\frac{a}{1-a},\frac{b}{1-b}\right) = 1 + \frac{a}{1-a} + \frac{b}{1-b} = E(a,b)$$ By induction, we find for any $n \ge 2$.

$$\begin{align} E(a_1,\ldots,a_n) &= F_n\left(\frac{a_1}{1-a_1},\ldots,\frac{a_n}{1-a_n}\right)\\ &= \frac{1}{\prod_{k=1}^n (1-a_k)}\int_0^\infty \left[\prod_{k=1}^n(1 + (t-1)a_k) - t^n \prod_{k=1}^n a_k\right] e^{-t} dt \end{align} $$ For positive integer $m \le n$, let $e_m$ be the $m^{th}$ elementary polynomial associated with the $n$ numbers $a_1, \ldots a_n$. $$e_m \stackrel{def}{=} \prod\limits_{1\le j_1 < j_2 < \cdots < j_m \le n} \prod_{i=1}^m a_{j_i}$$

In terms of the elementary polynomials, we can simplify the integrand above $$\prod_{k=1}^n(1 + (t-1)a_k) - t^n \prod_{k=1}^n a_k = \left( 1 + \sum_{k=1}^{n} (t-1)^n e_k \right) - t^n e_n$$ As a result, we get

$$E(a_1,\ldots,a_n) = \frac{1}{\prod_{k=1}^n(1-a_k)}\left[ 1 + \sum_{k=1}^{n-1} D_k e_k + (D_n - n!) e_n \right]\tag{*2}$$

where $$D_n = \int_0^\infty (t-1)^n e^{-t} dt = n!\left(\sum_{s=0}^n\frac{(-1)^s}{s!}\right) = \left\lfloor \frac{n!}{e} + \frac12 \right\rfloor$$ are the $n^{th}$ derangement number.

Please note that given $n$ numbers $a_1, \ldots, a_n$, formula $(*2)$ allow one to compute $E(a_1,\ldots,a_n)$ in polynomial time. This is because one can compute all the elementary polynomials $e_k$ one need by multiplication of $n$ monomials $$1 + \sum_{k=1}^n t^k e_k = \prod_{k=1}^n ( 1 + ta_k)$$ and that take $O(n^2)$ scalar multiplications/additions. For comparison, a naive evaluation of $E(a_1,\ldots,a_n)$ using its recursive definition need $O(n!)$ operations.