Fn-1十Fn-2 fn≥2， generating function: Fn= ifn=1 G(a)=∑Fnx" 0 if n=0. n>0 recursion: G(a)=F+Fx+∑Fnx”=c+∑En-1an+∑Fn-2an m>2 n>2 n>2 ∑Fn-1zn=∑Fn-1x”=∑Fnxn+1=xG(c) n>2 n>1 m>0 R-2=-∑Rn+2=2G) n>2 n>0 identity: G(x)=x+(x+x2)G(x)
n2 Fn1xn + n2 Fn2xn 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+ = 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+F-2 ifn≥2， generating function: Fn= if n =1 0 fn=0. G(c)=∑fna” n>0 identity: G(x)=x+(x+x2)G(x) solution: G()=1-r-x2 =Taylor denote 1+v√5 2 6=1-6 2 x 11 1 1 1-x-x2 V51-m v51-Φx
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: Taylor ? = 1 + 5 2 ˆ = 1 5 2 x 1 x x2 = 1 5 · 1 1 x 1 5 · 1 1 ˆ x denote =?
Fn-1+Fn-2 ifn≥2， generating function: En= if n=1 0 G(a)=∑Fnx” if n=0. n>0 identity: G（(x)=x+(x+x2)G(x) C solution: G()=1-x-2 1111 V5`1-ΦxV51-x 店如-o n>0 = 店(-）
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: = 1 5 n0 (x) n 1 5 n0 ( ˆ x) n = n0 1 5 n ˆ n xn = 1 5 · 1 1 x 1 5 · 1 1 ˆ x
(Fn-1+Fn-2 fn≥2， Fn= 1 if n=1 0 fn=0. 1+V5 6=1-v6 2 2 Ih= 1
= 1 + 5 2 ˆ = 1 ⇥5 2 Fn = 1 ⇥5 n ˆ n ⇥ Fn = ⌅⇤ ⌅⇥ Fn1 + Fn2 if n 2, 1 if n = 1 0 if n = 0
Ordinary Generating Function (OGF) {an} a0,01,02,··· generating function: G(）=∑anx=a0+a1x+a2.c2+. m=0 1 1-0c n=0
Ordinary Generating Function (OGF) G(x) = n=0 anxn = a0 + a1x + a2x2 + ··· {a a0, a1, a2,... n} generating function: 1 1 x = n=0 nxn