In the study of combinatorics we often encounter the following foundational principle: If you can count the elements of a set in two different ways, producing two different formulae, then those two formulae are equal to each other.

An example: Suppose that you take the set {1,2,3,4} and you want to count the subsets of size two. To be clear, here are the subsets of size two listed in brute-force.

{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

So we can see already that the answer is "There are six of them." But let's count this in a principled way.

If you have a set {1, 2, ..., n}, how many ways are there to select a subset of size 2?

One way to count this is to count all possible pairs. There are \( n\cdot (n-1) \) pairs. This comes from picking a first element, where there are n choices, then picking a second element, where there are n-1 choices because one choice has been removed.

Every subset of two elements, like for instance {2, 3}, corresponds to two pairs like (2,3) and (3,2). Therefore the number of subsets of two elements is $$ \frac{n(n-1)}{2} $$

On the other hand we could have counted this in a different way. You could first pick 1 and then find all two-element subsetes with some other element. There are n-1 of these. Next pick 2 and then find all two-element subsets with some element other than 2 or 1. There are n-2 of these. And so on. Therefore the number of subsets is $$ \sum_{k=1}^n (n-k) $$

Therefore since these two formulae count the same set, then we have proved $$ \frac{n(n-1)}{2} = \sum_{k=1}^n (n-k) $$

Sometimes it is remarked that this interesting as a proof technique in mathematics. But I would propose that EVERY equality works in a basically similar way. We always have some quantity expressed in two different ways, so that they must be equal! Even $$ x=1-1/x$$ expresses one quantity in two different ways. But it is the sameness of the quantity which justifies writing the equation in the first place.