# Nested ordered summation

How can I implement the following sum?

Given $n$ and $j<n$:

$$\sum_{k_j=1}^{n-1}\sum_{k_{j-1}=1}^{k_j-1}\sum_{k_{j-2}=1}^{k_{j-1}-1}\dots\sum_{k_1=1}^{k_2-1} \phi_{(n-k_j)}[\phi_{(k_j-k_{j-1})}[\phi_{(k_{j-1}-k_{j-2})}[\dots[\phi_{(k_2-k_1)}[\phi_{(k_1)}[x_0]]]$$

At the moment my code is very simple, for example n=4,j=3:

Sum[Sum[Sum[ϕ[4-k3][ϕ[k3-k2][ϕ[k2-k1][ϕ[k1][x0]]]],{k1,1,k2-1}], {k2,1,k3-1}],{k3,1,4-1}]

• Generally, users here like it when you provide some amount of starting code. Maybe this doc page would be of use in the meantime? – enano9314 May 3 '18 at 22:14
• At the moment my code is very simple: – Kowalski May 3 '18 at 22:19

## 1 Answer

Using Fold:

n = 4;
j = 3;

Sum[
Fold[f[#2][#1] &, f[k[1]][x0], Differences@Append[Array[k, j], n]]
, Evaluate[Sequence @@ Prepend[Table[{k[i], 1, k[i + 1] - 1}, {i, j - 1, 1, -1}], {k[j], 1, n - 1}]]
]