Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
sorry @Theo, I didn't mean to revert your edit… I just wanted to fix that missing $ and I didn't see the \cdots thing. – A. De Luca Jun 13 '11 at 13:57
also, I didn't see your comment before posting my answer… – A. De Luca Jun 13 '11 at 13:59
@Alessandro: No problem with both things. It's certainly better to have an answer than a comment. Your edit is better than mine since it also fixes the language (I approved it). – t.b. Jun 13 '11 at 14:05
@muffel: Minor point, you forgot to "justify" the statement $b_0=1$. This is true because there is exactly one empty word. (We need the empty word, silly as it may sound, to make the algebra come out right.) Also, your justification of $k(k-1)^{n-1}$ was informally fine, but a tad on the casual side. – André Nicolas Jun 13 '11 at 15:56
up vote 4 down vote accepted

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.

share|cite|improve this answer
@alessandro-de-luca How do you geht from $\sum_{n=0}^\infty b_nx^n$ to $1+kx\sum_{n=0}^\infty [(k-1)x]^n$? Neverthelesss your answer is a geometric series because each element can be calculated by multiplying the previous one by x. But why does a geometric series help me transforming $1+kx\sum_{n=0}^\infty [(k-1)x]^n$ to a closed expression? – muffel Jun 13 '11 at 18:09
@muffel, $\sum((k-1)x)^n$ is a geometric series, and there is a formula for the sum of a geometric series. – Gerry Myerson Jun 14 '11 at 0:27
@muffel, as to how you get from $\sum b_nx^n$ to the other sum, you've shown $b_n=k(k-1)^{n-1}$, so now you put that expression for $b_n$ into $\sum b_nx^n$ (and do a little algebra). – Gerry Myerson Jun 14 '11 at 0:29
@Gerry-Myerson I tried, but I couldn transform it to your term. (Neither by simple transforming nor by the binomial theorem). $\sum b_n x^n = k(k-1)^{n-1} x_n = $? Could you please give me another hint what you did. What would by the next step to get a "closed expression" from this? – muffel Jun 14 '11 at 7:32
@Alessandro-De-Luca great, thank you for effort! – muffel Jun 15 '11 at 6:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.