elementary counting and specify the generating function

Question

Let $k\geq1$, and let $b_n$ be the number of words $\omega=v_1 \cdots v_n$ over the alphabet $\Sigma=\{1,\dots k\}$ such that $v_i\neq v_{i+1}$ for $1\leq i\leq n-1$.

1. I have to show with elementary counting techniques that $b_0=1$, and $b_n=k(k-1)^{n-1}$ for $n\geq1$ .

2. I must also specify the generating function $\sum \limits_{n\geq0}b_nx^n$

$ \begin{align*} f_b(x)&=\sum \limits_{n\geq0}b_nx^n \\ &=b_0 + \sum \limits_{n\geq1}b_nx^n \\ &=1+\sum \limits_{n\geq1}k(k-1)^{n-1}x^n\\ &=1+\sum \limits_{n\geq1}kx(k-1)^{n-1}x^{n-1}\\ &=1+\sum \limits_{n\geq1}kx((k-1)x)^{n-1}\\ &=1+kx\sum \limits_{n\geq0}((k-1)x)^{n} \\ &= ??? \end{align*} $

Thank you for any help.

Answer 1

As said in the comment the first problem is straightforward, as a hint take any word $w$ of length $n$ satisfying the requirements ($n\geq 2$) then you can write :

$$w=w'v_n $$

Where $w'$ is a word of length $n-1$ which satisfies the requirements. Now use this decomposition to show that for $n\geq 2$ you have :

$$b_n=b_{n-1}(k-1) $$

From this deduce the formula for 1 (you must compute $b_1$ to start).

You can also use this to compute the generating function $B:=\sum_nb_nX^n$ because you have :

$$B=b_0+b_1X+\sum_{n=2}^{\infty}b_nX^n=1+kX+\sum_{n=2}^{\infty}b_nX^n $$

$$B=1+kX+(k-1)\sum_{n=2}^{\infty}b_{n-1}X^n $$

$$B=1+kX+(k-1)X\sum_{n=2}^{\infty}b_{n-1}X^{n-1}=1+kX+(k-1)X\sum_{n=1}^{\infty}b_{n}X^{n} $$

$$B=1+kX+(k-1)X(B-b_0)$$

Remark that $b_0=1$.

Hence :

$$(1-(k-1)X)B=1+(k-(k-1))X=1+X $$

Hence :

$$B=\frac{1+X}{1-(k-1)X}=\frac{1-(k-1)X+kX}{1-(k-1)X}=1+\frac{kX}{1-(k-1)X}$$

This is the closed form of $B$. One can verify that this gives the same $B$ as before :

$$B=1+\sum_{n=1}^{\infty}k(k-1)^{n-1}X^n $$

Answer 2

Call the desired words Smirnov words. The crucial observation is that we can construct an unrestricted word from a Smirnov word by substituting an arbitrarily long string of consecutive like letters for each letter in a Smirnov word. For example, from the Smirnov word b,a,b,c we can construct unrestricted words like b,b,a,a,a,b,c,c,c,c. Let W(a,b,c,...k) = 1/(1-a-b-c-...-k) be the multivariate generating function for the number of ALL words on alphabet {a,b,c,...k}. W(a,b,c,...,k) = S(a/(1-a),b/(1-b),(c/(1-c),...,k/(1-k) where S(a,b,c,...,k) is the multivariate generating function for Smirnov words. Since the inverse of x/(1-x) = x/(1+x) we have S(a,b,c,...,k) = 1/(1 - a/(1+a) - b/(1+b) - c/(1+c) - ... -k/(1+k). If we only want to count the total number of Smirnov words then we substitute a->z, b->z, c->z ... k->z into the generating function to get 1/(1 - k*z/(1+z)).