How did he "notice" this?

Question

Algorithms

Problem
Parsing

From here follows the solution of the problem. For each number, find the position of the most significant 1 bit pi. Then we need to count the number of pairs of numbers for which pi=pj. You can see that the answer is ∑ℓkℓ⋅(kℓ−1)2, where kℓ is the number of numbers that have pi=ℓ.

The complexity of the resulting solution in time is O(n).

How did he notice this formula? Before the words "You can notice" everything is clear.

Answer 1

Well, it's a well-known formula - the number of pairs among n objects. For the leftmost, n-1 right ends fit. For the second - there will be n-2 of them. For the latter - 0. Sum (n-1)+(n-2)+...+1+0 = (n-1)n/2. It can be obtained through the sum of an arithmetic progression.