Rigorously proving that $\sum_{k=1}^{n}\sum_{j=1}^{k}d_j$ is equal to $\sum_{k=0}^{n-1}(n-k)d_{k+1}$

Question

The way that I originally arrived upon $\sum_{k=0}^{n-1}(n-k)d_{k+1}$ is by seeing that $\sum_{k=1}^{n}\sum_{j=1}^{k}d_j$ is similar to a telescoping sum, as when the sums for various values of $k$ are written out a pattern emerges. The following is how I arrived at $\sum_{k=0}^{n-1}(n-k)d_{k+1}$:

Take the second sum $\sum_{j=1}^{k}d_j$ and look at a table of the expanded sum for different values of from $1$ to $n$ $$ \begin{array}{c|lcr} k & \sum_{j=1}^{k}d_j\\ \hline 1 & d_1 \\ 2 & d_1+d_2 \\ 3 & d_1+d_2+d_3 \\ ... & ... \\ n & d_1+d_2+d_3\ +\ ... \ +\ d_n \\ \end{array} $$ Notice that $d_1$ appears for every value of $k$ for a total of $n$ times, $d_2$ appears for every value of $k$ after $k=1$ for a total of $n-1$ times, and so on and so forth for every $d_k$ appearing $(n-k+1)$ times ending with $d_n$ appearing once. Therefore the two sums can be written as one which represents how often each $d_k$ appears, specifically $\sum_{k=1}^{n}(n-k+1)d_k$, or in a way that I find cleaner $\sum_{k=0}^{n-1}(n-k)d_{k+1}$.

My current problem with my argument is that I feel the introduction of the table and the argument about occurrences isn't very rigorous, is the a more rigorous way I could make my argument? Thanks!

Answer 1

I don't have a problem with your argument. But if you're not happy with it you could always use induction. The main step would be $$\eqalign{ \sum_{k=1}^{n+1}\sum_{j=1}^k d_j &=\Bigl(\sum_{k=1}^n\sum_{j=1}^k d_j\Bigr) +\Bigl(\sum_{j=1}^{n+1} d_j\Bigr)\cr &=\Bigl(\sum_{k=0}^{n-1}(n-k)d_{k+1}\Bigr) +\Bigl(\sum_{k=0}^n d_{k+1}\Bigr)\cr &=\Bigl(\sum_{k=0}^{n-1}(n-k)d_{k+1}+d_{k+1}\Bigr)+d_{n+1}\cr &=\sum_{k=0}^n (n+1-k)d_{k+1}\cr}$$ and I'll leave the formal details to you.

Answer 2

We can transform the double sum of the left-hand side to obtain the right-hand side as follows \begin{align*} \sum_{k=1}^n\sum_{j=1}^kd_j&=\sum_{\color{blue}{1\leq j\leq k\leq n}}d_j=\sum_{j=1}^n\sum_{k=j}^nd_j\tag{1}\\ &=\sum_{j=1}^nd_j\sum_{k=j}^n1\tag{2}\\ &=\sum_{j=1}^nd_j(n-j+1)\tag{3}\\ &=\sum_{j=0}^{n-1}d_{j+1}(n-j)\tag{4} \end{align*} and the claim follows by replacing in (4) the index $j$ with $k$.

Comment:

• In (1) we write the index region in a convenient form to better see what's going on. Then we write the double sum by changing the order of summation.

• In (2) we factor out $d_j$ from the inner sum.

• In (3) we simplify the inner sum.

• In (4) we shift the index by one to start with $j=0$.