1
$\begingroup$

It can be easily shown by step-by-step and rather messy summation over $j$ and then over $i$ that $$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=\tfrac12 (2n+1)n(n+1)$$ Note that RHS is equivalent to $$\displaystyle (2n+1)\sum_{r=1}^n r$$

(1) Is there a clever transform that will simplify the original summation into the summation above without first working out the closed form?

It is interesting to note that RHS is also equivalent to $$3\sum_{r=1}^n r^2$$

(2) Is there also another clever transform to convert the original summation into this summation without first working out the closed form?

$\endgroup$
  • $\begingroup$ The problem is "How can you write the factor $(2n+1)$ without knowing first RHS?" $\endgroup$ – Piquito May 27 '18 at 13:11
  • $\begingroup$ @Piquito Yes that is the question. $\endgroup$ – hypergeometric May 27 '18 at 13:14
  • $\begingroup$ The two answers below make the same mistake I did on more than one occasion: do not read the problem statement well. $\endgroup$ – Piquito May 27 '18 at 13:23
  • $\begingroup$ Looks like the strategy is to split $i+j$ and force "inner" sum to be in the form $\sum_{r=0}^n r$ $\endgroup$ – user160738 May 27 '18 at 13:33
3
$\begingroup$

(1)

$$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=\sum_{j=0}^{n-1}\sum_{i=1}^{n+1}i + \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}j=n\left((n+1)+\sum_{i=1}^n i\right)+(n+1)\left(-n+\sum_{j=1}^n j\right) \\ =(n+(n+1))\sum_{r=1}^n r=(2n+1)\sum_{r=1}^n r$$

(2)

$$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)= \sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ 1 \le i+j \le n \end{array}} \!(i+j) + \!\!\sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ n+1 \le i+j \le 2n \end{array}} \!((i-1)+(j+1)) \\ =\sum_{k=1}^n\sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ i+j=k \end{array}} \!k + \!\sum_{\begin{array} c k=0 \\ (i-1=k) \end{array}}^n\!\!\sum_{\begin{array} c 0 \le j \le n-1, \\ n-k \le j \le 2n-1-k \end{array}} \!\!\!\!k + \!\sum_{\begin{array} c k=1 \\ (j+1=k) \end{array}}^n\!\sum_{\begin{array} c 1 \le i \le n+1, \\ n+2-k \le i \le 2n+1-k \end{array}} \!\!\!\!\!k \\ =\sum_{k=1}^n \,k \!\sum_{\begin{array} c 1 \le i \le k \\ (j=k-i) \end{array}} \!\!1 + \!\sum_{k=1}^n \,k \sum_{j=n-k}^{n-1} \!1 + \!\sum_{k=1}^n \,k\sum_{i=n+2-k}^{n+1} \!1 \\ = \sum_{k=1}^n k \cdot k + \sum_{k=1}^n k \cdot k + \sum_{k=1}^n k \cdot k = 3 \sum_{r=1}^n r^2$$

$\endgroup$
  • $\begingroup$ Nice answer (+1). $\endgroup$ – hypergeometric May 27 '18 at 14:51
2
$\begingroup$

Let all summations have the upper bound $n$, it makes your life easier. Then expand layer by layer. I also pull out the last term in the first sum. $$\begin{align*}\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)&=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j-1)+\sum_{j=1}^{n}(n+j)\\ &=\sum_{i=1}^{n}\left[\sum_{j=1}^{n}i+\sum_{j=1}^{n}j-n\right]+n^2+\sum_{j=1}^{n}j\\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}i+\sum_{i=1}^{n}\sum_{j=1}^{n}j-n^2+n^2+\sum_{j=1}^{n}j\\ &=n\color{blue}{\sum_{i=1}^{n}i}+\underbrace{\sum_{i=1}^{n}}_{n}\color{blue}{ \sum_{j=1}^{n}j}+\color{blue}{\sum_{j=1}^{n}j}\\ &=\left(2n+1\right)\sum_{r=1}^{n}r \end{align*}$$ Note that terms in blue are identical. You can then factor $(2n+1)$ without knowing the right hand side.

To write this sum in $$3\sum_{r=1}^n r^2$$ is much more trickier, without realizing the fact that $$\sum_{r=1}^n r^2=\frac{n(n+1)(2n+1)}{6}.$$

$\endgroup$
  • $\begingroup$ Thanks for your answer. (+1) $\endgroup$ – hypergeometric May 28 '18 at 1:16
1
$\begingroup$

