5
$\begingroup$

Show that

$$\sum_{i=1}^n(n-i+1)(2i-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

$$5(1) + 4(3)+ 3(5)+2(7)+1(9)=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.

Further edit
Thanks to those who voted to reopen the question!

$\endgroup$
  • $\begingroup$ Hmm I don't see what is so slow about expanding and collecting the terms by powers of $r$. Summation by parts works too, but would take about the same amount of computation. $\endgroup$ – user21820 Aug 15 '15 at 3:03
  • $\begingroup$ I think this is a duplicate. Looks a lot like this: math.stackexchange.com/questions/1408182/… $\endgroup$ – marty cohen Apr 4 '16 at 3:21
  • $\begingroup$ @martycohen - It is a duplicate only if the question asks to show that it is equivalent to the sum of squares without expanding to the closed-form solution. $\endgroup$ – hypergeometric Apr 4 '16 at 3:25
  • $\begingroup$ @martycohen - The summations may be related but it is definitely not a duplicate - the summands are different and the other question is a double summation. In any case this question was posted first so it cannot be a duplicate! $\endgroup$ – hypergeometric Apr 4 '16 at 3:50
3
$\begingroup$

Drawing pictures for this kind of problem helps. If you draw

$$ \newcommand{\BL} {\color{black}{\text{X}}} \newcommand{\BB} {\color{blue}{\text{X}}} \newcommand{\PP} {\color{purple}{\text{X}}} \newcommand{\RR} {\color{red}{\text{X}}} \begin{align} % & \boxed{\begin{array} {c} \BL \end{array}} \\ & \boxed{\begin{array} {cc} \BL & \BB \\ \BB & \BB \end{array}} \\ & \boxed{\begin{array} {ccc} \BL & \BB & \PP \\ \BB & \BB & \PP \\ \PP & \PP & \PP \end{array}} \\ & \boxed{\begin{array} {ccc} \BL & \BB & \PP & \RR \\ \BB & \BB & \PP & \RR \\ \PP & \PP & \PP & \RR \\ \RR & \RR & \RR & \RR \end{array}} \\ & \vdots % \end{align}$$

There are

  • $n$ sets of $1$ black squares,
  • $n-1$ sets of $3$ blue squares,
  • $n-2$ sets of $5$ purple squares,
  • $n-3$ setes of $7$ red squares,
  • $\vdots$
  • $n - r + 1$ sets of $2r-1$ squares of any given color

but the shapes together form a sum of squares pyramid. Algebraically that is:

$$\begin{align} % \sum_{r=1}^{n} (n - r + 1)(2r - 1) % &= \sum_{r=1}^{n} \left(\sum_{s=r}^n 1\right)(2r - 1) % \\ &= \sum_{r=1}^{n} \sum_{s=r}^n (2r - 1) % \\ &= \sum_{s=1}^{n} \sum_{r=1}^s (2r - 1) % \\ &= \sum_{s=1}^{n} s^2 % \end{align}$$

where the last step uses the fact that the sum of odd numbers up to $2k-1$ is $k^2$.

$\endgroup$
  • $\begingroup$ Yes very nice solution! (+1) That was how I started, hoping to find a shorter solution to the sum of squares by recognising the each square is the sum of odd numbers. $\endgroup$ – hypergeometric Aug 15 '15 at 6:39
  • $\begingroup$ @hypergeometric I felt like the logic was backwards when I was writing it. Anyway, if you want a short solution to sum of squares, I suggest looking at $\sum (k^3 - (k - 1)^3) = \sum (3k^2 - 3k + 1)$ , use telescoping on the left and the known closed form for $\sum k$ on the right. $\endgroup$ – DanielV Aug 15 '15 at 7:32
3
$\begingroup$

$$(n-r+1)(2r-1)=(n+1)(-1)+r[2(n+1)+1]-2r^2$$

$$\implies\sum_{r=1}^n(n-r+1)(2r-1)=-(n+1)\sum_{r=1}^n1+\{2(n+1)+1\}\sum_{r=1}^nr-2\sum_{r=1}^nr^2$$

$$=-(n+1)\cdot n+(2n+3)\cdot\dfrac{n(n+1)}2-2\cdot\dfrac{n(n+1)(2n+1)}6$$

$\endgroup$
2
$\begingroup$

$\begin{array}\\ \sum_{r=1}^n(n-r+1)(2r-1) &=\sum_{r=1}^n(n+1)(2r-1)-\sum_{r=1}^nr(2r-1)\\ &=(n+1)n^2-2\sum_{r=1}^nr^2+\sum_{r=1}^nr\\ &=(n+1)n^2-2\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\\ &=\frac{6(n+1)n^2-2n(n+1)(2n+1)+3n(n+1)}{6}\\ &=n(n+1)\frac{6n-2(2n+1)+3}{6}\\ &=n(n+1)\frac{2n+1}{6}\\ &=\frac{n(n+1)(2n+1)}{6}\\ \end{array} $

Now that's quite a surprise!

I'll stop here a try to find a magic trick later.

$\endgroup$
  • $\begingroup$ Well spotted! (+1) $\endgroup$ – hypergeometric Aug 15 '15 at 6:38
1
$\begingroup$

Make the substitution $i = n - r + 1$ (like change of variable in integration), then \begin{align} & \sum_{r = 1}^n (n - r + 1)(2r - 1) = \sum_{i = 1}^n i(2n - 2i + 1) \\ = & (2n + 1) \sum_{i = 1}^n i - 2\sum_{i = 1}^n i^2 \end{align} I think I didn't expand the term "brutally", but the last step is still slight expansion.

$\endgroup$
1
$\begingroup$

Here's the "magic" solution in more general form, followed by an continuous analog.

Let $f(n) =\sum_{i=1}^n (n+1-i)g(i) $. Note that $f(1) = g(1)$ and $f(2) =2g(1)+g(2) =g(1)+(g(1)+g(2)) $. Then

$\begin{array}\\ f(n+1) &=\sum_{i=1}^{n+1} (n+2-i)g(i)\\ &=\sum_{i=1}^{n+1} (n+1+1-i)g(i)\\ &=\sum_{i=1}^{n+1} (n+1-i)g(i)+\sum_{i=1}^{n+1} g(i)\\ &=\sum_{i=1}^{n} (n+1-i)g(i)+\sum_{i=1}^{n+1} g(i) \quad\text{(since }n+1-i = 0 \text{ for } i=n+1)\\ &=f(n)+\sum_{i=1}^{n+1} g(i)\\ so\\ f(n+1)-f(n)&=\sum_{i=1}^{n+1} g(i)\\ so\ that\\ f(n)&=\sum_{j=1}^n\sum_{i=1}^{j} g(i)\\ \end{array} $

Setting $g(n) = 2n-1$, since $\sum_{i=1}^{n} g(i) =n^2 $, $f(n) =\sum_{i=1}^{n} i^2 =\dfrac{n(n+1)(2n+1)}{6} $.

The continuous analog:

Let $f(x) =\int_0^x (x-y)g(y)dy $. Then

$\begin{array}\\ f(x) &=\int_0^x (x-y)g(y)dy\\ &=\int_0^x xg(y)dy-\int_0^x yg(y)dy\\ &=x\int_0^x g(y)dy-\int_0^x yg(y)dy\\ \text{so that}\\ f'(x)&=xg(x)+\int_0^x g(y)dy- xg(x)\\ &=\int_0^x g(y)dy\\ \text{Integrating,}\\ f(x)&=\int_0^x \int_0^y g(z)dz dy\\ \end{array} $

If $g(y) = 2y$, then $\int_0^x g(y)dy =x^2 $ so $\int_0^x (x-y)g(y) dy =\int_0^x y^2 dy =\dfrac{x^3}{3} $

$\endgroup$
1
$\begingroup$

$$\begin{align} \sum_{i=1}^n(n-i+1)(2i-1) &=\sum_{i=1}^n\sum_{j=i}^n(2i-1)\\ &=\sum_{j=1}^n\sum_{i=1}^j(2i-1) &&(1\le i\le j \le n)\\ &=\sum_{j=1}^n\sum_{i=1}^ji^2-(i-1)^2\\ &=\sum_{j=1}^n j^2&&\text{(by telescoping)}\\ &=\sum_{i=1}^n i^2\qquad\blacksquare \end{align}$$


Posting another solution which has just been suggested by a friend:

$$\begin{align} \sum_{i=1}^n i^2 =&\sum_{i=1}^n \color{blue}{-}(\color{blue}{n-i})i^2+\sum_{i=1}^n(\color{blue}{n-i}+1)i^2\\ =&\sum_{i=2}^{n+1} -(n-i+1)(i-1)^2+\sum_{i=1}^n(n-i+1)i^2\\ =&\sum_{i=1}^{n} -(n-i+1)(i-1)^2+\sum_{i=1}^n(n-i+1)i^2\\ =&\sum_{i=1}^{n} (n-i+1)\big[i^2-(i-1)^2\big]\\ =&\sum_{i=1}^{n} (n-i+1)(2i-1)\qquad\blacksquare\\\ \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.