# Let k>=1 be fix and b_n be the amount of possible words w=v_1⋯v_n of length n on the alphabet {1,…,k}, such that v_i not = v_i+1,1<=i<=n−1. a) Show by counting that b_0=1 and b_n=k(k−1)^(n−1) for n>=1. b) Identify the generating function Sum_(n>=0) b_n x^n

Let $k\ge 1$ be fix and ${b}_{n}$ be the amount of possible words $w={v}_{1}\cdots {v}_{n}$ of length $n$ on the alphabet $\left\{1,\dots ,k\right\}$, such that ${v}_{i}\ne {v}_{i+1},\phantom{\rule{thickmathspace}{0ex}}1\le i\le n-1$.
a) Show by counting that
.
b) Identify the generating function $\sum _{n\ge 0}{b}_{n}{x}^{n}$
My try:
a) first. For the first element of each word there are $k$ possibilities. For every successor there are $\left(k-1\right)$ possibilities because they depend on the element before themselves.
Is this correct and complete?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Kaleb Harrell
Yes, your proof for a) is correct. For the generating function, observe that
$\sum _{n=0}^{\mathrm{\infty }}{b}_{n}{x}^{n}=1+kx\sum _{n=0}^{\mathrm{\infty }}\left[\left(k-1\right)x{\right]}^{n}$
and recall what a geometric series is.