6.042/18.] Mathematics for Computer Science Apri!8,2005 Srini devadas and Eric Lehman Notes for recitation 16 Problem 1. Find closed-form generating functions for the following sequences. Do not concern yourself with issues of convergence (a)(2,3,5,0,0,0,0.,…) Solution 2+3x+5 (b)(1,1,1,1,1,1,1,) Solution 1+x+x2+x3+...= (c)(1,2,4,8,16,32,64, Solution 1+2x+4x2+8x32+…=(2x)+(2x)2+(2x)2+(2x)3+ (d)(1,0,1,0.,1,0,1,0,…) Solution 1+x2+x4 (e)(0,0,0,1,1,1,1,1, Solution x3(1+x+x2 (f)(1,3,5,7,9.,11,6.042/18.062J Mathematics for Computer Science April 8, 2005 Srini Devadas and Eric Lehman Notes for Recitation 16 Problem 1. Find closed­form generating functions for the following sequences. Do not concern yourself with issues of convergence. (a) �2, 3, 5, 0, 0, 0, 0, . . .� Solution. 2 + 3x + 5x 2 (b) �1, 1, 1, 1, 1, 1, 1, . . .� Solution. 1 3 1 + x + x 2 + x + . . . = 1 − x (c) �1, 2, 4, 8, 16, 32, 64, . . .� Solution. 3 1 3 1 + 2x + 4x 2 + 8x + . . . = (2x) 0 + (2x) + (2x) 2 + (2x) + . . . 1 = 1 − 2x (d) �1, 0, 1, 0, 1, 0, 1, 0, . . .� Solution. 1 4 6 1 + x 2 + x + x + . . . = 1 − x2 (e) �0, 0, 0, 1, 1, 1, 1, 1, . . .� Solution. 3 3 4 5 6 3 3 x x + x + x + x + . . . = x (1 + x + x 2 + x + . . .) = 1 − x (f) �1, 3, 5, 7, 9, 11, . . .