0
$\begingroup$

I am trying to prove the following identity with little success!:

$\sum_{k=0}^{p-1} (p-k) = p(p+1)/2$.

Any suggestions?

Thanks.

$\endgroup$
1
$\begingroup$

The sum is

$$(p-0)+(p-1)+\ldots+(p-(p-1))=1+2+\ldots+p=\frac{p(p+1)}2$$

$\endgroup$
1
$\begingroup$

I'd suggest that you reindex by letting $j=p-k,$ so that it becomes $$\sum_{k=0}^{p-1}(p-k)=\sum_{j=1}^pj,$$ which is hopefully a more familiar sum, whose closed form you already know.

$\endgroup$
1
$\begingroup$

You can write $\frac{p(p+1)}{2}$ as $p+1 \choose 2$. The left-hand side of the series $\sum_{k=0}^{p-1}(p-k)$ reduces to $1+2+3+...+p$ as shown by @DonAntonio.

Therefore the right-hand side of your equation is the number of ways you can choose $2$ objects from $p+1$ objects $i.e$ $p+1 \choose 2$

Now consider the left-hand side. Label the objects as $1, 2, ... , p+1$. If you choose the object labelled as $1$, you have $p$ choices for the larger object. If you choose the object labelled as $2$, you have $p-1$ choices for choosing the larger object and so on. Thus you get $p+p-1+ ... + 1$ as the number of ways of choosing $2$ objects from $p+1$ objects.

Therefore $1+2+...+p =$ ${p+1}\choose{2}$ $=\frac{p(p+1)}{2}$ And the combinatorial proof is complete.

$\endgroup$
  • $\begingroup$ It would be better to say the larger object rather than the second object. $\endgroup$ – N. F. Taussig Jun 17 at 9:50
  • $\begingroup$ Yes. But I already labelled them. $\endgroup$ – tomriddle99 Jun 17 at 10:39
  • 1
    $\begingroup$ If you choose the object labeled $2$, what prevents you from taking $1$ as your second object? What you have in mind is that $2$ is your smaller object, which means you have $p - 1$ choices for your larger object. $\endgroup$ – N. F. Taussig Jun 17 at 10:53

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.