# Variable number of nested variable-range sums

I would like to express the following nested sum in Mathematica:

$$S(m,j,N) = \sum_{k_1=m+j-1}^{N-1} f(N,k_1) \sum_{k_2=m+j-2}^{k_1-1} f(k_1,k_2) \cdots \sum_{k_m=j}^{k_{m-1}-1} f(k_{m-1},k_m)$$

where $m$, $j$ and $N$ are unspecified and $f(p,q)$ is a complicated function depending on the indices $p$ and $q$. Thus, not only are there a variable number of nested sums, the ranges of the sums are also of variable length, depending on the index of the immediately outer sum.

Can anyone please help me? I've searched for solutions to this on this forum and elsewhere, but could only find solutions that treated the ranges of the sums to be variable but equal.

I eventually need to place $S(m,j,N)$ inside other expressions and functions, so I need to be able to pass $m$, $j$, $N$ as symbols. For example, one expression I ultimately want to obtain is

$$\sum_{m=1}^{N-1} \frac 1 {m!} \sum_{j=1}^{N-m} S(m,j,N),$$

and I would like the solution as an analytic formula, valid for any $N$. I am hoping (and have reason to believe) that the multiple sum $S(m,j,N)$ will simplify down to an easier expression. If you would like to see my definition for the function $f$, here is my code:

phifn[m_, k_] := \[Piecewise] {
{\[Piecewise] {
{1, k = 1},
{0, 2 <= k <= n}
}, m = 1},
{\[Piecewise] {
{((Gamma[m] Pochhammer[q, m - k])/(
Gamma[m - k + 1] Pochhammer[q + 1, m - 1])), 1 <= k <= m},
{0, m < k <= n}
}, 2 <= m <= n}
};
betafn[m_] := (PolyGamma[q + m] - PolyGamma[q]) q r;
f[m_, k_] := phifn[m, k] betafn[m];


I should also add that I'm rather unexperienced when it comes to Mathematica.

-
What kinds of other expressions and functions are you passing S into? –  hftf Apr 21 at 4:40
I'll amend the post again with an example. –  Craig H Apr 21 at 4:43
You say that m “will never be passed as an integer,” but in your example it is passed as an integer. –  hftf Apr 21 at 4:47
hmm, yes. What I should have said is that I want $N$ to remain a symbol. I would like a formula for that example (after putting in my complicated function $f$) that is valid for any integer $N$. I expect the sums to simplify down to an easier expression. –  Craig H Apr 21 at 4:52
Maybe you can provide an example of $f$, as well? I doubt it’s possible with my method because Array and Nest and the like all seem to require an integer in the relevant position. –  hftf Apr 21 at 5:18

I use Array to build up a list of functions for each level of the recursion. Each of those functions takes the next sum as its argument. For example, here is this intermediate list:

Then I use Composition to nest all the functions, and apply the entire function to 1.

foo = Function[{m, j, n},
(Composition @@
Array[
Function[i,
Sum[f[k[i - 1], k[i]] #, {k[i], m + j - i, k[i - 1] - 1}] /. k[0] -> n &]
, m
]
)[1]
];


For example,

foo[4, j, n]


$$\sum _{k_1=j+3}^{n-1} f(n,k_1) \sum _{k_2=j+2}^{k_1-1} f(k_1,k_2) \sum _{k_3=j+1}^{k_2-1} f(k_2,k_3) \sum _{k_4=j}^{k_3-1} f(k_3,k_4)$$

-
The first argument (m) has to be an integer, not a symbol. –  hftf Apr 21 at 4:32
I blindly tried to put your method into Mathematica, however, it returns an error beginning as: Array::ilsmn: Single or list of non-negative machine-sized integers expected at position 2 of Array... Does your method require me to pass a numeric first argument to 'foo'? I want to place this sum inside yet another sum, which sums over the first two indices, so the three arguments to your function 'foo' are never passed as numerals (perhaps I should have said that in the question). Sorry for my ignorant approach; I'm still trying to teach myself what the parts of your answer mean... –  Craig H Apr 21 at 4:35
Ah only seeing your earlier comment now. Unfortunately, I need to be able to pass all arguments as symbols. I'll amend the original post. –  Craig H Apr 21 at 4:36