Generating Functions

    • Generating Functions represents sequences where each term of a sequence is expressed as a coefficient of a variable x in a formal power series.
    • Mathematically, for an infinite sequence, say a0,a1,a2,…,ak,…,
    • the generating function will be −
  • Gx=a0+a1x+a2x2+⋯+akxk+⋯=∑k=0∞akxk
    • Some Areas of Application
    • Generating functions can be used for the following purposes −
      • For solving a variety of counting problems. For example, the number of ways to make change for a Rs. 100 note with the notes of denominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50
      • For solving recurrence relations
      • For proving some of the combinatorial identities
      • For finding asymptotic formulas for terms of sequences
    • Problem 1
    • What are the generating functions for the sequences {ak}
  • with ak=2 and ak=3k ?
    • Solution
    • When ak=2 , generating function, G(x)=∑∞k=02xk=2+2x+2x2+2x3+…
    • When ak=3k, G(x)=∑∞k=03kxk=0+3x+6x2+9x3+……
    • Problem 2
    • What is the generating function of the infinite series; 1,1,1,1,… ?
    • Solution
    • Here, ak=1 , for 0≤k≤∞
    • Hence, G(x)=1+x+x2+x3+…⋯=1(1−x)
    • Some Useful Generating Functions
      • For ak=ak,G(x)=∑∞k=0akxk=1+ax+a2x2+……⋯=1/(1−ax)
    • For ak=(k+1),G(x)=∑∞k=0(k+1)xk=1+2x+3x2……⋯=1(1−x)2
    • For ak=cnk,G(x)=∑∞k=0cnkxk=1+cn1x+cn2x2+……⋯+x2=(1+x)n
    • For ak=1k!,G(x)=∑∞k=0xkk!=1+x+x22!+x33!……⋯=ex