Generating Functions Rule 4(Derivative Rule). If (f0,f1,f2,f3,)←→F(x), th (f1,2f23/f3,)+→F(x Proof. (f1,2f2,3f3,…)=f1+2f2x+3f3x2+ (o+fic+f2 z+f3 The Derivative Rule is very useful. In fact, there is frequent, independent need for each of differentiation s two effects, multiplying terms by their index and left-shifting one place. Typically, we want just one effect and must somehow cancel out the other. For ex ample, let's try to find the generating function for the sequence of squares, 0, 1, 4, 9, 16,...) If we could start with the sequence (1,1,1,1,.. and multiply each term by its index two times, then wed have the desired result: (0·0.1·1,22,3:3,……)=(0,1,4,9,) A challenge is that differentiation not only multiplies each term by its index, but also shifts the whole sequence left one place. However, the Right-Shift Rule 3 tells how to cancel out this unwanted left-shift: multiply the generating function by a Our procedure, therefore, is to begin with the generating function for (1,1,1, 1,..., differentiate, multiply by a, and then differentiate and multiply by r once more (1,2,3,4,…)←→ 1 dr l-r ( (0,1,2,3,…) (1-x)2 (1,4,9,16,… 1+x dr(1-x)2(1-x)3 1+xx(1+x) (,.49…)一x(-x)=(1-x)3 Thus, the generating function for squares isGenerating Functions 5 Rule 4 (Derivative Rule). If �f0, f1, f2, f3, . . .� ←→ F(x), then � �f1, 2f2, 3f3, . . .� ←→ F (x). Proof. �f1, 2f2, 3f3, . . .� = f1 + 2f2x + 3f3x 2 + · · · d (f0 + f1x + f2x 2 + f3x 3 = + dx · · ·) d = F(x) dx The Derivative Rule is very useful. In fact, there is frequent, independent need for each of differentiation’s two effects, multiplying terms by their index and left­shifting one place. Typically, we want just one effect and must somehow cancel out the other. For ex￾ample, let’s try to find the generating function forthe sequence of squares, �0, 1, 4, 9, 16, . . .�. If we could start with the sequence �1, 1, 1, 1, . . .� and multiply each term by its index two times, then we’d have the desired result: �0 · · · · 0, 1 1, 2 2, 3 3, . . .� = �0, 1, 4, 9, . . .� A challenge is that differentiation not only multiplies each term by its index, but also shifts the whole sequence left one place. However, the Right­Shift Rule 3 tells how to cancel out this unwanted left­shift: multiply the generating function by x. Our procedure, therefore, is to begin with the generating function for �1, 1, 1, 1, . . .�, differentiate, multiply by x, and then differentiate and multiply by x once more. 1 �1, 1, 1, 1, . . .� ←→ 1 − x d 1 1 �1, 2, 3, 4, . . .� ←→ = dx 1 − x (1 − x)2 1 x �0, 1, 2, 3, . . .� ←→ x · = (1 − x)2 (1 − x)2 d x 1 + x �1, 4, 9, 16, . . .� ←→ = dx (1 − x)2 (1 − x)3 1 + x x(1 + x) �0, 1, 4, 9, . . .� ←→ x · = (1 − x)3 (1 − x)3 Thus, the generating function for squares is: x(1 + x) (1 − x)3