# Combinatorics proof involving finite series

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.

The sum is

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

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.

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.

• It would be better to say the larger object rather than the second object. – N. F. Taussig Jun 17 at 9:50
• Yes. But I already labelled them. – tomriddle99 Jun 17 at 10:39
• 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. – N. F. Taussig Jun 17 at 10:53