2

The sum of all absolute values of the differences of the numbers $1,2,3,\ldots, n$, taken two at a time, i.e. $$\sum_{j\le i\le n}\left|i-j\right|$$ equals:

(A) $\binom{n-1}3$ (B) $\binom n 3$ (C) $\binom{n+1}3$ (D)$\binom{n+2}3$

Please give me hints on starting off with this problem. Kindly don't put the whole answer.

(Original scan of problem)

MJD
  • 65,394
  • 39
  • 298
  • 580
Rajath Radhakrishnan
  • 1,715
  • 3
    Why not work it out for some small values of $n$ to see which answer fits, then try to prove it? – Gerry Myerson Aug 26 '13 at 13:30
  • @Gerry's suggestion lets us immediately rule out (A), (B) by considering $n=2$. – vadim123 Aug 26 '13 at 13:34
  • 1
    Of course I could do it because it is a multiple choice type question. But, I want to develop my problem solving ability even without the options. So, I want a hint on starting off the solution for this even if the options are not given. – Rajath Radhakrishnan Aug 26 '13 at 13:36
  • In that case then try doing it like this. If you fix $j$ to be $1$ and let $i$ range from $1$ up to $n$, you get the numbers, $1,2,3,...,n-1$. Now let $j=2$ and let $i$ range from $2$ to $n$, you get the numbers $1,2,3,...,n-2$, and so on. You end up getting: $(1+...+(n-1))+(1+...+(n-2))+...+(1+2)+(1)$. – Daniel Montealegre Aug 26 '13 at 13:39
  • 2
    $$\begin{matrix}0&1&2&3&\dotsb\1&0&1&2&\dotsb\2&1&0&1&\dotsb\3&2&1&0&\dotsb\ \vdots&\vdots&\vdots&\vdots&\ddots\end{matrix}$$ – Daniel Fischer Aug 26 '13 at 13:41
  • If you are going to prescribe $j\leq i$ why use $|i-j|$? Isn't $|i-j|=i-j$ in that instance? – Thomas Andrews Aug 26 '13 at 13:58
  • yeah that's right....... – Rajath Radhakrishnan Aug 26 '13 at 14:04
  • If you want the differences taken two at a time, both $i$ and $j$ have to go from $1$ to $n$. That is what I have done in my solution. – marty cohen Aug 26 '13 at 17:14
  • My suggestion that you work it out for some small values of $n$ applies even if it's not multiple choice. You do examples, you make a guess as to the answer, then you try to prove it. If you fail, then you ask for help. – Gerry Myerson Aug 26 '13 at 23:08

5 Answers5

2

The sum of all absolute values of the differences of the numbers 1,2,3,…,n, taken two at a time is

$\begin{align} S(n) &=\sum_{i=1}^n\sum_{j=1}^{n}|i-j|\\ &=\sum_{i=1}^n\sum_{j=1}^{i-1}|i-j| +\sum_{i=1}^n\sum_{j=i+1}^{n}|i-j|\\ &=\sum_{i=1}^n\sum_{j=1}^{i-1}(i-j) +\sum_{i=1}^n\sum_{j=i+1}^{n}(j-i)\\ &=\sum_{i=1}^n\sum_{j=1}^{i-1}j +\sum_{i=1}^n\sum_{j=1}^{n-i}j\\ &=\sum_{i=1}^n\frac{i(i-1)}{2} +\sum_{i=1}^n\frac{(n-i)(n-i+1)}{2}\\ &=\sum_{i=1}^n\left(\frac{i(i-1)}{2} +\frac{(n-i)(n-i+1)}{2}\right)\\ &=\sum_{i=1}^n\left(\frac{i(i-1)+(n-i)(n-i+1)}{2}\right)\\ &=\sum_{i=1}^n\left(\frac{i^2-i+(n-i)^2+(n-i)}{2}\right)\\ &=\frac12\sum_{i=1}^n\left(i^2-i+n^2-2ni+i^2+n-i\right)\\ &=\frac{n(n^2+n)}{2}+\sum_{i=1}^n\left(i^2-i-2ni\right)\\ &=\frac{n(n^2+n)}{2}+\frac{n(n+1)(2n+1)}{6}-(2n+1)\frac{n(n+1)}{2}\\ &=\frac{n(n+1)}{2}\left(n+\frac{(2n+1)}{3}-(2n+1)\right)\\ &=\frac{n(n+1)}{6}\left(3n+(2n+1)-3(2n+1)\right)\\ &=\frac{n(n+1)}{6}\left(3n-(2n+1)\right)\\ &=\frac{n(n+1)}{6}\left(n-1\right)\\ &=\frac{(n-1)n(n+1)}{6}\\ &=\binom{n+1}{3}\\ \end{align} $

(Whew!)

There are probably simpler ways, but this is my way.

marty cohen
  • 107,799
1

Let $f(n)=\sum_{1\le j\le i\le n}|i-j|$. Then $f(n+1)=f(n)+\sum_{1\le j\le n}|n-j|=f(n)+\sum_{0\le j\le n-1}j$. You may know a formula for the latter sum and then make a suitable ansatz that can be shown by induction.

Hagen von Eitzen
  • 374,180
1

First af all, the modulus is unnecessary as $i \ge j.$ Next, the sum $$ \sum_{j\le i\le n}(i-j)= \sum_{j=1}^{j=n}\sum_{i=j }^{i=n} (i-j).$$ The inner sum $$\sum_{i=j }^{i=n} (i-j)=\frac 1 2 (n+1)^2-\frac 1 2 n-\frac 1 2-j(n+1)+\frac 1 2 j^2+\frac 1 2 j .$$ Therefore, the sum under consideration equals $$\sum_{j=1}^{j=n}\left(\frac 1 2 (n+1)^2-\frac 1 2 n-\frac 1 2-j(n+1)+\frac 1 2 j^2+\frac 1 2 j \right)= \frac 1 6 (n^3-n) =C_{n+1}^{3}. $$

user64494
  • 5,811
1

After having seen @marty cohen 's answer I'd argue as follows:

The sum $S$ in question is equal to the number of unit intervals of the form $$[l,l+1]\qquad (0\leq i-1<l<j\leq n)\ ,$$ counted with multiplicity. Each such interval determines a three-element subset of $\{0,1,2,\ldots,n\}$ of the form $\{i-1,l,j\}$ with $i-1<l<j\ $, and conversely: For any three-element subset $\{i-1,l,j\}$ of $\{0,1,2,\ldots,n\}$ we obtain an interval $[l,l+1]\subset[i,j]$ that is counted in the sum $S$ as one of the $j-i$ unit segments between $i$ and $j$.

It follows that $$S={n+1\choose 3}\ .$$

Christian Blatter
  • 226,825
1

If you fix $j=1$, then let $i$ range you get: $1+2+..+(n-1)$.

If you fix $j=2$, then let $i$ range you get: $1+2+..+(n-2)$.

...

If you fix $j=n-1$, then let $i$ range you get: $1$.

If you put them all together you get a total of $(n-1)$ number of $1$'s, $(n-2)$ number of $2$'s,..., $1$ number of $(n-1)$'s. Thus your sum equals: $$\sum_{k=1}^{n-1}k\cdot (n-k)$$Which equals: $n\sum_{k=1}^{n-1} k-\sum_{k=1}^{n-1}k^2$, and using the well know formulas (and some algebra) you get $n^3/6-n/6$, which is equal to $\binom{n+1}{3}$

Daniel Montealegre
  • 6,783