2 erating Functio This equation does not hold when [zl> 1, but once again we won't worry about conver- gence issues. This formula gives closed-form generating functions for a whole range of sequences. For example (1,1,1,1,)←→1+x+x2+x3 1+x 1+ax+a2x2+a3x3+ (1,0,1,0,1,0,……) 1+x2+x4+x6+ 2 Operations on Generating Functions The magic of generating functions is that we can carry out all sorts of manipulations on sequences by performing mathematical operations on their associated generating func- tions. Let' s experiment with various operations and characterize their effects in terms of 2.1 Scaling Multiplying a generating function by a constant scales every term in the associated se- quence by the same constant. For mple, we noted above that (1,0,1,0,1,0,)←→1+x2+x4+x°+ Multiplying the generating function by 2 gives 2 2+2x2+2x4+2x6+ which generates the sequence (2,0,2,0,2,0, Rule 1(Scaling Rule). If then cfo,cf1,cf2,…)←→c·F(x)2 Generating Functions This equation does not hold when | | z ≥ 1, but once again we won’t worry about conver￾gence issues. This formula gives closed­form generating functions for a whole range of sequences. For example: 1 , 1, 1, 1, . . .� 1 + x + x �1 ←→ 2 + x3 + · · · = 1 − x 1 �1, −1, 1, −1, . . .� ←→ 1 − x + x2 − x3 + x4 − · · · = 1 + x 1 3 3 �1, a, a2, a , . . .� 1 + ax + a2x2 + a x = 1 − ax ←→ 3 + · · · 1 4 + x6 �1, 0, 1, 0, 1, 0, . . .� 1 + x2 + x = 1 − x ←→ 2 + · · · 2 Operations on Generating Functions The magic of generating functions is that we can carry out all sorts of manipulations on sequences by performing mathematical operations on their associated generating func￾tions. Let’s experiment with various operations and characterize their effects in terms of sequences. 2.1 Scaling Multiplying a generating function by a constant scales every term in the associated se￾quence by the same constant. For example, we noted above that: 1 4 6 �1, 0, 1, 0, 1, 0, . . .� ←→ 1 + x 2 + x + x = 1 − x2 + · · · Multiplying the generating function by 2 gives 2 = 2 + 2x 2 + 2x 4 + 2x 6 1 − x2 + · · · which generates the sequence: �2, 0, 2, 0, 2, 0, . . .� Rule 1 (Scaling Rule). If �f0, f1, f2, . . .� ←→ F(x), then �cf0, cf1, cf2, . . .� ←→ c · F(x)