Dynamic programming - paint fence algorithm

total[i] = diff[i] + same[i]   (definition)

diff[i] = (k - 1) * total[i-1]
        = (k - 1) * (diff[i-1] + same[i-1])
        = (k - 1) * (diff[i-1] + diff[i-2])

Here's a combinatorics argument.

Let diff[i, c] be the number of ways to paint i posts according to the rules of the problem statement such that the last fence is painted with color c.

We have:

diff[i, c] = diff[i - 1, c'] + diff[i - 2, c''], c' != c OR c'' != c

For each c with which we paint i, the previous can either end with a c' != c (in which case we don't care what the second previous is), or the second previous can end with a c'' != c (in which case we don't care what the previous is), or both.

There are k - 1 possibilities for c' != c and k - 1 for c'' != c. So we can drop c from the recurrence and simply write:

diff[i] = (k - 1) * (diff[i - 1] + diff[i - 2])

Which is what you have.