Rewrite $2 +\cdots + ( n-1) + n +(n-1)\cdot 2$ (possible error?)

52 Views Asked by At

This is from a book (regarding an analysis of selction sort), but isn't there an error between line $2$ and $3$?

\begin{align} n + &(n-1) + \cdots + 2 + (n-1)\cdot 2 \tag 1\\ &= 2 +\cdots + ( n-1) + n +(n-1)\cdot 2 \tag 2\\ &=\frac{n(n+1)}{2} -1 +(n-1)\cdot 2 \tag 3 \end{align} where \begin{align} 1 + 2 + \cdots (n-1) + n = \frac{n(n+1)}{2} \tag 4 \end{align}

My attempt:

From line $2$ we have \begin{align} 2 +\cdots + &( n-1) + n +(n-1)\cdot 2 \\ & = 2 + \cdots + 2n -1 +(n-1) \cdot 2 \tag 5 \end{align} and \begin{align} 2 + \cdots 2n = 2(1+2+ \cdots +n) = 2 \tag 6\frac{n(n+1)}{2} \end{align} So from line $5$ we end up with \begin{align} n(n+1) -1 +(n-1)\cdot 2 \tag 7 \end{align}

Have I missed something?

1

There are 1 best solutions below

2
On BEST ANSWER

The final $2$ is multiplied by only $(n-1)$, not by all the terms in the sum.

$2+\cdots+(n-1)+n+\color{green}{(n-1)\cdot2}$

$=\underbrace{\color{blue}1+2+\cdots+(n-1)+n}-\color{blue}1+\color{green}{(n-1)\cdot2}$

$=\dfrac{n(n+1)}2-1+\color{green}{(n-1)\cdot2}$