# Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows

$F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{l=j-1}^{m} F_{k,l}(m-ij) \right ]$

It's given that $F_{i,j}(m)=0$ for $m<0$.

Here $x_{ij}$ is defined as a random number with the property that $0<x_{ij}<j$.

How do I write a recursive algorithm to compute $F_{i,j}(m)$?

• Ironic, given your username, but could you be more precise? The $x_{ij}$ have what distribution? Are they resampled every time the sum is evaluated or are they fixed? Is the naive implementation too slow? Did you try dynamic programming? – David Richerby Mar 27 '15 at 20:48
• $x_{ij}$ is uniformly distributed random number and it is re-sampled every time the sum is evaluated. I am trying to build a recursive algorithm for it so that for a given i,j and m, the function fun(i,j,m) can compute $F_{i,j}(m)$. – precision Mar 27 '15 at 21:01
• What is provided as inputs? Are the $x_{ij}$'s provided as part of the input, along with $i,j,m$? – D.W. Mar 27 '15 at 21:19
• Inputs are $i,j ,m$. Every time I have to compute $x_{ij}$ for each k,l and m. – precision Mar 27 '15 at 21:27
• OK. So $F_{i,j}(m)$ is not a number; it is a random variable. So it's not clear what you want. Do you want to sample a single value from $F_{i,j}(m)$? Do you want to compute the distribution of $F_{i,j}(m)$? If the latter, we'll need to know what the base cases are (so we can evaluate how large $F_{i,j}(m)$ might get, as a function of $i,j,m$ and the $x$'s). – D.W. Mar 28 '15 at 4:28

Assuming we are given the $x_{ij}$'s and $i,j,m$, your formula already is a recursive algorithm to compute $F_{i,j}(m)$. If you use dynamic programming (memoization) to avoid re-computing $F_{i',j'}(m')$ more than once for any given tuple $(i',j',m')$, the running time will be $O(m^3)$, since you only evaluate $F_{i',j'}(m')$ for tuples $(i',j',m')$ where $0 \le i',j',m' \le m$.
If the $x_{ij}$'s are not given, your question is not well-defined. If that's what you meant, it's possible you might be asking for us to compute the distribution of $F_{i,j}(m)$, but if so, the question needs to be edited accordingly.
Either way, I suspect that there must be some additional base cases you have not provided. As it currently stands, the solution $F_{i,j}(m)=0$ for all $i,j,m$ satisfies your equation. I suggest you edit your question to specify the missing base cases.