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
    $\begingroup$ Sweet Christ on a biscuit, where does this abomination come from? $\endgroup$ – The Count Jun 11 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$ – William Jun 11 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$ – Eric Towers Jun 11 at 16:32
  • $\begingroup$ @EricTowers please see the edit :) $\endgroup$ – William Jun 11 at 16:36
  • $\begingroup$ @EricTowers fixed. Now there is one constrain on $i$ $\endgroup$ – William Jun 12 at 10:08
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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