18 312 Algebraic Combinatorics Lionel Levine Problem Set 3 Due at the beginning of class on Feb 24 2011 P9 Find a linear recurrence satisfied by the sequence S n 3 n 3 P10 Give an example with proof of a sequence that does not satisfy any linear recurrence P11 Let k 1 be an integer and let e2 i k Prove that any sequence of complex numbers a0 a1 a2 that is periodic with period k that is an k an for all n 0 can be written in the form an c0 c1 n c2 2n ck 1 k 1 n for some constants c0 ck 1 C P12 Let f n be the number of ways to make n cents out of pennies nickels dimes and quarters For example f 10 4 10 pennies or 5 pennies and 1 nickel or 2 nickels or 1 dime a Show that X n 0 f n xn 1 1 1 1 1 x 1 x5 1 x10 1 x25 b Write down a linear recurrence that f n satisfies c Prove that f 50n an3 bn2 cn 1 for some constants a b c 3 1 P13 If an satisfies a linear recurrence of order k and bn satisfies a linear recurrence of order show that an bn satisfies a linear recurrence of order k an bn satisfies a linear recurrence of order k a2n satisfies a linear recurrence of order k 1 2 P14 Find the values of the infinite series X Fn n 1 and 2n X Fn n 1 n 1 1 2 3 5 8 13 2 4 8 16 32 64 128 1 1 2 3 5 8 13 2 6 24 120 720 5040 3 2
View Full Document
Unlocking...