Changing finite double summation $\sum_{i=1}^n\sum_{k=1}^i f(k) = \sum_{k=1}^n\sum_{i=1}^k f(n+1-k).$

Question

I have a double sum of the form $$ \sum_{i=1}^n\sum_{k=1}^i f(k) $$ and I want to change the order of the sums. From drawing some pictures I am fairly confident that $$ \sum_{i=1}^n\sum_{k=1}^i f(k) = \sum_{k=1}^n\sum_{i=1}^k f(n+1-k). $$

Again, writing out the terms, this seems pretty clear, but I am looking for a more precise proof. I tried a change of variable, but I don't seem to be able to find something that works. So my question is: How can I rigorously prove the above formula?

EDIT: Again, I can see that the formula is true by simply writing out the terms and collecting them again. So I can see that I will $n$ terms of $f(1)$ and $n-1$ terms of $f(2)$.

What I am specifically looking for is a rigorous proof that the formula holds. Is there, for example, some way to do this by a change of variables? Or some way of algebraically manipulating the sum?

Answer 1

A derivation can go as follows:

We obtain \begin{align*} \color{blue}{\sum_{i=1}^n\sum_{k=1}^if(k)} &=\sum_{1\leq k\leq i\leq n}f(k)\tag{1}\\ &=\sum_{k=1}^n\sum_{i=k}^nf(k)\tag{2}\\ &=\sum_{k=1}^n\sum_{i=n-k+1}^nf(n-k+1)\tag{3}\\ &\,\,\color{blue}{=\sum_{k=1}^n\sum_{i=1}^kf(n-k+1)}\tag{4}\\ &=\sum_{k=1}^nf(n-k+1)\sum_{i=1}^k1\tag{5}\\ &\,\,\color{blue}{=\sum_{k=1}^nkf(n-k+1)}\tag{6} \end{align*} where (4) is the representation claimed by the OP followed by some further simplifications.

Comment:

• In (1) we rewrite the index range to see the relationship between $i$ and $k$ more conveniently.

• In (2) we change the order of summation by exchanging the sums.

• In (3) we reverse the order of summation of the outer sum by setting the index $k\to n-k+1$.

• In (4) we shift the index of the inner sum $i\to i-(n-k)$ to start with $i=1$.

• In (5) we factor out $f(n-k+1)$ which does not depend on the index $i$.

• In (6) we replace the inner sum by the factor $k$.

Answer 2

It's even better than that -- you can write it as a single sum $$\sum_{k=1}^n (n-k+1)f(k)$$ which is the same thing as $$\sum_{k=1}^n kf(n-k+1)$$ by reindexing to sum in reverse order (use whichever form you prefer). That's because the term $f(j)$ appears in exactly your inner sums for which $i$ is at least $j$ -- that is, for the values of $i$ with $j\leq i \leq n$; there are $n-j+1$ indices in the range $j,j+1,j+2,\ldots,n$.

---

Addendum: To see that the double sum reduces as indicated, write out the inner sums on separate rows: $$f(1)+\tag{row $1$}$$ $$f(1)+f(2)+\tag{row $2$}$$ $$f(1)+f(2)+f(3)+\tag{row $3$}$$ $$\cdots +$$ $$f(1)+f(2)+f(3)+\cdots+f(n)\tag{row $n$}$$ Note $f(1)$ appears in rows $1$ to $n$, $f(2)$ appears in rows $2$ to $n$; generally $f(j)$ appears in rows $j$ to $n$.

This means that there are $n-j+1$ copies of $f(j)$ in the sum. For example, $n-1+1=n$ copies of $f(1)$, $n-2+1=n-1$ copies of $f(2)$, $n-3+1=n-2$ copies of $f(3)$, etc.

So the whole sum is $nf(1)$ plus $(n-1)f(2)$ plus $(n-2)f(3)$ etc.; the generic term here is $(n-j+1)f(j)$, thus the first single sum.

To reindex, just replace $k$ in the first single summand with $n-k+1$. This simply reverses the order of summation.

Note: If an index $m$ runs from $a$ to $b$, then the index $m'\equiv b-m+a$ runs from $b$ to $a$. Since you are summing the same terms in reverse order, it should be clear that $$\sum_{m=a}^b t(m) =\sum_{m=a}^b t(b-m+a)$$

Answer 3

Given that $$\sum_{i=1}^{n} \sum_{k=1}^{i} f(k) = \sum_{k=1}^{n} \sum_{i=1}^{k} f(n-k+1)$$ then one may use the generating function method to show equality. This is seen by the following. \begin{align} \sum_{n=1}^{\infty} \sum_{i=1}^{n} \sum_{k=1}^{i} f(k) \, t^{n} &= \sum_{n,i=1}^{\infty} \sum_{k=1}^{i} f(k) \, t^{n+k} \\ &= \sum_{n,i,k=1}^{\infty} f(k) \, t^{n+k+i} \\ &= \frac{t^2}{(1-t)^{2}} \, \sum_{k=1}^{\infty} f(k) \, t^{k} \end{align} For the right hand side it is easier to consider it in the form $$\sum_{k=1}^{n} \sum_{i=1}^{k} f(n-k+1) = \sum_{k=1}^{n} k \, f(n-k+1) = \sum_{k=1}^{n} (n-k+1) \, f(k)$$ and then take the generating function. When completed it will be shown that the left and right side generating functions are equal.

Answer 4

If $s(n) =\sum_{i=1}^n\sum_{k=1}^i f(k) $, then this has in the inner sum all $k$ with $1 \le k \le i \le n$.

This can be rearranged as $s(n) =\sum_{k=1}^n\sum_{i=k}^n f(k) =\sum_{k=1}^n(n-k+1) f(k) $, since the new inner sum does not depend on $i$.