For a finite set $A$,let $|A|$ denote the number of elements in the set $A$.
(a) Let $F$ be the set of all functions
$$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying
$f(i)\ne f(i+1)$ for every $1\le i\le {n-1}$. Show that $|F|=k(k-1)^{n-1}$.
(b) Let $c(n,k)$ denote the number of functions in $F$ satisfying $f(n)\ne f(1)$.
For $n\ge 4$, show that
$$c(n,k)=k(k-1)^{n-1}-c(n-1,k)$$.
(c) Using (b) prove that for $n\ge 3$,
$$c(n,k)=(k-1)^n+(-1)^n(k-1)$$
I could solve the part (a),it is quite trivial.But, then next two parts are critical. Please help!
(a) Let $f:\{1,2,\ldots,n\}\mapsto \{1,2,\ldots,k\}$ be a function satisfying $f(i)\neq f(i+1)$ for $1\leq i\leq n-1$. Then $f(1)$ can be any number from $1$ to $k$, hence $k$ choices. But $f(2)$ only has $k-1$ options as it cannot be equal to $f(1)$. The same holds for $f(3),f(4),\ldots,f(n)$. Thus the total number of such mappings equals $k(k-1)^{n-1}$
(b) Denote by $C(n,k)$ the set of functions in $F$ satisfying $f(n)\neq f(1)$. You want to show $|C(n,k)|+|C(n-1,k)|=|F|$. Note that the set $F$ contains every element of $C(n,k)$ as well as those $f$'s in $F$ satisfying $f(n)=1$, i.e., $f$'s with $f(n-1)\neq 1$. Now if you force $f(n)=f(1)$ on every element in $C(n-1,k)$, what set do you get?
(c) Easily proved using induction and part(b)