5
$\begingroup$

$$\sum_{n_m>n_{m-1}>\dots>n_1\ge 1}n_1(-1)^{(n_1+n_2+...+n_m)} $$

I know for the case where the terms are all positive, i.e: $$\sum_{n_m\ge n_{m-1}\ge\dots\ge n_1\ge 1}n_1 $$

You retrieve the $m$-dimensional equivalent of the $n_m$th "tetrahedral" number given by $\binom{n_m+m-1}{m}$.

I was wondering if the same was true for the above. When I try to work it out, I end up picking up so many extra terms that I can't trust myself to not make any mistakes.

$\endgroup$
4
  • $\begingroup$ I personally think the problem is posed fine as is (you clearly put some work into it and ot doesn't look like a homework problem), but it might be a good idea to either show what work you have already done, or give some context about why you're interested in this sum. It should help you avoid more downvotes. $\endgroup$ Sep 4, 2023 at 18:59
  • $\begingroup$ Reminds me of the difference between determinant and permanent. $\endgroup$ Sep 4, 2023 at 20:20
  • $\begingroup$ For the first sum, the indices are constrained to be strictly decreasing, but for the second sum, they are only weakly decreasing. Is there a typo? $\endgroup$ Sep 5, 2023 at 14:59
  • 1
    $\begingroup$ Looking at this sum makes me slightly nauseated. The $n_m$ does not have the same status as the other $n_i$... it is fixed, not a variable of summation like the others. I know you're just taking the notation from wikipedia but I have no idea why they chose to write it like this ;_; $\endgroup$ Sep 5, 2023 at 16:35

2 Answers 2

5
$\begingroup$

1. The Short Version

For the remainder of this post I will be setting $N:=n_m$ and never speaking about it again. I believe I've been clear in the comments about why I'm making this choice.

Here is the no-frills answer to your question:

  • If $m$ is even and $N$ is even: $\displaystyle \binom{\frac{N}{2}+\frac{m}{2}-1}{\frac{m}{2}}$.
  • If $m$ is even and $N$ is odd: $\displaystyle \binom{\frac{N-1}{2}+\frac{m}{2}}{\frac{m}{2}}$.
  • If $m$ is odd and $N$ is even: $2\displaystyle \binom{\frac{N}{2}+\frac{m-1}{2}}{\frac{m+1}{2}}$. Note the $-1$ versus $+1$.
  • If $m$ is odd and $N$ is odd: $-2\displaystyle \binom{\frac{N-1}{2}+\frac{m-1}{2}}{\frac{m+1}{2}} - \binom{\frac{N}{2}+\frac{m-1}{2}}{\frac{m-1}{2}}$.

Note that we can combine the two "$m$ even" cases to obtain BillyJoe's prediction. Also, you're free to do your own check, but this does agree with their data as well. For instance if $m=9$ and $N=7$ then $$-2\displaystyle \binom{\frac{7-1}{2}+\frac{9-1}{2}}{\frac{9+1}{2}} - \binom{\frac{7-1}{2}+\frac{9-1}{2}}{\frac{9-1}{2}} = -42-35=-77.$$


2. An Apologetic Prelude

First of all, this is long. Grab some water. Take breaks.

I think it's natural to see the formulae above and wonder why it came out so dang complicated. There is actually a short answer to this: you have asked the wrong question.

Let me qualify that. I do not think yours is a bad question, and I hope that the effort that I put into the post is enough to convey that. It is, in fact, a very thoughtful question, and certainly the question points in a very interesting direction. And the sense in which the question is wrong is one of those things that could not be known when asking it, so I put no fault on you. But it turns out that you have used a somewhat unfortunate definition of the triangular numbers. For, you see:

$$\sum_{N\geq n_{m-1}\geq \dots\geq n_1\geq 1} n_1 = \sum_{N\geq n_{m-1}\geq \dots\geq n_1\geq n_0\geq 1} 1.$$

Either choice is fine when we simply add the terms up, of course, but when it comes time to put signs on them, it matters whether we start the recursion at the "one-dimensional" versus "zero-dimensional" triangular numbers.

To this end, for any nonnegative $a$ and $b$, define $S_{a,b}$ to be the "start-at-0D" alternating sum; precisely, $S_{a,b}=\displaystyle\sum_{b\geq k_a\geq \cdots k_1\geq 0} (-1)^{k_1+k_2+\cdots+k_a}$. Then the answer is prettier:

Lemma. For any non-negative $a$ and $b$, $$ S_{a,b}= \begin{cases} 0 & a,b\text{ are both odd} \\\\ \displaystyle\binom{\lfloor\frac{a}{2}\rfloor+\lfloor\frac{b}{2}\rfloor}{\lfloor\frac{a}{2}\rfloor} & \text{otherwise} \end{cases} $$

This Lemma is hard. So for now, let us take it as a black box and show how we use it to answer the question that you did ask.


3. The Hero of Our Story

In this bit, we will make heavy use of a certain identity which I will call Chu's Theorem. In the Western world it's more commonly known as the "Hockey Stick Identity" (because of the shape it makes in Pascal's triangle), but I prefer the attribution.

Chu's Theorem. Let $A$ and $B$ be nonnegative integers. Then $$ \sum_{k=0}^A \binom{B+k}{B} = \binom{A+B+1}{B+1}.$$

Now remember we are trying to compute this sum:

\begin{align*} \sum_{N\geq n_{m-1}\geq \dots\geq n_1\geq 1} & n_1 (-1)^{n_1+\cdots+n_{m-1}+N} \\ &= (-1)^N\sum_{n_1=1}^N \left[n_1(-1)^{n_1} \sum_{N\geq n_{m-1}\geq \dots\geq n_2\geq n_1} (-1)^{n_2+\cdots+n_{m-1}}\right] \\ &= (-1)^N\sum_{n_1=1}^N \left[n_1(-1)^{n_1}(-1)^{n_1(m-2)} \sum_{N-n_1\geq k_{m-2}\geq \dots\geq k_1\geq 0} (-1)^{k_1+\cdots+k_{m-2}}\right] \\ &= (-1)^N\sum_{n_1=1}^N n_1(-1)^{n_1(m-1)} S_{m-2,N-{n_1}} \end{align*} Despite the dense algebra, very little has happened. The main event was reindexing the sum by setting $k_i=n_{i+1}-n_1$ so we could more easily recognize the non-$n_1$ summations were giving an $S_{a,b}$. Keep the signs straight and we're there.1

From here, we apply the Lemma and set the hero to work on the four cases: $m$ is odd or even, and $N$ is odd or even. Each of these is annoying in it's own special way2, so let me only do one in full.

Suppose $m$ and $N$ are both even. Immediately remove the leading $(-1)^N$. Now, if $n_1$ is also even, observe that it "nearly cancels" with the $n_1-1$ term, because $S_{m-2,N-n_1}=S_{m-2,N-n_1+1}$. In particular, using all the parity information we have, we can see that the sum of these two terms is $(n_1-(n_1-1))S_{m-2,N-n_1}$. Moreover, because $N$ is even, this pairs up all terms in the sum.

Thus, let us reindex the sum via $k=\frac{N-n_1}{2}$ (for even $n_1$), leading to $$\sum_{n_1=1}^N n_1(-1)^{n_1(m-1)} S_{m-2,N-{n_1}} = \sum_{k=1}^{N/2}\binom{\frac{m}{2}-1+k}{\frac{m}{2}-1}.$$

Finally, use Chu's Theorem to simplify.

The reindexing that we did here seems kind of random, but it turns out that all four cases benefit from the exact same substitution: $k=\frac{N-n_1}{2}$. Unfortunately, they benefit in different ways, and I couldn't find a unifying pattern.

The rest of this post is a proof of the Lemma. It will be longer than strictly necessary because I want to do it "from very nearly nothing." Nevertheless, I wish to stress that the Lemma is quite a deep result, even having close ties to the linear algebra of finite vector spaces. Any proof you find will either be relatively lengthy, or use advanced machinery/cleverness.


4. Building Blocks

In broad strokes, we will be using the Description-Involution-Exception method, otherwise known as the method of sign-reversing involutions. These are fancy words to describe the following simple idea:

  • If you are counting some set but some things count positively and some things count negatively (Description)...
  • and if we find a way to pair off each of the positive and negative things (Involution)...
  • then the total sum will be zero.
  • Even if we cannot pair off everything, if we can at least describe the things that do not get paired off (Exception), then we can reduce to a smaller signed sum.

We begin with a description of what $S_{a,b}$ counts. Note that if we draw $1\times k_i$ rectangles, left-justified and stacked on top of one another (so $k_a$ is on top, and $k_1$ is on bottom), then the condition $b\geq k_a\geq \cdots k_1\geq 0$ implies that the resulting shape sits "triangularly" in the top-left corner of an $a\times b$ box:

A partition fitting into a box

Considered this way, the list $(k_i)$ is often called a partition (of size $n=k_1+\cdots+k_a$), and the drawing is called its Young diagram. In $S_{a,b}$,we count the partitions positively if they have even size, and negatively if they have odd size.

There is a very natural involution on Young diagrams sitting inside an $a\times b$ box; simply take the "other half" of the box:

The opposite of a partition in a box is a rotated partition

True, the other half is not literally a Young diagram, but it is if you rotate 180 degrees! This does indeed "pair off" the partitions: if you do this operation twice, you get back to where you started.3 The trouble is with the sign.

One sees immediately that that the size of the two partner partitions is equal to $ab$, and thus if both $a$ and $b$ are odd then these partitions have opposite signs. Hence, for the reasons laid out initially, $S_{a,b}=0$.

It remains to consider the case when either $a$ or $b$ is even.


5. Proof of the Lemma

To simplify matters, note that $S_{a,b}=S_{b,a}$ by another geometric argument: we can reflect the Young diagram across the top-left-to-bottom-right diagonal. Therefore, without loss of generality we may assume that $b$ (the width of the box) is even.

We proceed by strong induction4 on $a+b$. The base case is classic annoying trivial combinatorics: if $a+b=0$ then both $a$ and $b$ are zero, and so while it looks like the sum is empty, it isn't because the zero-tuple "$()$" is a partition fitting inside of the $0\times 0$ box.5

Let's focus on the case of exactly one even parameter, that is, $b$ is even and $a$ is odd. We can't use our odd-odd involution... unless the partition happens to fit into an $a\times (b-1)$ box, right? And that does indeed happen quite often: whenever the top row of the partition is not $b$, then it is strictly less than $b$, and also all lower rows are strictly less than $b$, so it does fit into that odd-odd box. But it's even better: whenever it doesn't fit into that odd-odd box, then some of the $k_i$ necessarily are equal to $b$. Since $b$ is even, we can simply remove those rows from both the box and the partition (without changing its sign!), and then we can recurse, because the new box has smaller $a+b$.

The partition either doesn't use the last column, or it uses a full row

This is the big idea. The rest is details.

Break apart the set of partitions in the sum $S_{a,b}$ by parameter $j$, the number of $k_i$ strictly less than $b$. Clearly $0\leq j\leq a$ Then $$ S_{a,b} = \sum_{j=0}^a S_{j,b-1} = \sum_{j=0}^a S_{b-1,j} = \sum_{i=0}^{\lfloor a/2\rfloor} S_{b-1,2i},$$ where the last equality holds because $b-1$ is odd, so the odd $j$ terms contribute zero to the sum; so we can rewrite the sum in terms of $i=j/2$. And in so doing, after applying the induction hypothesis (since clearly $(b-1)+2i<b+a$) we have paved the way for the triumphant return of the hero: $$ S_{a,b} = \sum_{i=0}^{\lfloor a/2\rfloor} \binom{\lfloor\frac{b-1}{2}\rfloor + \lfloor\frac{2i}{2}\rfloor}{\lfloor\frac{b-1}{2}\rfloor} = \sum_{i=0}^{\lfloor a/2\rfloor} \binom{\frac{b}{2}-1+ i}{\frac{b}{2}-1} = \binom{\frac{b}{2}+\lfloor \frac{a}{2}\rfloor}{\frac{b}{2}}.$$

Yes, it's Chinese hockey sticks all the way down.

Briefly, the plan for the even-even case is to reduce to the even-odd case as quickly as possible. Therefore, instead of breaking the sum apart into lots of pieces depending on how many full rows it uses (or doesn't), we break it into two pieces depending only on whether it uses any full rows: $S_{a,b}= S_{a,b-1}+(-1)^bS_{a-1,b}$. Again $b$ is even, so Pascal's identity $\binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}$ finishes the job.


X. Footnotes

1 By the way, this is the step where we can handle $>$ versus of $\geq$: if the $n_i$ are related with $>$, simply take away an additional $i$ from the new variables $k_i=n_{i+1}-n_1-i$, and then the $k_i$ are still related by $\geq$ and so we can use an $S_{a,b}$ again. It will have a smaller second index than $N-n_1$, though, which is what is responsible for the leading zeros in BillyJoe's data.

2 But one is more annoying than the others, as you might guess from the answer. To handle the $m$ odd, $N$ even case, we'll need a "second order" Chu's Theorem:

Corollary. Let $A$ and $B$ be nonnegative integers. Then $$ \sum_{k=0}^A (A-k)\binom{B+k}{B} = \binom{A+B+1}{B+2}.$$

To prove this, draw a picture of the coefficients $(A-k)$ in the appropriate places in Pascal's triangle: it's a bunch of hockey sticks nested so that applying Chu gives another hockey stick, and so we can apply Chu again.

3 Technically you need to worry about partitions happen to be their own "other half". But we're safe because we only use the involution when the box length and width are both odd, in which case this clearly can't happen because the two partitions have different sizes.

4 I'll note here that this is not strictly necessary; it is possible (and perhaps instructive) to unwind the recursion to get a "full" involution. It will still be essentially piecemeal ("Try this, and if that doesn't work, try this, and if that doesn't work...") but the things that don't work at the end of the line are at least clearly counted by the relevant binomial.

5 I'm sorry about this, but this is the price we have to pay for using pictorial shorthands. The alternative is simply defining base cases like $a=b=0$ by fiat, and then having to constantly worry about them at each future step. It's much better to simply count these degenerate objects. As some consolation, recall where this sum actually gets used in your problem: the $S_{a,b}$ is not actually counting the $n_i$, but rather "what's left" of the $n_i$ after removing $n_1$. The zero-tuple corresponds to $m=2$ and the tuple of zeros corresponds to $n_1=N$; you can check for yourself that our conventions really do capture that "what's left".

$\endgroup$
5
  • $\begingroup$ Well... thank you! Though I must ask how you've justified factoring the sum in your first step in $ \mathbf{3.} $ i.e. how have you determined that the sum is divisible by $\sum_{n_1=1}^N n_1 (-1)^{n_1} = \lfloor {\frac{N+1}{2}}\rfloor (-1)^{n_1}$ P.S. I was trying to fix my MathJax, so I deleted my comment hoping that you wouldn't be able to see it before I fixed it. I did not anticipate that you'd be so quick to reply $\endgroup$
    – mavfs
    Sep 8, 2023 at 7:12
  • $\begingroup$ Ah, nothing is dividing anything. I added some parentheses that hopefully clarify my meaning? I'm just doing the $n_1$-summation separately instead of lumping it together with the sums-over-other-variables. $\endgroup$ Sep 8, 2023 at 7:16
  • 1
    $\begingroup$ The effect is still the same. There is no $n_1$ in the inner sum, so the outer sum is still effectively multiplying it. $\endgroup$
    – mavfs
    Sep 8, 2023 at 7:25
  • $\begingroup$ Oof, I botched those couple lines pretty badly when I was copying my notes. It should be correct now. $\endgroup$ Sep 8, 2023 at 7:25
  • 1
    $\begingroup$ Alas there is one more correction to my MathJax, rhs should be $\lfloor {\frac{N+1}{2}}\rfloor (-1)^{N}$ $\endgroup$
    – mavfs
    Sep 8, 2023 at 7:30
1
$\begingroup$

This is only a long comment.

The results here are for indexes $n_k \ge n_{k-1}$.

Here below your formula computed for $m=2,\ldots,16$ (the rows) and $n_m=1,\ldots,16$ (the columns):

1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8
-1,2,-4,6,-9,12,-16,20,-25,30,-36,42,-49,56,-64,72
1,1,3,3,6,6,10,10,15,15,21,21,28,28,36,36
-1,2,-5,8,-14,20,-30,40,-55,70,-91,112,-140,168,-204,240
1,1,4,4,10,10,20,20,35,35,56,56,84,84,120,120
-1,2,-6,10,-20,30,-50,70,-105,140,-196,252,-336,420,-540,660
1,1,5,5,15,15,35,35,70,70,126,126,210,210,330,330
-1,2,-7,12,-27,42,-77,112,-182,252,-378,504,-714,924,-1254,1584
1,1,6,6,21,21,56,56,126,126,252,252,462,462,792,792
-1,2,-8,14,-35,56,-112,168,-294,420,-672,924,-1386,1848,-2640,3432
1,1,7,7,28,28,84,84,210,210,462,462,924,924,1716,1716
-1,2,-9,16,-44,72,-156,240,-450,660,-1122,1584,-2508,3432,-5148,6864
1,1,8,8,36,36,120,120,330,330,792,792,1716,1716,3432,3432
-1,2,-10,18,-54,90,-210,330,-660,990,-1782,2574,-4290,6006,-9438,12870
1,1,9,9,45,45,165,165,495,495,1287,1287,3003,3003,6435,6435
-1,2,-11,20,-65,110,-275,440,-935,1430,-2717,4004,-7007,10010,-16445,22880

Apparently for $m$ even it is:

$$\binom{\lfloor\frac{n_m+1}{2}\rfloor+\frac{m}{2}-1}{\frac{m}{2}}$$

$m$ odd seems more complicated, however you can search OEIS to try to deduce a formula.

Of course, after that we will need proofs too.

Good luck!

EDIT

In case of indexes strictly decreasing ($n_k \gt n_{k-1}$) the results are basically the same, just with some shifts and sign changes:

0,-1,-1,-2,-2,-3,-3,-4,-4,-5,-5,-6,-6,-7,-7,-8,-8,-9,-9,-10,-10,-11,-11,-12,-12,-13,-13,-14,-14,-15,-15,-16
0,0,1,-2,4,-6,9,-12,16,-20,25,-30,36,-42,49,-56,64,-72,81,-90,100,-110,121,-132,144,-156,169,-182,196,-210,225,-240
0,0,0,1,1,3,3,6,6,10,10,15,15,21,21,28,28,36,36,45,45,55,55,66,66,78,78,91,91,105,105,120
0,0,0,0,-1,2,-5,8,-14,20,-30,40,-55,70,-91,112,-140,168,-204,240,-285,330,-385,440,-506,572,-650,728,-819,910,-1015,1120
0,0,0,0,0,-1,-1,-4,-4,-10,-10,-20,-20,-35,-35,-56,-56,-84,-84,-120,-120,-165,-165,-220,-220,-286,-286,-364,-364,-455,-455,-560
0,0,0,0,0,0,1,-2,6,-10,20,-30,50,-70,105,-140,196,-252,336,-420,540,-660,825,-990,1210,-1430,1716,-2002,2366,-2730,3185,-3640
0,0,0,0,0,0,0,1,1,5,5,15,15,35,35,70,70,126,126,210,210,330,330,495,495,715,715,1001,1001,1365,1365,1820
0,0,0,0,0,0,0,0,-1,2,-7,12,-27,42,-77,112,-182,252,-378,504,-714,924,-1254,1584,-2079,2574,-3289,4004,-5005,6006,-7371,8736
0,0,0,0,0,0,0,0,0,-1,-1,-6,-6,-21,-21,-56,-56,-126,-126,-252,-252,-462,-462,-792,-792,-1287,-1287,-2002,-2002,-3003,-3003,-4368
0,0,0,0,0,0,0,0,0,0,1,-2,8,-14,35,-56,112,-168,294,-420,672,-924,1386,-1848,2640,-3432,4719,-6006,8008,-10010,13013,-16016
0,0,0,0,0,0,0,0,0,0,0,1,1,7,7,28,28,84,84,210,210,462,462,924,924,1716,1716,3003,3003,5005,5005,8008
0,0,0,0,0,0,0,0,0,0,0,0,-1,2,-9,16,-44,72,-156,240,-450,660,-1122,1584,-2508,3432,-5148,6864,-9867,12870,-17875,22880
0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-8,-8,-36,-36,-120,-120,-330,-330,-792,-792,-1716,-1716,-3432,-3432,-6435,-6435,-11440
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-2,10,-18,54,-90,210,-330,660,-990,1782,-2574,4290,-6006,9438,-12870,19305,-25740
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,9,9,45,45,165,165,495,495,1287,1287,3003,3003,6435,6435,12870
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,2,-11,20,-65,110,-275,440,-935,1430,-2717,4004,-7007,10010,-16445,22880
$\endgroup$
3
  • $\begingroup$ Oh dear, that's far more effort than I deserve, thank you! Though I believe the first sequence should be $\pm 1, \mp 1, \pm 2, \mp 2, \pm 3, \mp 3, \pm 4, \mp 4, \dots $ I am not sure how that affects the final result $\endgroup$
    – mavfs
    Sep 5, 2023 at 9:09
  • $\begingroup$ Point of order: your $m$ appears is the number of variables being summed over, is that true? In the OP that number is actually $m-1$ (actively restraining myself from continuing the notation rant). In particular, the binomial formula holds for even $m$. $\endgroup$ Sep 6, 2023 at 16:00
  • $\begingroup$ @EricNathanStucky yes, I think you are right. I have edited and hopefully fixed the comment. $\endgroup$ Sep 6, 2023 at 16:54

You must log in to answer this question.

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