5

Show that

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

without expanding the summation to its closed-form solution, i.e. $\dfrac 16n(n+1)(2n+1)$ or equivalent.

E.g., if $n=5$, then

$$\frac 14 \bigg[\;1(10) + 2(9)+ 3(8)+\cdots+10(1)\;\bigg]=1^2+2^2+3^2+4^2+5^2$$

Background as requested:
The summands for both equations are not the same but the results are the same. The challenge here is to transform LHS into RHS without solving the summation. It seems like an interesting challenge. If you like this question, please vote to reopen it. Thank you!

Hypergeometricx
  • 22,657

4 Answers4

4

$$\require{cancel}\begin{align} \frac14\sum_{i=1}^{2n}i(2n-i+1) &=\frac14\sum_{i=1}^{2n}\sum_{j=i}^{2n}i\\ &=\frac14\sum_{j=1}^{2n}\sum_{i=1}^j i && (1\le i\le j\le 2n)\\ &=\frac 14\sum_{j=1}^{2n}\binom {j+1}2\\ &=\frac14\sum_{r=1}^{n}\binom {2r}2+\binom{2r+1}2\\ &=\frac14\sum_{r=1}^n(2r)^2\\ &=\sum_{r=1}^nr^2 =\sum_{i=1}^ni^2\qquad\blacksquare \end{align}$$

This solution requires prior knowledge of the result for the sum of integers but does not require prior knowledge of the result for the sum of squares (i.e. $C$).

Hypergeometricx
  • 22,657
  • +1 Nice. Suggestion (if you want to avoid the combinations): $\sum_{i=1}^{2j}i + \sum_{i=1}^{2j-1}i = 1 + \sum_{i=2}^{2j}i + \sum_{i=1}^{2j-1}i = 1 + \sum_{i=1}^{2j-1}(i+1) + \sum_{i=1}^{2j-1}i = 1 + \sum_{i=1}^{2j-1}(2i+1) = 1 + 3 + 5 + \dots + (4j-1) = (2j)^2$ – Marconius Aug 18 '15 at 21:02
3

Notice that $2n - i + 1 = \sum_{k = 1}^{2n - i + 1} 1$, therefore, by changing the summation order of $i$ and $k$, \begin{align} & \sum_{i = 1}^{2n}i(2n - i + 1) \\ = & \sum_{i = 1}^{2n}\sum_{k = 1}^{2n - i + 1} i \\ = & \sum_{k = 1}^{2n}\sum_{i = 1}^{2n - k + 1} i \\ = & \sum_{k = 1}^{2n}\frac{(2n - k + 2 )(2n - k + 1)}{2} \\ = & \frac{1}{2}\sum_{k = 1}^{2n}(2n - k + 1)^2 + \frac{1}{2}\sum_{k = 1}^{2n}(2n - k + 1) \\ = & \frac{1}{2}\sum_{k = 1}^{2n}k^2 + \frac{1}{2}\sum_{k = 1}^{2n}k \end{align}

Zhanxiong
  • 14,040
  • Thanks for posting an answer. Can you complete it so that it ends up as RHS? Can you also show that it's the sum of squares without doing the full expansion? If so, then we can get to the closed form straight away. – Hypergeometricx Aug 17 '15 at 13:11
2

$$\frac14 \sum_{i=1}^{2n}i(2n+1-i)= \frac{2n+1}{4}\sum_{i=1}^{2n}i - \frac{1}{4}\sum_{i=1}^{2n}i^2$$ $$=\frac{2n+1}{4}\cdot \frac{2n\left(2n+1\right)}{2} - \frac{1}{4}\frac{\left(2n\right)\left(2n+1\right)\left(4n+1\right)}{6}$$ $$=\frac{2n+1}{4}\left[n(2n+1) - \frac{n(4n+1)}{3}\right]$$ $$=\frac{2n+1}{12}\left[3n(2n+1) - n(4n+1)\right] = \frac{2n+1}{12}\left[2n^2 + 2n\right]$$ $$= \frac16n\left(2n+1\right)(n+1)= \sum_{i=1}^ni^2$$

jameselmore
  • 5,207
1

I'm not sure how acceptable this answer is, because it uses induction and the triangle numbers identity of Gauss. Still, it doesn't directly use the sum of squares formula, so here goes. For abbreviation let $a_{i, n} = i(2n-i+1)$. Also let $S_n = \sum_{i=1}^{2n}a_{i, n}$ Now notice the following inductive identity:

$$S_{n + 1} = \sum_{i=1}^{2n + 2}a_{i, n + 1} = \sum_{i=1}^{2n}a_{i, n} + \sum_{i=1}^{2n}2i + 2n + 2 + (2n + 1)2 = S_n + 2n(2n + 1) + 2n + 2 + (2n + 1)2 = S_n + 4(n + 1)^2$$

Combine this with the base case of $S_1 = 4$ and you have an inductive proof of your identity.

Colm Bhandal
  • 4,649