0
935views
Find the generating function for the following series
  1. {0, 1, 2, 3, 4,………….}
  2. {1, 2, 3, 4, 5,………….}
  3. {2, 2, 2, 2, 2,………….}
  4. {0, 0, 0, 1, 1, 1, 1……}

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2014

1 Answer
0
7views
  1. {0, 1, 2, 3, 4,………….}

    Assume the generating function

    $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

    But, the given sequence is {0, 1, 2, 3, 4,…………}. Using this sequence, the expression above becomes

    f(x)$=x+2x^2+3x^3+4x^4…… \\ =x(1 +2x+3x^2+4x^3+……) \\ =x(1-x)^{-2}$

    Accordingly, $f(x) = x(1-x)^{-2}$ is the generating function for the given sequence {0, 1, 2, 3, 4,…………}

  2. {1, 2, 3, 4, 5,………….}

    Assume the generating function

    $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

    But, the given sequence is {1, 2, 3, 4,…}. Using this sequence, the expression above becomes

    f(x)$=1 +2x+3x^2+4x^3+…… =(1-x)^{-2}$

    Accordingly, $f(x)= (1-x)^{-2}$ is the generating function for the given sequence {1, 2, 3, 4,…}

  3. {2, 2, 2, 2, 2,………….}

    Assume the generating function

    $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

    But, the given sequence is {2, 2, 2, 2, 2,…………}. Using this sequence, the expression above becomes

    f(x)$=2 +2x+2x^2+2x^3+…… \\ =2(1+x+x^2+x^3+…….) \\ =2(1-x)^{-1}$

    Accordingly, $f(x) = 2(1-x)^{-1}$ is the generating function for the given sequence {2, 2, 2, 2, 2,…………}

  4. {0, 0, 0, 1, 1, 1, 1……}

    Assume the generating function

    $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

    But, the given sequence is {0, 0, 0, 1, 1, 1, 1……}. Using this sequence, the expression above becomes

    f(x)$=0 +0x+0x^2+x^3+x^4+x^5+x^6+…… \\ =x^3+x^4+x^5+x^6+…… \\ =x^3 (1+x+x^2+x^3+…….) \\ =x^3 (1-x)^{-1}$

    Accordingly, $f(x) = x^3 (1-x)^{-1}$ is the generating function for the given sequence {0, 0, 0, 1, 1, 1, 1…}

Please log in to add an answer.