1
$\begingroup$

I'm currently working on reducing the summation on the first line. The three lines below show the steps of the reduction according to the instructor. Unfortunately I'm not following the logic. Can someone help explain the algebraic transformations between each line?

$$\sum_{i=0}^{n-2} n-i-1$$

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

$$=(n-1)^2-\frac{(n-2)(n-1)}{2}$$

$$=\frac{n(n-1)}{2}$$

$\endgroup$
  • $\begingroup$ Am I correct in assuming that you're having trouble with the first and second step? $\endgroup$ – Nimnam1 Feb 4 '17 at 21:43
  • $\begingroup$ Yes, I'm blocked going from the first to the second step but would really appreciate an explanation between each step. I think some smaller or assumed to be trivial steps were left out for brevity but it's causing me not to understand. $\endgroup$ – Matthew Feb 4 '17 at 21:47
  • $\begingroup$ I do not feel you could have had so much trouble looking at the problem and understand it fine after reading my answer below in 7 minutes. I implore you to actually fully read answers before marking any correct. $\endgroup$ – Simply Beautiful Art Feb 4 '17 at 22:00
  • $\begingroup$ @icarusalways Let me concentrate on $\sum_{i=0}^{n-2} i$. It is known that $$\sum_{i=0}^{k} i=\frac{k\cdot (k+1)}{2}$$ Now you can substitute k by n-2 $$\sum_{i=0}^{n-2} i=\frac{(n-2)\cdot (n-2+1)}{2}=\frac{(n-2)\cdot (n-1)}{2}$$ $\endgroup$ – callculus Feb 4 '17 at 22:02
  • 1
    $\begingroup$ @SimplyBeautifulArt Nice answer. $\endgroup$ – callculus Feb 4 '17 at 22:06
2
$\begingroup$

We first split the sum:

$$\sum_{i=0}^{n-2}(n-i-1)=\color{#4488dd}{\sum_{i=0}^{n-2}(n-1)}-\color{#cc5500}{\sum_{i=0}^{n-2}i}$$

One can then factor:

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

and

$$\sum_{i=0}^{n-2}1=\underbrace{1+1+1+\dots+1}_{n-1}=n-1$$

And so,

$$\color{#4488dd}{\sum_{i=0}^{n-2}(n-1)=(n-1)(n-1)=n(n-1)-1(n-1)}$$

which is an explanation for the first step. In the next line, you will notice that it reduces down to $(n-1)^2$, which should be fairly obvious.

On the other hand, we have

$$\color{#cc5500}{\sum_{i=0}^{n-2}i=\frac{(n-2)(n-1)}2}$$

This has been heavily proven in many answers, so I'll leave it to you to see how all that works out.

The last step was combining the fractions:

$$\color{#4488dd}{(n-1)^2}-\color{#cc5500}{\frac{(n-2)(n-1)}2}=\color{#4488dd}{\frac{2(n-1)(n-1)}2}-\color{#cc5500}{\frac{(n-2)(n-1)}2}$$

$$=\frac{2(n-1)(n-1)-(n-2)(n-1)}2$$

$$=\frac{(2(n-1)-(n-2))(n-1)}2$$

$$=\frac{n(n-1)}2$$

$\endgroup$
1
$\begingroup$

Put $j=n-i-1$:

$$\sum_{i=0}^{n-2} n-i-1=\sum_{j=1}^{n-1} j=\frac {n(n-1)}2$$

$\endgroup$
  • 1
    $\begingroup$ Tbh, if the steps weren't already there, this would've been my answer. :D $\endgroup$ – Simply Beautiful Art Feb 5 '17 at 2:27

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.