5
$\begingroup$

I have the following sum, $$\sum_{j=0}^{\lfloor\frac{i+n-1}{n+2}\rfloor}(-1)^{j}\binom{n}{j}\binom{i+n-j(n+2)-1}{n-1}+\sum_{j=0}^{\lfloor\frac{i+n-2}{n+2}\rfloor}2(-1)^{j}\binom{n}{j}\binom{i+n-j(n+2)-2}{n-1}+\sum_{j=0}^{\lfloor\frac{i+n-3}{n+2}\rfloor}(-1)^{j}\binom{n}{j}\binom{i+n-j(n+2)-3}{n-1}$$ Notice that the upper bound of each sum is slightly different in each term. I wonder if there is a closed form for this? If we don't have the last binomial in each summation then there would be a closed form but at this level I am not sure how to get the closed form.

Edit: $n$ is non-negative integer, and the constraint on $i$ is as follow: $0\leqslant i\leqslant n(n+1)+2$.

$\endgroup$
6
  • 6
    $\begingroup$ Sweet Christ on a biscuit, where does this abomination come from? $\endgroup$
    – The Count
    Jun 11, 2019 at 16:28
  • $\begingroup$ @TheCount haha it's a result of a messy generating function partly explained and answered here math.stackexchange.com/questions/3250717/… $\endgroup$
    – Wiliam
    Jun 11, 2019 at 16:32
  • 1
    $\begingroup$ Do you have any constraints on $i$ and $n$? A natural example would be $0 \leq i < n$, but that tends to lead to very short sums. $\endgroup$ Jun 11, 2019 at 16:32
  • $\begingroup$ @EricTowers please see the edit :) $\endgroup$
    – Wiliam
    Jun 11, 2019 at 16:36
  • $\begingroup$ @EricTowers fixed. Now there is one constrain on $i$ $\endgroup$
    – Wiliam
    Jun 12, 2019 at 10:08

1 Answer 1

3
$\begingroup$

Note that we can better write each term as $$ \eqalign{ & S(k,n)=\sum\limits_{j = 0}^{\left\lfloor {{{i + n - k} \over {n + 2}}} \right\rfloor } {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr n - 1 \cr} \right)} = \cr & = \sum\limits_{0\, \le j} {\left[ {0 \le i + n - k - j\left( {n + 2} \right)} \right]\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr n - 1 \cr} \right)} = \quad \quad (1) \cr & = \sum\limits_{0\, \le j} {\left[ {0 \le i + n - k - j\left( {n + 2} \right)} \right]\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} = \quad \quad (2) \cr & = \left[ {1 \le n} \right]\sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} \quad \quad (3) \cr} $$ where $[P]$ denotes the Iverson bracket
and where:
- (1) we replace the upper bound with Iverson bracket;
- (2) we can apply reflection, since the upper term of the binomial is non-negative;
- (3) we can omit the Iverson bracket, because for $1 \le n$ it is implicit in the binomial.

Note that $S(k,n)$ is equivalent to $$ S(k,n) = N_{\,b} (i + 1 - k,\,n + 1,n) $$ where $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ is the number discussed in this related post, and is also called the "r-nomial coefficient" since $$ F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^m $$

Now, the cumulative sum of $N_b$ has a similar expression $$ M_{\,b} (t,\,r,m) = \sum\limits_{0\, \le s\; \le \,\,t} {N_{\,b} (s,\,r,m)} = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{t \over {r + 1}}\, \le \,m} \right)} {\left( { - 1} \right)^k \binom {m}{k} \binom{ t + m - k\left( {r + 1} \right)} {t - k\left( {r + 1} \right) } } $$ but this does not help to simplify much your sum, since it will always leave three terms.

The attempt to directly perform the sum will give: $$ \eqalign{ & S(n) = \left[ {1 \le n} \right]\sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\left( \matrix{ 2 \cr k \cr} \right)\sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,j} \left( \matrix{ 2 \cr k \cr} \right)\left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,k + j} \left( \matrix{ k - 3 \cr k \cr} \right)\left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - \left( {k + j} \right) - j\left( {n + 1} \right) \cr i + 1 - \left( {k + j} \right) - j\left( {n + 1} \right) \cr} \right)} } = \cr & = \sum\limits_{0\, \le l} {\sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,l} \left( \matrix{ l - j - 3 \cr l - j \cr} \right)\left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - l - j\left( {n + 1} \right) \cr i + 1 - l - j\left( {n + 1} \right) \cr} \right)} } \cr} $$ and we cannot proceed to simplify by applying double correlation, due to the presence of $\left( { - 1} \right)^{\,l}$

We could instead simplify the related sum $$ \eqalign{ & S_{\, - } (n) = \sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ 2 \cr k \cr} \right)S(k,n)} = \cr & = \sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ 2 \cr k \cr} \right)\sum\limits_{} {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} } = \cr & = \sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,2} \right)} {\left( \matrix{ k - 3 \cr k \cr} \right)\left( \matrix{ i + n - k - j\left( {n + 2} \right) \cr i + 1 - k - j\left( {n + 2} \right) \cr} \right)} } = \cr & = \sum\limits_{0\, \le j} {\left( { - 1} \right)^{\,j} \left( \matrix{ n \cr j \cr} \right)\left( \matrix{ i + n - 2 - j\left( {n + 2} \right) \cr i + 1 - j\left( {n + 2} \right) \cr} \right)} \cr} $$ so that the actual sum may be reduced to two terms.

Besides these, and other related manipulations, I do not see better ways.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .