Let $k \geq 1$ be fix and $b_n$ be the amount of possible words $w = v_1 \cdots v_n$ of length $n$ on the alphabet $\{1,\ldots,k\}$, such that $v_i \neq v_{i+1},\; 1 \leq i \leq n -1$.
a) Show by counting that $b_0 = 1 \text{ and } b_n = k(k-1)^{n-1} \text{ for } n \geq 1.$
b) Identify the generating function $\sum_{n \geq 0} b_n x^n$
I tried a) first. For the first element of each word there are $k$ possibilities. For every successor there are (k-1) possibilities because they depend on the element before themselves.
Is this correct and complete?
How do I solve b)? How do I get this tranformed to a generating function?
Thank you in advance!