0
$\begingroup$

Hello math stackexchange! I'm new here so please correct any formatting mistakes I make / I'm happy to provide more info if needed.

I have a summation of the form $\sum_{i=1}^{n} \sum_{j=1}^{i} (i+j)$, and I'm not too sure how to go about solving this (and by solve, I mean rewrite it into a formula) . So far I've been able to refactor the inner set of brackets into $\sum_{i=1}^{n} \big( \sum_{j=1}^{i} i + \sum_{j=1}^{i} j \big) $. From here though I'm not too sure what to do as my inner summations depend on two variables (the i and j cannot be factored out)

From here I've tried the following:

  • Rewrite the inner summations to iterate up to n instead of i. However I'm not too sure if this is a valid way of continuing the problem:

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

  • Given that the variable i is in the scope of the inner summations, i can be factored out and then solve the inner summation for j.

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

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

This only gets me up to this point, because I don't know a formula to rewrite a nested summation that iterates up to i.

  • That lead me to combining both those ideas and ending up with this:

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

$= \sum_{i=1}^{n} i \big( \sum_{j=i}^{n} (1) + \sum_{j=i}^{n} (j) \big)$ [2]

$= \sum_{i=1}^{n} i \big(n + \frac{n(n+1)}{2} \big)$ [3]

$=\sum_{i=1}^{n} i n + \sum_{i=1}^{n} i \frac{n(n+1)}{2} $ [4]

$=\frac{1}{2} n^2 (n+1) + \frac{1}{2} \sum_{i=1}^{n} i n(n+1)$ [5]

$=\frac{1}{2} n^2 (n+1) + \frac{1}{2} n^2 (n+1)^2$ [6]

Which simplifies to $\frac{1}{2} n^2 (n+2)(n+1)$. Wolfram's solution was $\frac{1}{2} n(n+1)^2$. I'm wondering which of my assumptions are invalid, or is it an issue to do with my process? Maybe I'm overcomplicating the fact that there is two variables being referenced inside the summations, and this problem could be simplified in a different way?

Cheers

$\endgroup$
0
$\begingroup$

Correction:

$$\sum_{i=1}^{n} \sum_{j=1}^{i} (i+j) = \sum_{i=1}^{n} \left[i\left( \sum_{j=1}^{i} 1\right) + \sum_{j=1}^{i} j \right]$$

To obtain the answer: \begin{align} \sum_{i=1}^{n} \sum_{j=1}^{i} (i+j) &= \sum_{i=1}^{n} \left[i^2 + \frac{i(i+1)}{2} \right] \\ &=\frac32 \sum_{i=1}^n i^2+\frac12 \sum_{i=1}^n i\\ &=\frac32 \frac{n(n+1)(2n+1)}{6} + \frac12\frac{n(n+1)}{2} \\ &= \frac{n(n+1)(2n+2)}4 \\ &= \frac{n(n+1)^2}{2} \end{align}

$\endgroup$
  • $\begingroup$ This makes the most sense, I can see where I was going wrong by refactoring i. Thank you! $\endgroup$ – Netwinder Feb 27 '18 at 20:17
1
$\begingroup$

In the most straightforward way

$$\sum_{i=1}^{n}\sum_{j=1}^{i}(i+j)=\sum_{i=1}^{n}\left(i^2+\sum_{j=1}^{i}j\right)=\sum_{i=1}^{n}\left(i^2+\frac{(i+1)i}{2}\right)$$ can be proved to be equal to $\frac{1}{2}n(n+1)^2$ by induction on $n$. As an alternative, we may notice that $$ \sum_{1\leq j \leq i \leq n}(i+j)=\frac{1}{2}\left(\sum_{1\leq i,j\leq n}(i+j)+\sum_{1\leq i = j\leq n}(i+j)\right)$$ equals $$ \frac{1}{2}\left(n\sum_{1\leq i\leq n}i+n\sum_{1\leq j\leq n}j+\sum_{1\leq k\leq n}2k\right)=\frac{1}{2}\left(2n\frac{n(n+1)}{2}+n(n+1)\right)=\frac{1}{2}n(n+1)^2. $$

$\endgroup$
  • 1
    $\begingroup$ In the second set of summations you give, the base is dependent on two variables based on $1 \leq j \leq i \leq n$ - I haven't seen it done this way but this looks promising. Either way you're able to rewrite the inner summation as $i^2$ and then solve $\sum_{j=1}^{i} j$. I can see where I was going wrong $\endgroup$ – Netwinder Feb 27 '18 at 20:16
