The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 6: Di↵erence Equations and Generating Functions –
Answers
Q1: (a) For each permutation of {1, 2, . . . , n} insert the element n+ 1 in any position
(b) We have A1 = 1. To verify that An = n! satisfies the recurrence and initial condition,
note that the formula gives
A1 = 1! = 1 and LHS = (n+ 1)! RHS = (n+ 1)n! = (n+ 1)!
as required.
Q2: (a) Consider a k-tuple, k < n of elements from {1, 2, · · · , n}. This k-tuple does not include n� k elements from the set. Any of these elements can be chosen to be the final entry in the (k + 1)-tuple (b) Bn,1 = n. With Bn,k = n! (n�k)! , we have Bn,1 = n! (n�1)! = n, and for the recurrence LHS = n! (n� k � 1)! RHS = (n� k) n! (n� k)! = n! (n� k � 1)! as required. Q3: Consider the recurrence an = 5an�1 � 6an�2, n = 3, 4, . . . with the initial conditions a1 = 1, a2 = 5. (a) Introduce generating function A(x) = 1X n=0 anx n take out first two terms then use an = 5an�1 � 6an�2, change summation index and solve for A(x). (b) 6x2 � 5x+ 1 = (1� 3x)(1� 2x) so we can write A(x) = x 6x2 � 5x+ 1 = a 1� 3x + b 1� 2x . Q4: (a) (1 + x+ x 2) | {z } Apples 1 $ no apples x $ 1 apple x2 $ 2 apples (1 + x) | {z } Pear (1 + x+ x2) | {z } Oranges (1 + x) | {z } Banana (b) a0 = 1, a1 = 4, a2 = 8, a3 = 10, a4 = 8, a5 = 4, a6 = 1. Q5: (a) In (1+x+x2+x3+ · · · )n each factor corresponds to the objects deposited in a given box. (b) The geometric series tells us that 1 + x+ x2 + x3 + · · · = 1/(1� x). (c) Taylor series for f(x) at x = 0 is f(x) = 1X p=0 f (p)(0) p! x p . Now set f(x) = (1 + x)↵. (d) Make the replacement x 7! �x and ↵ = �n (n a positive integer).