Going over $i$ and then over $j$: $$ \begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &= \sum_{j=0}^{n-1}\sum_{i=1}^{n+1} (i+j) \\ &= \sum_{j=0}^{n-1} \frac{(n+1)(n+2)}{2} + (n+1) j \\ &= \frac{n(n+1)(n+2)}{2} + (n+1) \sum_{j=0}^{n-1} j \\ &= \frac{n(n+1)(n+2)}{2} + (n+1) \frac{(n-1)n}{2} \\ &= \frac{n(n+1)}{2} \left((n+2) + (n-1) \right) \\ &= \frac{n(n+1)(2n+1)}{2} \end{align} $$

$\endgroup$
1
$\begingroup$

In a patient, step-by-step manner, we have

$$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{i=0}^{n}\sum_{j=0}^{n-1}((i+1)+j)\\ &=\sum_{i=0}^{n}\sum_{j=0}^{n-1}(i+(1+j))\\ &=\sum_{i=0}^{n}\sum_{j=1}^{n}(i+j)\\ &=\sum_{i=0}^{n}\sum_{j=1}^ni+\sum_{i=0}^{n}\sum_{j=1}^nj\\ &=\sum_{i=0}^{n}\sum_{j=1}^ni+\sum_{j=1}^{n}\sum_{i=0}^nj\\ &=\sum_{i=0}^{n}ni+\sum_{j=1}^{n}(n+1)j\\ &=n\sum_{i=0}^ni+(n+1)\sum_{j=1}^nj\\ &=n\sum_{i=1}^ni+(n+1)\sum_{j=1}^nj\\ &=(2n+1)\sum_{r=1}^nr \end{align}$$

$\endgroup$
  • $\begingroup$ Nice answer (+1). $\endgroup$ – hypergeometric May 27 '18 at 14:52
1
$\begingroup$

Part (1) $$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{r=1}^n\sum_{i=1}^r r+\sum_{r=n+1}^{2n}\sum_{i=r-n+1}^{n+1}r &&\scriptsize(r=i+j)\\ &=\sum_{r=1}^nr^2+\sum_{r=n+1}^{2n}r(2n+1-r)\tag{*}\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n(2n+1-r')r' &&\scriptsize(r'=2n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n r(2n+1-r) &&\scriptsize(r=r')\\ &=(2n+1)\sum_{r=1}^n r\qquad\blacksquare\end{align}$$

Part (2)

Note that $$\begin{align} \sum_{r=n+1}^{2n}r\ (2n+1-r) &=\sum_{r=n+1}^{2n}\bigg[\big(2n+1-r\big)+\big(2r-2n-1\big)\bigg]\big(2n+1-r\big)\\ &=\sum_{r'=1}^n\bigg[r'+\big(2n-2r'+1\big)\bigg]\; r' &&\scriptsize (r'=2n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n r\; \big(2n-2r+1\big) &&\scriptsize (r=r')\\ &=\sum_{r=1}^n r^2+\sum_{t=1}^n (n+1-t)\ (2t-1) &&\scriptsize (t=n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{t=1}^n\sum_{s=t}^n (2t-1)\\ &=\sum_{r=1}^n r^2+\sum_{s=1}^n\sum_{t=1}^s (2t-1)\\ &=\sum_{r=1}^n r^2+\sum_{s=1}^n s^2\\ &=2\sum_{r=1}^n r^2 \end{align}$$ From $(*)$ in Part (1) above, $$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{r=1}^n r^2+\sum_{r=n+1}^{2n}r\ (2n+1-r)\\ &=\sum_{r=1}^n r^2+2\sum_{r=1}^n r^2\\ &=3\sum_{r=1}^n r^2\qquad\blacksquare\end{align}$$

A tabulated example for $n=5$ is shown below.

enter image description here

$\endgroup$
  • $\begingroup$ Very nice. (+1) $\endgroup$ – Markus Scheuer May 28 '18 at 19:14
  • $\begingroup$ @MarkusScheuer - Thanks! $\endgroup$ – hypergeometric May 29 '18 at 3:30
0
$\begingroup$

Denoting: $\sum_{k=1}^n1=A$: $$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=\sum_{i=1}^{n+1}(in+(A-n))=\sum_{i=1}^{n+1}(A+n(i-1))=\\ A(n+1)+n\sum_{i=1}^{n+1}(i-1)=A(n+1)+nA=(2n+1)A=\tfrac12 (2n+1)n(n+1).$$

$\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.