First, the base case. For all lists of length 1 we have only 1 distinct element on it.

Let's now assume is it true for all lists of length n, then we shall also prove is true for all lists of length n+1:

Say we have a1, a2, ..., an, an+1. Notice that the sublist a1, a2, ..., an is of length n, therefore all elements in there are the same. Notice also that the sublist a2, a3,..., an, an+1 is also of length n, therefore all elements there are equal to a2 and therefore equal to all elements from the first sublist.

QED