Coloring polygon vertices

The vertices of a regular $n$-gon ($n \geq 3$) are to be colored with one of the $k$ colors such that no two adjacent vertices may have the same color. Let $f(n)$ be the number of legal coloring. Find a closed formula for $f(n)$.

Solution:

Suppose we sever one of the edges temporarily, so that we're left with a "string" of length $n$ where the first and last vertices are not connected. In order to color this string, we may color the first vertex $k$ ways, but each of the subsequent vertices may only be colored $k-1$ ways, avoiding the color of the previous vertex. Suppose $g(n)$ is the number of ways to color a string of length $n$, then $g(n) = k(k-1)^{n-1}$

Now, take one of these colored strings of length $n$ and join the first and last vertices. The resulting polygon may or may not be a valid coloring. It is not a valid coloring if and only if the first and last vertices have the same color. The number of such invalid coloring is the same as $f(n-1)$. There is a bijection between the invalid coloring where the first and last vertices have the same color and a valid coloring of an $(n-1)$-gon.

So: $$f(n) = g(n) - f(n-1)$$ Now, $f(3) = k(k-1)(k-2)$. So: $$f(4) = k(k-1)^3 - f(3) = k(k-1)(k^2 -3k+3) =(k-1)((k-1)^3+1)$$ $$f(5) = k(k-1)^4 - f(4) = k(k-1)(k^3-4k^2+6k-4) = (k-1)((k-1)^4-1)$$ $$f(6) = k(k-1)^5 - f(5) = (k-1)((k-1)^5+1)$$ So we can see a pattern, which we can prove via induction easily.

$$f(n) = (k-1)((k-1)^{n-1}+(-1)^n)$$