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 ≠ 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 ∑ n ≥ 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 ( k − 1 ) possibilities because they depend on the element before themselves.Is this correct and complete?

Question

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    ≠      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       ∑          n      ≥      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   (  k  −  1  ) possibilities because they depend on the element before themselves.Is this correct and complete?

Kaleb Harrell · Accepted Answer

Yes, your proof for a) is correct. For the generating function, observe that      ∑          n      =      0        ∞        b    n        x    n    =  1  +  k  x      ∑          n      =      0        ∞    [  (  k  −  1  )  x      ]    n  and recall what a geometric series is.

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

Answered question

Answer & Explanation

New Questions in Precalculus