# How to evaluate the sum over a hyperplane

I have difficulties in evaluating the following expression:

$$\sum_{\small n_1+...+n_{k}=m-k}\; \prod_{i=1}^{k}\frac{1}{(n_i+1)(n_i+2)}$$

I have tried the function RootSum, but it doesn't work and gives the following warning:

RootSum[Sum[Subscript[n, j], {j, 1, k}] - m + k,
Product[1/((Subscript[n, i] + 2) (Subscript[n, i] + 1)), {i, 1, k}]]


"RootSum::pfn - m + k + $\sum\limits_{j=1}^{k} n_j$ is not a pure function".

I will really appreciate it if someone could give me some hints. Thanks!

-
Could you please write down here the Mathematica expression you've tried to evaluate? –  belisarius Jan 24 '13 at 17:00
@belisarius: RootSum[Sum[Subscript[n, j], {j, 1, k}] - m + k, Product[1/((Subscript[n, i] + 2) (Subscript[n, i] + 1)), {i, 1, k}]] –  user5551 Jan 24 '13 at 17:27
RootSum expects both arguments to be a pure function of a single variable. That's not the case here, and I don't think you can state your problem that way. BTW Any restrictions on the $n_i$'s? Can we assume they are integer or so? For reals it doesn't seem to make sense at all. –  Sjoerd C. de Vries Jan 24 '13 at 18:18

The formula is a little vague because starting limits for the $n_i$ are not given. However, its form suggests it started out as

$$\sum_{(n_1, n_2, \ldots, n_k) \mid 1 \le n_i \wedge n_1+n_2+\cdots+n_k=m} \prod_{i=1}^k \frac{1}{n_i (n_i+1)}$$

for a fixed value of $k$. The relationship to the expression in the question is that we can replace each $n_i$ by $n_i-1$ and allow their values to start at $0$ rather than $1$; their sum is thereby reduced by $k \times 1 = k$ and we obtain precisely the sum in the question, assuming its $n_i$ are allowed to start at $0$ rather than $1$.

In any event, the sum appears to be over all ordered partitions $(n_1, n_2, \ldots, n_k)$ of $m$ consisting of exactly $k$ nonzero values or else it can be re-expressed in such a manner. The crux of the problem is to generate these partitions. This solution relies on the one-to-one-correspondence between any such partition and the set of its distinct partial sums $0, n_1, n_1+n_2, \ldots, n_1+n_2+\cdots+n_k=m$. The intermediate terms determine a $k-1$ element subset of $\{1,2,\ldots,m-1\}$ and, conversely, each such subset when ordered can be construed as such a sequence of partial sums from which all the $n_i$ can be recovered by taking successive differences. Mathematica has a function to produce all such subsets, naturally called Subsets.

All these key elements can be found in the following expression which comprises Subsets to generate the partition data (already sorted), Append and Prepend to tack on the final $m$ and initial $0$, Differences to recover all the $n_i$, Product to multiply the reciprocals, and finally Total to sum the terms:

f[m_Integer, k_Integer] /; 0 < k <= m :=
Product[1/(i (i + 1)), {i, #}] & /@
(Differences[Append[Prepend[#, 0], m]] & /@ Subsets[Range[m - 1], {k - 1}]) // Total


For example, consider the case $m=5, k=2$. The ordered two-partitions of $5$ are $(n_1,n_2)$ = $(1,4), (2,3), (3,2), (4,1)$, introducing terms $\frac{1}{1 \cdot 2}\frac{1}{4 \cdot 5} = \frac{1}{40}$, $\frac{1}{2 \cdot 3}\frac{1}{3 \cdot 4} = \frac{1}{72}$, $\frac{1}{3 \cdot 4}\frac{1}{2 \cdot 3} = \frac{1}{72}$, and $\frac{1}{4 \cdot 5}\frac{1}{1 \cdot 2} = \frac{1}{40}$, respectively. They sum to $\frac{2}{40} + \frac{2}{72}= \frac{7}{90}$. And indeed,

f[5,2]


$\frac{7}{90}$

-