# Counting possibilities of building words

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?

a) looks good. As for b): you already know what $b_n$ is, so the generating function is $\sum_{n \geq 0} b_n x^n = 1 + \sum_{n \geq 1} k(k-1)^{n-1} x^{n}$. Now the job is to transform this function into a closed expression. Use the geometric series. – t.b. Jun 13 '11 at 13:50