For an assignment I've been asked to provide a proof that k-means converges in a finite number of steps.

This is what I've written:


  In the following, $C$ is a collection of all the cluster centres. 
  Define an “energy” function
  $$E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert
 \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$$  The energy function is
  nonnegative. We see that steps (2)   and (3)   of the algorithm both
  reduce the energy. Since the energy is bounded from below and is
  constantly being reduced it must converge to a local minimum.
  Iteration can be stopped when $E(C)$   changes at a rate below a
  certain threshold.


Step 2 refers to the step which labels each data point by its closest cluster centre, and step 3 is the step where the centres are updated by taking a mean.

This is not sufficient to prove convergence in a finite number of steps. The energy can keep getting smaller but it doesn't rule out the possibility that the centre points can jump about without changing the energy much. In other words there might be multiple energy minima and the algorithm can jump about between them, no?

First, there are at most $k^N$ ways to partition $N$ data points into $k$ clusters; each such partition can be called a "clustering". This is a large but finite number. For each iteration of the algorithm, we produce a new clustering based only on the old clustering. Notice that 


if the old clustering is the same as the new, then the next
clustering will again be the same.
If the new clustering is
different from the old then the newer one has a lower cost


Since the algorithm iterates a function whose domain is a finite set, the iteration must eventually enter a cycle. The cycle can not have length greater than $1$ because otherwise by (2) you would have some clustering which has a lower cost than itself which is impossible. Hence the cycle must have length exactly $1$. Hence k-means converges in a finite number of iterations.
