8
$\begingroup$

I've found the following summation to be true $$\sum_{i=1}^3 i^2 = 3+(3+2)+(3+2+1)$$ and it works for the first $n$ numbers, I also know that there is already a summation for that: $\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}$ but that's not what I'm looking to use, my question is how would I appropiately write that first summation, could it be the following? $$\sum_{i=1}^n i^2 = n+\big(n+(n-1)\big)+\big(n+(n−1)+(n−2)\big)+\dots$$ I think that looks kind of ugly.

How would I write the previous summation with a correct notation?

$\endgroup$
  • 1
    $\begingroup$ The summation is fairly obvious if you consider it geometrically with blocks. You are taking a pyramid consisting of stacked squares each one unit high and all aligned to one corner, and slicing it vertically. $\endgroup$ – Wildcard Dec 19 '16 at 23:45
  • $\begingroup$ Indeed, I was just looking for a way to correctly represent that geometric/arithmetic relation between the number squares. $\endgroup$ – Pablo Ivan Dec 20 '16 at 1:39
6
$\begingroup$

You can write it as a double summation I believe, if I have understood you correctly:

$$ \sum_{i=1}^n i^2 = n+(n+(n-1)+\dots = \sum_{k=0}^n\sum_{i=0}^kn - i $$

I may have some of the indexing off by one but this is the general idea.

Here is a good intuition for why the double sum on the RHS equals the sum on the LHS. Let us make a grid of the double summation on the right, where the rows represent values of $k$ and columns represent values for $i$:

$$ \begin{array}{|c|ccc} \hline k \ \ / \ \ i& 0 & 1 & 2 & 3 & 4 & \ldots & n\\ \hline 0 & n & \\ 1 & n & n-1 \\ 2 & n & n-1 & n-2 \\ 3 & n & n-1 & n-2 & n-3 \\ 4 & n & n-1 & n-2 & n-3 & n-4 \\ \vdots & \vdots &\vdots &\vdots &\vdots &\vdots & \ddots \\ n & n & n-1 & n-2 & n-3 & n-4 & \ldots & 1\\ \end{array} $$

The double summation on the RHS given by:

$$ \sum_{k=0}^n\sum_{i=0}^kn - i $$

is equivalent to adding up the values in the grid row by row. That is, you start at the first row and read across till the column number equal to the current row you are on. So you read the $0$-th row across and get $n$, then you read across the first row and add $n + (n-1)$ and finally read across the second row and add $n + (n-1) + (n-2)$ and so on, giving a total of $(n) + (n + (n-1)) + (n + (n-1) + (n-2) + \cdots + (n + (n-1) + (n-2) + \cdots + 1)$.

But notice rather than adding across the rows, we can equivalently add down the columns. That is, we start at column $0$ and add all the values in this column which are $n$ copies of the value $n$ giving a total of $n^2$. We then move on to the next column and add the values down this column which consists of $n-1$ copies of $n-1$ giving a total of $(n-1)^2$. Continuing in this way, we get that the sum in the grid is equal to:

$$ n^2 + (n-1)^2 + (n-2)^2 + \cdots + 1 \\ = \sum_{i = 0}^n i^2 $$

thus the RHS is equal to the LHS.

$\endgroup$
  • $\begingroup$ Within that double summation, where is the power? And why subtracting i from n? Could you expand on that a bit? Thanks. $\endgroup$ – Pablo Ivan Dec 19 '16 at 20:11
  • 1
    $\begingroup$ @PabloIvan My answer is only showing how to rewrite the right hand side of your equation in summation notation. I will expand the answer to show you how to get the power. $\endgroup$ – gowrath Dec 19 '16 at 20:13
  • $\begingroup$ In your expanded answer could you include an example, say 3^2 + 2^2 + 1^2? $\endgroup$ – Pablo Ivan Dec 19 '16 at 20:44
3
$\begingroup$

You can probably write it as $\sum\limits_{i=1}^n i^2=\sum\limits_{i=1}^n \sum\limits_{j=1}^i (n+1-j)$

$\endgroup$
  • 1
    $\begingroup$ I think op is specifically asking about writing $n + (n + (n - 1)) + (n + (n-2) + (n-3)) + \ldots $ $\endgroup$ – gowrath Dec 19 '16 at 20:08
  • $\begingroup$ yeah, my bad. thanks for that. $\endgroup$ – Jorge Fernández Hidalgo Dec 19 '16 at 20:09
  • 1
    $\begingroup$ @PabloIvan That original summation was equivalent to writing your series backwards i.e. $(1) + (1 + 2) + (1+2+3) + \cdots + (1 + 2 + 3 + \cdots n)$. $\endgroup$ – gowrath Dec 19 '16 at 20:11
  • $\begingroup$ But then the expression fails. If I want to sum 3^2+2^2+1^2, using your formula I would write: 1 + (1+2) + (1+2+3) = 10, which isn't the case since the correct answer is: 3 + (3+2) + (3+2+1) = 14, now that is the correct result. $\endgroup$ – Pablo Ivan Dec 19 '16 at 20:22
  • $\begingroup$ @PabloIvan which is why the poster edited his answer to a correct one $\endgroup$ – gowrath Dec 19 '16 at 20:49
2
$\begingroup$

Putting aside all the neat manipulations one can do with summation identities, note that $$\begin{align} \text{RHS}=\quad &\color{red}3\\ +(&\color{red}3+\color{green}2)+\\ +(&\color{red}3+\color{green}2+\color{blue}1)\\\\\ =3(&\color{red}3)+2(\color{green}2)+1(\color{blue}1)\\\\ =\; \; \; &3^2+2^2+1^2\\\\ =\;\;\;&\sum_{i=1}^3 i^2 = \text{LHS} \end{align}$$

You can prove the general case using the same method.


The formal notation for $n$ numbers, as requested, and the proof that it is equal to the sum of squares is as follows:

$$\begin{align} \color{purple}{\sum_{i=1}^n}\sum_{j=1}^i \color{orange}{(n+1-j)} &=\color{purple}{\sum_{i=1}^n}\sum_{j=1}^i\color{orange}{\sum_{k=j}^n1}\\ &=\sum_{j=1}^n\color{purple}{\sum_{i=j}^n}\color{orange}{\sum_{k=j}^n1} && (1\le j\le i\le n)\\ &=\sum_{r=1}^n \;\;\color{purple}{\sum_{i=(n+1-r)}^n} \;\color{orange}{\sum_{k=(n+1-r)}^n 1} &&(r=n+1-j)\\ &=\sum_{r=1}^n \qquad \color{purple}r\;\;\cdot \quad \color{orange}r\\ &=\sum_{r=1}^n r^2 =\sum_{i=1}^n i^2 \end{align}$$

$\endgroup$
  • $\begingroup$ That +1 is because you are indexing from one, isn't it? $\endgroup$ – Pablo Ivan Dec 20 '16 at 18:35
  • $\begingroup$ Which +1 are you referring to? $\endgroup$ – hypergeometric Dec 20 '16 at 18:39
  • $\begingroup$ r=n+1-j, that one. $\endgroup$ – Pablo Ivan Dec 20 '16 at 21:36
  • $\begingroup$ @PabloIvan - the number of items from $a$ to $b$ ($b>a)$ inclusive of both $a,b$ is $b+1-a$. $\endgroup$ – hypergeometric Dec 21 '16 at 2:28
  • 1
    $\begingroup$ This is a great algebraic answer (y) $\endgroup$ – gowrath Dec 21 '16 at 2:55
1
$\begingroup$

Note that $i= \sum_{j=1}^i(1)$. Hence, we can write

$$\begin{align} \sum_{i=1}^n i^2&=\sum_{i=1}^n i\sum_{j=1}^i(1)\\\\ &=\sum_{j=1}^n \sum_{i=j}^n i\,\,\dots\text{changing the order of summation}\\\\ &=\sum_{j=n}^1 \sum_{i=j}^n i \,\,\dots\text{reversing the order of the exterior summation}\\\\ &=n+(n+(n-1))+(n+(n-1)+(n-2))+\cdots+\sum_{i=1}^n i \end{align}$$

as was to be shown!

$\endgroup$
  • 1
    $\begingroup$ What are the rules for transforming summations? I got a bit lost at the second step. $\endgroup$ – Pablo Ivan Dec 19 '16 at 21:09
  • $\begingroup$ Is the second step the change of order of summations or is it the reversing the order of the exterior sum? $\endgroup$ – Mark Viola Dec 19 '16 at 21:10
  • $\begingroup$ Changing the order of summations. $\endgroup$ – Pablo Ivan Dec 19 '16 at 21:12
  • 1
    $\begingroup$ To intuit the change of order, draw a grid $[1,n]\times[1,n]$ and see which grid points are implicated in each case. In the first, we see that as $j$ goes from $1$ to $i$ and $j$ goes from $1$ to $n$, the same points are covered when $i$ goes from $j$ to $n$ and $j$ goes from $1$ to $n$. $\endgroup$ – Mark Viola Dec 19 '16 at 21:17
  • 1
    $\begingroup$ It is indeed a double summation. Interestingly, we can pursue evaluating the double sum in closed form quite easily. $\endgroup$ – Mark Viola Dec 19 '16 at 21:28

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.