(Fn-1+Fn-2 i fm≥2， generating function: Fn 1 if n =1 G(2)=>Fn.am 0 if n =0. m>0 recursion: G()=o+Fx+∑Fnx”=x+∑F-1xn+∑Fn-2n m>2 m>2 m>2 ∑F-1xn=∑n-1x”=∑ Fnxn+1 =xG(x) m≥2 m>1 m≥0 ∑Fn-2n=∑Fnxn+2=x2G() n≥2 m>0 identity: G(c)=x+(+x2)G(x)
Fn = ⌅⇤ ⌅⇥ Fn1 + Fn2 if n 2, 1 if n = 1 0 if n = 0. generating function: G(x) = n0 Fnxn G(x) = F0 + F1x + n2 Fnxn = x+ n2 Fn1xn + n2 Fn2xn = n0 Fnxn+1 = n0 Fnxn+2 n2 Fn2xn = x2G(x) = xG(x) G(x) = x + (x + x2)G(x) recursion: identity: n2 Fn1xn = n1 Fn1xn
Fn-1+Fn-2ifn≥2， generating function: 1 if n =1 G()=>Fnz" 0 if n=0. m>0 identity: G(x)=x+(x+z2)G(z) C solution: G(x)= 1-x-x2 1 1 1 1 expand: G()=V店'1-or V5 1-Ox 1+√5 2 -店 = n> n>0 v5 2 5(e-） n>
Fn = ⌅⇤ ⌅⇥ Fn1 + Fn2 if n 2, 1 if n = 1 0 if n = 0. generating function: G(x) = n0 Fnxn G(x) = x + (x + x2 identity: )G(x) G(x) = x 1 x x2 solution: expand: G(x) = 1 5 · 1 1 x 1 5 · 1 1 ˆ x = 1 5 n0 (x) n 1 5 n0 ( ˆ x) n = n0 1 5 n ˆ n xn = 1 + 5 2 ˆ = 1 5 2
Solving Recurrence I.Recurrence: a0=0 a1 =1 an=an-1+an-2 2.Manipulation: G(c）=∑anx”=∑am-1x”+∑ an-2xn n>0 m>1 m>2 =x+(x+x2)G(x) 3.Solving: G()=1-x-2 4.Expanding: )=∑Goe n! m>0
1. Recurrence: 2. Manipulation: 3. Solving: 4. Expanding: Solving Recurrence a0 = 0 a1 = 1 an = an1 + an2 G(x) = n⇥0 anxn = n⇥1 an1xn + n⇥2 an2xn = x + (x + x2)G(x) G(x) = x 1 x x2 G(x) = n0 G(n) (0) n! xn
Operations on generating functions G(a)=∑gnin F(c)=∑fnxm n≥0 n≥0 right shift: xkG(c)=∑ 9n-kzn n≥k left shift: c-d9r-∑ xck n+kZn n≥0 addition: F(z)+G(a)=>(fn+gn)z" m>0 scaling: G(c)=∑c"gnx” n>0 convolution: F(c)G()=∑∑fkgn-kx” n≥0k=0 differentiation: G'(c)=(n+1)9n+1a” m>0
G(x) = n0 gnxn F(x) = n0 fnxn Operations on generating functions xkG(x) = nk gnkxn G(x) k1 i=0 gixi xk = n0 gn+kxn F(x) + G(x) = n0 (fn + gn)xn G(cx) = n0 cngnxn F(x)G(x) = n0 n k=0 fkgnkxn G (x) = n0 (n + 1)gn+1xn right shift: left shift: addition: scaling: convolution: differentiation:
Changing Money (壹，伍)n=壹伍n-k k=0 of ways to change n yuan using 壹圆 》壹nx”=1十x+x2+…= 1 m>0 1-c :of ways to change n yuan using 伍圆 》伍n”=1+x5+x10+…= 1 m>0 1-x
Changing Money n ၊n : # of ways to change n yuan using 壹圆 : # of ways to change n yuan using 伍圆 n0 ၊nxn n0 nxn =1+ x + x2 + ··· =1+ x5 + x10 + ··· = 1 1 x = 1 1 x5 (၊ )n = n k=0 ၊knk
Changing Money (壹，伍)n=壹k伍n-k k=0 壹nx= 1 ∑伍nx” 1 n>0 1-C 1-2x5 n>0 》（壹，伍)mx”=》壹k伍n- m>0 m>0k=0 1 convolution! (1-x)(1-xc5)
= 1 (1 x)(1 x5) Changing Money n0 ၊nxn n0 nxn = 1 1 x = 1 1 x5 (၊ )n = n k=0 ၊knk = n0 n k=0 ၊knk convolution! n0 (၊ )nxn
Changing Money 件 50 100 (壹，伍，拾，贰拾，伍拾，壹佰)nxn m≥0 1 (1-x)(1-x5)(1-x10)(1-x20)(1-2x50)(1-x100)
Changing Money n0 (၊ ൎ م ൎ ൎ၊ϭ)nxn = 1 (1 x)(1 x5)(1 x10)(1 x20)(1 x50)(1 x100)
Solving Recurrence I.Recurrence: a0=0 a1 =1 an=an-1+an-2 2.Manipulation: G()=∑anx”=∑an-1x”+∑ an-2xn n>0 m>1 m>2 =x+(x+x2)G(x) 3.Solving: G()=1-x-2 4.Expanding: )=∑Go n! m>0
Solving Recurrence a0 = 0 a1 = 1 an = an1 + an2 G(x) = n⇥0 anxn = n⇥1 an1xn + n⇥2 an2xn = x + (x + x2)G(x) G(x) = x 1 x x2 G(x) = n0 G(n) (0) n! xn 1. Recurrence: 2. Manipulation: 3. Solving: 4. Expanding:
Expanding generating functions Taylor's expansion: ce-∑0 m>0 Geometric sequence: C 1-b2 =∑ ab”xn m>0 01 G(x)=1-b1x +e+…+1 a2 ak [x"G(c)=a1b2 +a262 +...+akbr
Expanding generating functions G(x) = n0 G(n) (0) n! xn Taylor’s expansion: Geometric sequence: G(x) = a1 1 b1x + a2 1 b2x + ··· + ak 1 bkx [xn]G(x) = a1bn 1 +a2bn 2 + ··· + akbn k a 1 bx = n0 abnxn
Expanding generating functions Binomial theorem: Newton's formula I+er-S@ m>0 (1+))m=a(a-1)(a-2)…(a-n+1)(1+c)-n generalized binomial coefficient: =a(a-1a-2)…(a-n+1) n!
Expanding generating functions Binomial theorem: (1 + x) = ⇤ n0 n ⇥ xn n ⇥ = ( 1)( 2)···( n + 1) n! generalized binomial coefficient: ((1 + x) ) (n) = ( 1)( 2)···( n + 1)(1 + x) n Newton’s formula