1

I'd like to see a proof of this identity I discovered:

$$ \sum_{i=1}^{n}\sum_{j=1}^{i}a_j = \sum_{i=1}^{n}a_i(n-i+1) $$

Probably there's something I forgot because I couldn't manage it.

[edit]Possibly with just identities, not examples please!

[edit2]No induction procedure, either.

user2488812
  • 23
  • 1
  • 4

4 Answers4

3

$$\sum_{i=1}^n\sum_{j=1}^nx_{ij}=\sum_{i=1}^n\sum_{j=1}^nx_{ji}\;;\tag{1}$$ because each summand $x_{rs}$ on the RHS can be found on the LHS and vice versa and summation is commutativ. Therefore this sum is often written as

$$ \sum_{1\le i,j\le n}x_{ij}$$

We set

$$ x_{rs}=a_s,s \le r \;;\tag{2}$$ $$ x_{rs}=0, s \gt r \;;\tag{3}$$

Expanding the LHS from (1) and substituting (2) and (3) we get

$$\sum_{i=1}^n\sum_{j=1}^nx_{ij}=\sum_{i=1}^n\sum_{j=1}^{i}x_{ij}+\sum_{i=1}^n\sum_{j=i+1}^nx_{ij}=\sum_{i=1}^n\sum_{j=1}^{i}a_j+\sum_{i=1}^n\sum_{j=i+1}^n0=\sum_{i=1}^n\sum_{j=1}^ia_j$$

This is the LHS of your idendity.

Expanding the RHS of (1) and substituting (2) and (3) gives

$$\sum_{i=1}^n\sum_{j=1}^nx_{ji}=\sum_{i=1}^n\sum_{j=1}^{i-1}x_{ji}+\sum_{i=1}^n\sum_{j=i}^nx_{ji}=\sum_{i=1}^n\sum_{j=1}^{i-1}0+\sum_{i=1}^n\sum_{j=i}^na_i=\sum_{i=1}^na_i(\sum_{j=i}^n1)=\sum_{i=1}^na_i(\sum_{j=1}^n1-\sum_{j=1}^{i-1}1)=\sum_{i=1}^na_i(n-(i-1))$$

This is the RHS of your idendity.

miracle173
  • 11,049
2

Hints:

$$\sum_{i=1}^n\sum_{j=1}^ia_j=\sum_{i=1}^n\left(a_1+a_2+\ldots+a_i\right)=a_1+(a_1+a_2)+\ldots+(a_1+\ldots+a_n)=$$

$$na_1+(n-1)a_2+\ldots +(n-(k-1))a_k+\ldots+a_n\;,\;\text{(observe that}\;n-(n-1)=1)$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Well, that's correct, but I'd like to prove this without any '...' notation, ie not through summation expansions. – user2488812 Aug 14 '13 at 12:17
  • Yeah...too bad you didn't mention that, and I doubt whether any other proof is a simple, elementary and straightforward as this one. – DonAntonio Aug 14 '13 at 12:25
2

You can reverse the order of summation in much the same way that one reverses the order of integration in an iterated integral:

$$\sum_{i=1}^n\sum_{j=1}^ia_j=\sum_{j=1}^n\sum_{i=j}^na_j\;;\tag{1}$$

now just notice that the inner summation on the righthand side of $(1)$ is the sum of $(n-j-1)$ copies of $a_j$.

If you've not seen other examples of reversing the order of summation, the array below may be helpful:

$$\begin{array}{c|cccccc|c} i\backslash j&1&2&3&\dots&n-1&n&\sum_{j=1}^ia_j\\ \hline 1&a_1&&&&&&\sum_{j=1}^1a_j\\ 2&a_1&a_2&&&&&\sum_{j=1}^2a_j\\ 3&a_1&a_2&a_3&&&&\sum_{j=1}^3a_j\\ \vdots&\vdots&\vdots&\vdots&\ddots&&&\vdots\\ n-1&a_1&a_2&a_3&\dots&a_{n-1}&&\sum_{j=1}^{n-1}a_j\\ n&a_1&a_2&a_3&\dots&a_{n-1}&a_n&\sum_{j=1}^ma_j\\ \hline \sum_{i=j}^na_j&\sum_{i=1}^na_1&\sum_{i=2}^na_2&\sum_{i=3}^na_3&\dots&\sum_{i=n-1}^na_{n-1}&\sum_{i=n}^na_n&\text{double sum}\atop(1) \end{array}$$

Brian M. Scott
  • 616,228
  • Ok finally! That summation identity is what I needed: $$\sum_{i=1}^n\sum_{j=1}^ia_j=\sum_{j=1}^n\sum_{i=j}^na_j=\sum_{j=1}^na_j\sum_{i=j}^n1=\sum_{j=1}^na_j(n-j+1);\tag{1}$$ though, is it there a way to prove it with other summation identities? – user2488812 Aug 14 '13 at 12:22
  • @user2488812: For each $\langle i,j\rangle$ such that $1\le j\le i\le n$ let $a_{i,j}=a_j$. Then observe that both double sums are equal to $$\sum{a_{i,j}:1\le j\le i\le n};;$$ they're just adding the terms in a different order. That's what I tried to show in my array: the first double sum first adds up each row and then takes the total of the row sums; the second first adds up each column and then takes the total of the column sums. – Brian M. Scott Aug 14 '13 at 12:27
  • mmm as I thought. Thank you for you response! – user2488812 Aug 14 '13 at 12:31
  • @user2488812: You're welcome! – Brian M. Scott Aug 14 '13 at 12:34
  • I'm really sorry, but I cannot ignore the answer of @miracle173. – user2488812 Aug 14 '13 at 20:49
0

Hint: Try to figure out how many times

  • $a_1$ occurs in LHS
  • $a_n$ occurs in LHS
  • $a_k$, $k \leq n$ occurs in LHS

Guess this will help you out.