1

I am trying to self teach myself discrete maths and I am unable to solve this double summation for a closed form. Would really appreciate if someone help me understand the next step.

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

What I have tried:

I have separated the two $i$ and $j$ as $\sum\sum i + \sum\sum j$.

Since $\sum_{i=1}^ni=\frac12n(n+1)$, I have replaced $\sum j$ with this closed form formula

So I am left with $$\sum \sum i + \sum\frac12 n(n + 1)$$

Now I cant understand how to open the left summation of $i$ and how to further open the right summation.

EDIT: Bsed on @DavidC.Ullrich’s suggestion, I got $\Sigma ni$ on the left, so $n\cdot\dfrac{n(n+1)}{2}$ for the left side, but still can’t open the right hand summation any further.

insipidintegrator
  • 6,642
Furrukh Jamal
  • 49
  • 1
    Welcome to Mathematics Stack Exchange! As this site is meant to be a useful repository rather than a Do My Homework forum, it's common courtesy to show what you've already tried, and really narrow down what you're struggling with. Most people here are glad to help once you've adequately motivated the problem. Quick Guide to attracting answers and preventing your question from being deleted. Good luck! – InanimateBeing Aug 21 '22 at 18:21
  • 2
    Try evaluating the sum for small values of $n$ and see if you notice a pattern. You may also find it helpful to write the terms of the sum out on a grid. As a final hint, you may find it helpful to separate out the $i$ terms and the $j$ terms. – Qiaochu Yuan Aug 21 '22 at 18:27
  • 2
    Please don't use pictures, use MathJax. Here is a tutorial. – Dietrich Burde Aug 21 '22 at 18:28
  • Hnit (can be applied to both pieces): $\sum_{j=1}^32=2+2+2=6$. – David C. Ullrich Aug 21 '22 at 18:45
  • based on @David C. Ullrich suggestion I got ∑ ni on the left, took n outside and I am left with n∑ i, so n * n(n+1)/2 for the left side, but still cant open the right hand summation any further – Furrukh Jamal Aug 21 '22 at 19:07
  • for the other part don't do what you did - instead start with $\sum_i\sum_j=\sum_j\sum_i$. – David C. Ullrich Aug 21 '22 at 19:50

3 Answers3

2

Hint

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

Claude Leibovici
  • 260,315
1

Let’s evaluate the inside summation first (In my opinion, the summations can be interchanged by symmetry).

$$\sum_{j=1}^n(i+j)= \sum_{j=1}^ni+ \sum_{j=1}^nj$$$$=i \sum_{j=1}^n1+\frac{n(n+1)}{2}=ni+ \frac{n(n+1)}{2} $$ Next, we have $$\sum_{i=1}^n \left(ni +n\frac{n+1}{2}\right)$$$$= n\sum_{i=1}^ni+ \sum_{i=1}^n\frac{n(n+1)}{2}=n\cdot\frac{n(n+1)}{2}+ n\cdot\frac{n(n+1)}{2}$$$$=n^2(n+1).$$

insipidintegrator
  • 6,642
0

I know you're trying to learn how to manipulate sums directly, but sometimes you can see a cool pattern* and short-circuit the calculation.

Intuition: in $S=\sum_{i=1}^n\sum_{j=1}^n(i+j)$ there are $n^2$ terms; the minimum is $2$; the maximum is $2n$. So the average is $\frac12 (2+2n)=n+1$. And so $S=n^2(n+1)$.

Formalisation: proceed the same way as in the proof of the formula for the sum of an arithmetic progression, by adding another copy "in reverse".

$$\begin{align} 2S&=\sum_{i=1}^n\sum_{j=1}^n(i+j)+\sum_{i=1}^n\sum_{j=1}^n((n+1-i)+(n+1-j))\\ &=\sum_{i=1}^n\sum_{j=1}^n((n+1)+(n+1))\\ &=2n^2(n+1). \end{align} $$

*In this case the pattern is that the terms $(i,j,i+j)\in \mathbb{Z}^3$ lie on a $2$-dimensional (flat) plane. This linearity makes the intuition of averages work.

Benjamin Wang
  • 3,920