1
$\begingroup$

Use the formal identity $$ \sum_{i=1}^n \sum_{j=1}^n (i+j)=2 \sum_{i=1}^n \sum_{j=1}^{i-1} (i+j)+ 2\sum_{i=1}^n i=2\sum_{i=1}^n \sum_{j=1}^{i} (i+j). $$ Then $$ \sum_{i=1}^n \sum_{j=1}^{i} (i+j)=\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n (i+j)=\sum_{i=1}^n \sum_{j=1}^n i=\frac{(n+1)n^2}{2}. $$

$\endgroup$
0
$\begingroup$

The inner sum is

$$i^2+\frac {i (i+1)}{2} =\frac {3}{2}i^2+\frac {1}{2}i $$

the result is $$\frac {3}{2}\sum_{i=1}^ni^2+\frac {1}{2}\sum _{i=1}^ni=$$

$$\frac {3}{2}\frac {n (n+1)(2n+1)}{6}+\frac {1}{2}\frac {n (n+1)}{2} =$$

$$\frac {n (n+1)^2}{2} $$

$\endgroup$
0
$\begingroup$

\begin{align}\sum_{i=1}^n\sum_{j=1}^ii+j&=\sum_{i=1}^n\left(\sum_{j=1}^i i+\sum_{j=1}^ij\right)\\&=\sum_{i=1}^ni^2+\frac{i(i+1)}2\\&=\frac32\sum_{i=1}^ni^2+\frac12\sum_{i=1}^ni\\&=\frac32\cdot\frac{n(n+1)(2n+1)}6+\frac12\cdot\frac{n(n+1)}2\\&=\frac12n(n+1)^2.\end{align}

$\endgroup$
0
$\begingroup$

Your first refactoring seems wrong to me.

The inner sum is,

$$\sum\limits_{j=1}^i i+j = (i+1) + (i+2) + \ldots + (i+i) = i^2 + \frac{i(i+1)}{2}$$

Using the $n$th triangle number. Then we have the following,

$$\sum\limits_{i=1}^ni^2 + \frac{i(i+1)}{2} = \sum\limits_{i=1}^n i^2 + \frac{1}{2}\sum\limits_{i=1}^n i^2 + \frac{1}{2}\sum\limits_{i=1}^ni = \left(\frac{3}{2}\sum\limits_{i=1}^ni^2\right) + \frac{n(n+1)}{4},\\ =\frac{3}{2}\frac{(n(n + 1)(2n + 1))}{6}+\frac{n(n+1)}{4} = \frac{n(n+1)^2}{2}$$

$\endgroup$
0
$\begingroup$

New Solution

This solution reduces the summation to $(n+1)$ times the sum of the first $n$ integers, only by manipulating summation limits and order of summation. This then leads to the closed-form solution with minimal algebraic manipulation.

$$\begin{align} \sum_{i=1}^n\sum_{j=1}^n (i+j) &=\sum_{i=1}^n\sum_{j=1}^i(j+i)\\ &=\sum_{i=1}^n\sum_{j=1}^i j+\sum_{k=1}^n\sum_{j=1}^k k\\ &=\sum_{i=1}^n\sum_{j=1}^i j+\sum_{j=1}^n\sum_{k=j}^n k\\ &=\sum_{i=0}^n\sum_{j=1}^i j+\sum_{j=0}^{n-1}\sum_{k=j+1}^n k\\ &=\sum_{i=0}^n\sum_{j=1}^i j+\sum_{j=0}^{n}\sum_{k=j+1}^n k\\ &\color{lightgrey}{=\sum_{i=0}^n\sum_{j=1}^i j+\sum_{i=0}^{n}\sum_{k=i+1}^n k}\\ &\color{lightgrey}{=\sum_{i=0}^n\left[\sum_{j=1}^i j+\sum_{k=i+1}^n k\right]}\\ &=\sum_{i=0}^n\left[\sum_{j=1}^i j+\sum_{j=i+1}^n j\right]\\ &=\sum_{i=0}^n\sum_{j=1}^n j\\ &=(n+1)\cdot \frac {n(n+1)}2\\ &=\color{red}{\frac {n(n+1)^2}2}\end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.