This homework is due on gradescope Friday November 11th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in LATEXis recommend though not required.

Question 1 (Binomial Theorem Identity, 20 points). Notice that (1−x2 )n  = (1+x)n (1−x)n .  By expanding both sides using the Binomial  Theorem and comparing terms,  derive a combinatorial identity.

Question 2 (Generating Functions for Polynomials, 20 points). Show that for m a non-negative integer that

nm xn  =  S(m,k)k! ( ) .

Question  3  (Finite Differences,  30 points).  Given  a  sequence  a(0),a(1),a(2), . . .,  define  the  first finite difference to be another sequence ∆a(n) = a(n)−a(n−1) for n ≥ 1 .  Define the kth finite difference ∆k a(n) to be the sequence obtained by applying the finite difference operation to the sequence a(i) a total of k times .

(a)  Given  the generating function A(x) = 又 a(n)xn  give  a formula for the generating function for its first finite difference B(x) = 又 ∆a(n)xn .  [15 points]

(b)  Show that for the sequence a(n) = nk for some integer k ≥ 0 that the (k+1)st finite difference ∆k+1a(n) is 0 for all sufficiently large n .  Hint:  You may want to use the result from Question 2 above .  [15 points]

Question 4 (Generating Function Calculations, points).  Derive formulas for the following generating func- tions:

(a)  The sequence an  is given by the recurrence a0  = a1  = a2  = 1 and an  = an −2 + an −3  for all n ≥ 3 .  Give a formula for the generating function A(x) = 又 an xn . [10 points]

(b)  The sequence bn  is given by the recurrence b0  = 1 and

bn  = {

bn/2             −b(n− 1)/2

if n is  even

if n is odd