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!

  • 1
    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.2011-06-13
  • 0
    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.2011-06-13
  • 0
    also, I didn't see your comment before posting my answer…2011-06-13
  • 1
    @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).2011-06-13
  • 0
    @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.2011-06-13
  • 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.

  • 0
    @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?2011-06-13
  • 0
    @muffel, $\sum((k-1)x)^n$ is a geometric series, and there is a formula for the sum of a geometric series.2011-06-14
  • 0
    @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).2011-06-14
  • 0
    @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?2011-06-14
  • 0
    @muffel, the next step is to erase what you did and do what I said. In particular, I didn't say to delete the $\sum$-symbol, and I didn't say to write $x_n$.2011-06-14
  • 0
    @muffel, since $b_n=k(k-1)^{n-1}$ for $n>0$, you get $\sum_{n\geq 0} b_nx^n=b_0x^0+\sum_{n\geq 1}b_nx^n=1+\sum_{n\geq 1}k(k-1)^{n-1}x^n$2011-06-14
  • 0
    … then you can rewrite the last sum as $\sum_{n\geq 1}(kx)[(k-1)x]^{n-1}$. Taking $kx$ out of the sum and lowering the index of the sum, you get what I wrote in my answer. The resulting series is a geometric one, its ratio being $(k-1)x$ (**not** $x$ as you wrote in a previous comment).2011-06-14
  • 0
    @muffel, regarding "_why does a geometric series help me_", have you read [Wikipedia](http://en.wikipedia.org/wiki/Geometric_series#Formula)?2011-06-14
  • 0
    @Allesandro-De-Luca thank you, I haven't thought about the initial $b_0$! So regarding $1 + \sum_{n\geq 1} k(k-1)^{n-1}x^n$ the sum is a geometric series with the scale factor $a = k\cdot x$ and the common ratio $r = (k-1)x$, right? So the generating function is according the the formula from [Wikipedia](http://en.wikipedia.org/wiki/Geometric_progression#Geometric_series) $f(n) = 1 + \sum_{i=1}^n k(k-1)^{i-1} x^i = 1 + \frac{(k-1)x(kx-(kx)^n)}{1-(k-1)x}$, correct as well?2011-06-14
  • 0
    @muffel: not quite. You said you need the generating function, which is the sum of the whole series, not just the first $n$ terms. Read further ;)2011-06-14
  • 0
    @Allesandro-De-Luca Ok, the problem here seems to be that $|r| = |(k-1)x| \geq 1$. I don't understand that part - what is the solution and how is such a value with $r \geq 1$ calculated? I haven't every heard of a "Banach algebra" and now am completely confused ;)2011-06-14
  • 0
    @muffel, don't panic! The problem statement has nothing to do with convergence questions. You can treat the series as purely formal, i.e., use the formula for $\sum_{n\geq 0}r^n$ as if you were assuming $|r|<1$.2011-06-14
  • 0
    @Alessandro-De-Luca ok, that information saved my day ;) I'm gonna take $\sum\limits_{i=m}^\infty a r^i = \frac{ar^m}{1-r}$ as I am not sure about the index shifting for $\sum\limits_{n \geq 1}$ to $\sum\limits_{n \geq 0}$. That gets me $\sum_{n \geq 1} b_n x^n = \frac{kx(k-1)x}{1-(x(k-1))}$ Is the the (correct) final answer?2011-06-14
  • 0
    @muffel, Nope… I resign, $\sum_{n\geq 1}b_nx^n=\frac{kx}{1-(k-1)x}$. The reason why you _need_ the index shifting is that your formula has $r^{n-1}$ instead of $r^n$. What I did in my original answer is equivalent to defining a new index variable $m=n-1$ and then adjusting the sum accordingly (I used the symbol $n$ again instead of $m$, index names being irrelevant).2011-06-14
  • 1
    @Alessandro-De-Luca great, thank you for effort!2011-06-15