Question: For a finite set $A$, let $|A|$ denote the number of elements in $A$. Let $F$ denote the set of all functions $f:\{1,2,3,4,\dot{}\dot{},n\}\rightarrow\{1,2,3,4,\dot{}\dot{},k\} (n\geq 3,k\geq 2)$ satisfying $f(i)\neq f(i+1) $ for every $i:1\leq i\leq n-1$ and $C(n,k)$ denote the number of functions in $F$ satisfying $f(n) \neq f(1)$. Then For $n \geq 3, C(n,k)$ is?
Answer given is $(k-1)^n + (-1)^n(k-1)$ but I happen to have no idea How to get there.
What i initially though was $f(1)$ can be chosen in $K$ ways and $f(r)$ for $r\neq 1$ in $(k-1)$ ways. So number of maps of $f$ are $$|F|=k(k-1)^{n-1}$$And the number of maps for $f(n)=(f1)$ is same as the number of maps in $F$ for which $f(n-1) \neq f(n)$ But That's it. I'm lost on how to proceed. Please guide.