2

I am looking at a summation that resembles the summation below: $$\sum_{i=1}^n\sum_{\matrix{j=1\\j \not= i}}^n 1$$ What is the best way to think about this summation and thus get the result? Can the sum be broken apart into a more intuitive form?

Damien
  • 75
  • Is $\left(\sum_{i=1}^n\sum{j=1}^n f(i,j)\right)-\sum_{k=1}^nf(k,k)$ more intuitive? (I think this is really a question that doesn't respond well to generalization; how you rearrange a sum depends on what you're summing) – Milo Brandt Apr 08 '15 at 21:55
  • For completeness you might want to specify $j=1$ to $n$, in addition to $j\neq i$ (if that is indeed what it is supposed to mean). – Hypergeometricx Apr 09 '15 at 16:26
  • As an extension, an interesting question would be to evaluate $$\sum_{i=1}^{n}\sum_{\matrix{j=1\ j\neq i}}^{n}j$$ – Hypergeometricx Apr 09 '15 at 16:46
  • An easy way, I think: take a $n\times n$ matrix $A$ with all entries equal to $1$, except the diagonal which is 0. Then sum all terms: you may imagine first that even the diagonal has ones, hence sum $n^2$, and you remove the diaginal which sums to $n$, hence result is $n^2-n$. – Jean-Claude Arbaut Apr 09 '15 at 22:24

3 Answers3

3

I would rewrite it this way.

$\sum_{i=1}^{n}\bigg[\underbrace{\sum_{j=1}^{i-1}1}_{(i-1)\text{-terms}}+\underbrace{\sum_{j=i+1}^{n}1}_{(n-i)\text{-terms}}\bigg]=\sum_{i=1}^{n}[(i-1)+(n-i)]=\sum_{i=1}^{n}(n-1)$ $\phantom{\sum_{i=1}^{n}\bigg[\underbrace{\sum_{j=1}^{i-1}1}_{(i-1)\text{-terms}}+\underbrace{\sum_{j=i+1}^{n}1}_{(n-i)\text{-terms}}\bigg]}=(n-1)\underbrace{\sum_{i=1}^{n}1}_{n\text{-terms}}=(n-1)n$.

bkarpuz
  • 833
3

I would add and remove the deleted term from the inside summation:

$\begin{array}\\ \sum_{i=1}^n\sum_{j \not= i} 1 &=\sum_{i=1}^n((\sum_{j=1}^n 1)- 1)\\ &=\sum_{i=1}^n((n)- 1)\\ &=n(n-1) \end{array} $

Fortunately, my answer agrees with that if bkarpuz.

More generally, if $F = \sum_{j=1}^n f(j)$,

$\begin{array}\\ \sum_{i=1}^n\sum_{j \not= i} f(j) &=\sum_{i=1}^n((\sum_{j=1}^n f(j))- f(i))\\ &=\sum_{i=1}^n\sum_{j=1}^n f(j)-\sum_{i=1}^n f(i)\\ &=\sum_{i=1}^n F-F\\ &=nF-F\\ &=(n-1)F\\ \end{array} $

Even more generally, if $F(i) = \sum_{j=1}^n f(i, j)$, $G = \sum_{i=1}^n F(i)$, and $D = \sum_{i=1}^n f(i, i)$ ,

$\begin{array}\\ \sum_{i=1}^n\sum_{j \not= i} f(i,j) &=\sum_{i=1}^n((\sum_{j=1}^n f(i,j))- f(i,i))\\ &=\sum_{i=1}^n\sum_{j=1}^n f(i,j)-\sum_{i=1}^n f(i,i)\\ &=\sum_{i=1}^n F(i)-D\\ &=G-D\\ \end{array} $

marty cohen
  • 107,799
0

Since the summand is $1$, the summation is just the count of the number of elements to be summed. Hence $$\begin{align} &\overbrace{\sum_{1\leqslant i\leqslant n}}^n\; \overbrace{\sum_{\matrix{1\leqslant j\leqslant n,\\ j\neq i}}1}^{n-1}\\ &=n(n-1)\qquad\blacksquare \end{align}$$

Hypergeometricx
  • 22,657