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