0
$\begingroup$

Is there a nice way to write the following repeated sum $$ \sum_{a_1=1}^{i+(2-k)} \sum_{a_2=1}^{i-(a_1-(3-k))}\sum_{a_3=1}^{i-(a_1+a_2-(4-k))}\sum_{a_4=1}^{i-(a_1+a_2+a_3-(5-k))}\dotsb\sum_{a_k=1}^{i-(a_1+a_2+a_3+\dotsb+a_{k-1}-1)} \left[A + \sum_{\ell=0}^{i-(a_1+a_2+\dotsb+a_k)} B_{\ell} + \sum_{p=i-(a_1+a_2+...+a_k-1)}^{i-(a_2+\dotsb+a_k-1)} C_{p} +\dotsb+\sum_{q=i-(a_k-1)}^{i} D_{q} \right], $$ where $i$ and $k$ are positive integers without any condition (i.e. $i \ge k$ or $k \ge i$), as a single sum? If any closed form about a few repeated sums can be advised, I will generalize for the rest. Of course, one way is to write it is $$ \sum_{a_j,1\le j \le k}^{i-(\sum_{\ell=1}^{j-1} a_{\ell}-(j-k+1))}, $$ but I want some appealing form.

$\endgroup$
11
  • $\begingroup$ You're missing a summand. $\endgroup$ Nov 28, 2021 at 22:36
  • $\begingroup$ @SamHopkins, yes, the summand itself is quite complicated involving products and exponentials, which will make my question horrible. $\endgroup$
    – Ahmed Khan
    Nov 28, 2021 at 22:42
  • $\begingroup$ What do all the tags have to do with the problem? $\endgroup$
    – LSpice
    Nov 28, 2021 at 22:47
  • 2
    $\begingroup$ So it's the sum over all combinations of $k$ positive (and non-zero, for people who use the French convention) integers which sum to no more than $i+1$? $\endgroup$ Nov 28, 2021 at 23:41
  • $\begingroup$ The tags should reflect what your question is about, not external context that is irrelevant to the question. If the external context is relevant to the question, then you should include it. (Also, your comment appears to be truncated.) $\endgroup$
    – LSpice
    Nov 28, 2021 at 23:55

1 Answer 1

1
$\begingroup$

$\newcommand{\N}{\mathbb N}\newcommand{\Si}{\Sigma}$For integers $n$ and $k$, let $A_{n,k}$ denote the set of all $a=(a_1,\dots,a_k)\in\N^k$ such that $\sum_1^k a_j\le n$, and let $c_{n,k}$ denote the cardinality of the set $A_{n,k}$. For $a\in A_{n,k}$, let $s_p:=s_p(a):=\sum_1^p a_j$.

We want to simplify the sum \begin{equation*} \Si:=\sum_{a\in A_{i+1,k}} \Big(A+\sum_{l=0}^{i-s_k}B_l +\sum_{r=1}^{k-1}\;\sum_{p=i+1-s_k+s_{r-1}}^{i+1-s_k+s_r}C_{r,p}+\sum_{q=i+1-a_k}^i D_q\Big), \label{1}\tag{1} \end{equation*} where $A,B_l,C_{r,p},D_q$ are arbitrary numbers. More precisely, we want to (get rid of $\sum_{a\in A_{i+1,k}}$ and) find the coefficients of $A,B_l,C_{r,p},D_q$ in $\Si$. That is, we want to write the identity \begin{equation*} \Si=A\,\Si_A+\sum_{l=0}^{i-k}B_l\,\Si_{B_l} +\sum_{r=1}^{k-1}\;\sum_{p=r-1}^{k-r}C_{r,p}\,\Si_{C_{r,p}}+\sum_{q=k-1}^i D_q\,\Si_{D_q}, \label{2}\tag{2} \end{equation*} where the coefficients $\Si_A,\Si_{B_l},\Si_{C_{r,p}},\Si_{D_q}$ of $A,B_l,C_{r,p},D_q$ do not depend on $A,B_l,C_{r,p},D_q$ -- but only on $i$, $k$, and the respective indices $l,r,p,q$.

The key here is this simple lemma:

Lemma 1: $c_{n,k}=\binom nk$ for any nonnegative integers $n$ and $k$.

This follows by induction, using the recursion \begin{equation*} c_{n,k}=\sum_{a_k=1}^\infty c_{n-a_k,k-1}=\sum_{a_k=1}^{n-(k-1)} c_{n-a_k,k-1} =\sum_{j=k-1}^{n-1}c_{j,k-1}. \label{3}\tag{3} \end{equation*}

It is also easy to give a "bijective" proof of Lemma 1. However, \eqref{3} is more succinct and will be used in what follows.

Immediately from Lemma 1, we get \begin{equation*} \Si_A=c_{i+1,k}=\binom {i+1}k. \label{4}\tag{4} \end{equation*}

Next, the condition $0\le l\le i-s_k$ on $l$ in \eqref{1} means that $l\ge0$ and $s_k\le i-l$. So, \begin{equation*} \Si_{B_l}=\sum_{a\in A_{i+1,k}}1(s_k\le i-l)=c_{i-l,k}=\binom {i-l}k, \label{5}\tag{5} \end{equation*} again by Lemma 1.

