We are given a picket fence with $n$ pickets and we are given $k$ colors to paint it.
No more than two neighbouring pickets should share same color. In how many different ways can we paint the fence ?
For example if we have $2$ pickets and $4$ colors we have $16$ possible ways of painting the fence.
$4$ choices if every picket is painted the same color.
And then $4$ choices for the first picket * $3$ remaining choices for the second picket.
In total : $4$+$4*3 = 4 + 12 = 16$
My question is how can I build a recurrence relation for this problem ?
Let the number of ways be $C(n,k)$. Then the number of ways when the first picket cannot use a specific colour is $\frac{k-1}{k}C(n,k)$.
Then, for $n\ge 3$:-
The number of ways is $k \times\frac{k-1}{k}C(n-1,k)=(k-1)C(n-1,k)$.
The number of ways is $k \times 1\times \frac{k-1}{k}C(n-2,k)=(k-1)C(n-2,k)$.
$$C(n,k)=(k-1)\biggl(C(n-1,k)+C(n-2,k)\biggr).$$