Generating Functions Proof (cfo,cf1,cf2… cfo +cfia+cf222+ (o+fia+f2 2.2 Addition Adding generating functions corresponds to adding the two sequences term by term. For example, adding two of our earlier examples gives 1,1, 1.-1 1+ 2,0.2,0,2,0 1+ Weve now derived two different expressions that both generate the sequence (2, 0, 2, 0, .. Not surprisingly, they turn out to be equal 1 2 )(1+x)1-x2 Rule 2 (Addition Rule). If f,f1,f2, the Jfo+90,f1+g1,f2+g2,…)←→F(x)+G(x) Proof (fo+90,f1+g1,f2 (n+gn)r fn gn F(a)+G(a)Generating Functions 3 Proof. �cf0, cf1, cf2, . . .� cf0 + cf1x + cf2x ←→ 2 + · · · = c · (f0 + f1x + f2x 2 + · · ·) = cF(x) 2.2 Addition Adding generating functions corresponds to adding the two sequences term by term. For example, adding two of our earlier examples gives: 1 � 1, 1, 1, 1, 1, 1, . . . � ←→ 1 − x 1 + � 1, −1, 1, −1, 1, −1, . . . � ←→ 1 + x 1 1 � 2, 0, 2, 0, 2, 0, . . . � ←→ + 1 − x 1 + x We’ve now derived two different expressions that both generate the sequence �2, 0, 2, 0, . . .�. Not surprisingly, they turn out to be equal: 1 1 (1 + x) + (1 − x) 2 + = = 1 − x 1 + x (1 − x)(1 + x) 1 − x2 Rule 2 (Addition Rule). If �f0, f1, f2, . . .� ←→ F(x), and �g0, g1, g2, . . .� ←→ G(x), then �f0 + g0, f1 + g1, f2 + g2, . . .� ←→ F(x) + G(x). Proof. �∞ �f0 + g0, f1 + g1, f2 + g2, . . .� ←→ (fn + gn)x n n=0 � � � � �∞ �∞ = fnx n + gnx n n=0 n=0 = F(x) + G(x)