Problem

Count the number of ways to paint n fence posts with k colors such that no more than 2 adjacent posts have the same color.

There are n fence posts to be painted with k colors. Count the number of ways to paint them such that no more than 2 adjacent posts have the same color.