3
$\begingroup$

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!

  • 0
    @user6312 thank you, I'd have forgotten the $b_0$!2011-06-13

1 Answers 1

4

Yes, your proof for a) is correct. For the generating function, observe that $\sum_{n=0}^\infty b_nx^n=1+kx\sum_{n=0}^\infty [(k-1)x]^n$ and recall what a geometric series is.

  • 1
    @Alessandro-De-Luca great, thank you for effort!2011-06-15