Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$

Let's denote $P(G,k)$ be the chromatic polynomial of a simple graph $G$. By deletion-contraction formula, given any edge $e$ in $G$, we have the following: $$P(G,k)=P(G-e,k)-P(G\cdot e, k)$$ where $G-e$ is the graph obtained by deleting $e$ in $G$, and $G\cdot e$ is the graph obtained by contracting $e$ in $G$.

To prove that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$, we use induction on $n$. For $n=3$, it's easy to see that we need to use different colors for different vertices. Therefore, $$P(C_3,k)=k(k-1)(k-2)=(k-1)(k^2-2k)=(k-1)^3+(-1)^3(k-1).$$ This proves the case when $n=3$.

Now assume that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$. Apply the deletion-contraction formula to $G=C_{n+1}$, we have $$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k).$$ Note that the graph $C_{n+1}\cdot e$ is obtained by contracted an edge $e$ in $C_{n+1}$, which is isomorphic to $C_n$, which implies that $$P(C_{n+1}\cdot e, k)=P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1).$$ Note also that $C_{n+1}-e$ is the path $P_{n+1}$ with $n+1$ vertices, which implies that $$P(C_{n+1}-e, k)=P(P_{n+1},k)=k(k-1)^n.$$ (To see the last equality, we can use induction on number of vertices, or by simple counting argument: to color the end vertex, there are $k$ colors we can choose, then for the next one incident to the end vertex, there are $k-1$ colors we can choose, and so on.) Combining all these, we have $$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k)$$ $$=k(k-1)^n-(k-1)^{n}-(-1)^{n}(k-1)=(k-1)^{n+1} + (-1)^{n+1}(k-1),$$ as required.

You're on the right track. As far as I'm aware the greedy algorithm for finding a colouring and the deletion–contraction algorithm for counting them are two quite distinct algorithms. The deletion–contraction algorithm is exactly what you need. If you delete an edge in a cycle, the colourings of the remaining graph are straightforward to count, whereas if you contract an edge, you get a cycle with one fewer vertex. Thus you get a recurrence relation that expresses the number of colourings of $C_n$ as the number of colourings of $C_{n-1}$ plus a known expression. Then, since you already know the solution, you just have to verify that it solves this recurrence, and that it's correct for $n=2$.

You can also do this directly using the principle of inclusion–exclusion. Label the vertices of $C_n$ sequentially using the integers $0$, $1$, ..., $n-1$. For $S\subseteq\{0,1,\ldots,n-1\}$, let $T_S$ be the set of colorings (proper or improper) of $C_n$ in which, for each $j\in S$, the color of vertex $j$ is the same as that of vertex $j-1$ (with arithmetic performed mod $n$). The number of proper colorings is then $$ \lvert T_{\{\}}\rvert-\sum_{i=0}^{n-1}\lvert T_{\{i\}}\rvert+\sum_{0\le i<j<n}\lvert T_{\{i,j\}}\rvert-\ldots+(-1)^n\lvert T_{\{0,1,\ldots,n-1\}}\rvert. $$ Now there are $\binom{n}{m}$ different $S$ of size $m$. Furthermore, $$ \lvert T_S\rvert=\begin{cases}k^{n-\lvert S\rvert} & \text{if $\lvert S\rvert<n$,}\\ k & \text{if $S=\{0,1,\ldots,n-1\}$.}\end{cases} $$ Hence the number of proper colorings is $$ (-1)^nk+\sum_{m=0}^{n-1}\binom{n}{m}k^{n-m}(-1)^m $$ The result follows immediately from the binomial theorem.