Further, the condition $i+1-a_k\le q\le i$ on $q$ in (1) means that $q\ge i$ and $a_k\ge i+1-q$. The condition $a\in A_{i+1,k}$ also implies $s_{k-1}\le i+1-a_k$. So, once again by Lemma 1, \begin{equation*} \begin{aligned} \Si_{D_q}&=\sum_{a\in A_{i+1,k}}1(a_k\ge i+1-q,s_{k-1}\le i+1-a_k) \\ &=\sum_{a_k=i+1-q}^\infty\binom {i+1-a_k}{k-1} =\sum_{j=-\infty}^q\binom j{k-1} =\binom {q+1}k; \end{aligned} \label{6}\tag{6} \end{equation*} cf. \eqref{3}.

It remains to find $\Si_{C_{r,p}}$. The condition $i+1-s_k+s_{r-1}\le p\le i+1-s_k+s_r$ on $p$ in \eqref{1} together with the condition $a\in A_{i+1,k}$ mean that \begin{equation*} i+1-p-a_r\le \sum_{j=r+1}^k a_j\le\min(i+1-p,i+1-a_r-s_{r-1}). \label{7}\tag{7} \end{equation*} Note that $0\le s_{r-1}\le i-k+r$ for $a\in A_{i+1,k}$. So, \begin{equation*} \Si_{C_{r,p}}=\sum_{s=0}^{i-k+r}N_{r,s}\Si_{C_{r,p};s}, \label{8}\tag{8} \end{equation*} where $N_{r,s}$ is the cardinality of the set of all $(a_1,\dots,a_{r-1})\in\N^{r-1}$ such that $\sum_1^{r-1} a_j=s$, and $\Si_{C_{r,p};s}$ is the cardinality of the set of all $(a_r,\dots,a_k)\in\N^{k-r+1}$ such that inequalities \eqref{7} hold with $s$ in place of $s_{r-1}$.

Note that $N_{r,s}=N_{r,\le s}-N_{r,\le s-1}$, where $N_{r,\le s}$ is the cardinality of the set of all $(a_1,\dots,a_{r-1})\in\N^{r-1}$ such that $\sum_1^{r-1} a_j\le s$. So, $N_{r,\le s}=c_{s,r-1}=\binom s{r-1}$, by Lemma 1. So, $N_{r,s}=\binom s{r-1}-\binom{s-1}{r-1}=\binom{s-1}{r-2}$ if $r\ge2$. However, the equality \begin{equation*} N_{r,s}=\binom{s-1}{r-2} \label{9}\tag{9} \end{equation*} holds even for $r=1$. (Alternatively, the case $r=1$ can be similarly considered separately).

Once again by Lemma 1, \begin{equation*} \begin{aligned} \Si_{C_{r,p};s} &=\sum_{a_r=1}^{p-s}\Big(\binom {i+1-p}{k-1}-\binom {i-p-a_r}{k-1}\Big) \\ & +\sum_{a_r=p-s+1}^\infty\Big(\binom {i+1-a_r-s}{k-1}-\binom {i-p-a_r}{k-1}\Big) \\ &=(p-s)\binom {i+1-p}{k-1} +\sum_{j=-\infty}^{i-p}\binom j{k-1} \\ &-\sum_{a_r=1}^\infty\binom {i-p-a_r}{k-1} \\ &=(p-s)\binom {i+1-p}{k-1}+\binom {i+1-p}k-\binom {i-p}k \\ &=(p-s)\binom {i+1-p}{k-1}+\binom {i-p}{k-1} \\ &=\Big[p\binom {i+1-p}{k-1}+\binom {i-p}{k-1}\Big] -s\binom {i+1-p}{k-1}. \end{aligned} \end{equation*} here we also reasoned as in \eqref{3}.

The latter expression is linear (I mean affine) in $s$. So, in view of \eqref{8} and \eqref{9}, to obtain $\Si_{C_{r,p}}$, it suffices to note that \begin{equation*} \sum_{s=1}^{i-k+r}\binom{s-1}{r-2}=\binom {i+1-k+r}{r-1} \end{equation*} and \begin{equation*} \sum_{s=1}^{i-k+r}s\binom{s-1}{r-2} =(r-1)\sum_{s=1}^{i-k+r}s\binom s{r-1}=(r-1)\binom{i+1-k+r}r. \end{equation*} Collecting the pieces, we finally get \begin{equation*} \begin{aligned} &\Si_{C_{r,p}}=\Big[p\binom {i+1-p}{k-1}+\binom {i-p}{k-1}\Big]\binom {i+1-k+r}{r-1} \\ &-(r-1)\binom {i+1-p}{k-1} \binom{i+1-k+r}r. \end{aligned} \label{10}\tag{10} \end{equation*}

Thus, we have \eqref{2} with the coefficients $\Si_A,\Si_{B_l},\Si_{C_{r,p}},\Si_{D_q}$ of $A,B_l,C_{r,p},D_q$ given by \eqref{4}, \eqref{5}, \eqref{6}, \eqref{10}.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.