Discrete Mathematics Multiple Choice Questions on “Discrete Probability – Generating Functions”.
1. What is the sequence depicted by the generating series 4 + 15x2 + 10x3 + 25x5 + 16x6+⋯?
a) 10, 4, 0, 16, 25, …
b) 0, 4, 15, 10, 16, 25,…
c) 4, 0, 15, 10, 25, 16,…
d) 4, 10, 15, 25,…
Answer: c
Clarification: Consider the coefficients of each xn term. So a0=4, since the coefficient of x0 is 4 (x0=1 so this is the constant term). Since 15 is the coefficient of x2, so 15 is the term a2 of the sequence. To find a1 check the coefficient of x1 which in this case is 0. So a1=0. Continuing with these we have a2=15, a3=10, a4=25, and a5=16. So we have the sequence 4, 0, 15, 10, 25, 16,…
2. What is the generating function for the sequence 1, 6, 16, 216,….?
a) (frac{(1+6x)}{x^3})
b) (frac{1}{(1-6x)})
c) (frac{1}{(1-4x)})
d) 1-6x2
Answer: b
Clarification: For the sequence 1, 6, 36, 216,… the generating function must be (frac{1}{(1-6x}), when basic generating function: (frac{1}{1-x}).
3. What is the generating function for generating series 1, 2, 3, 4, 5,… ?
a) (frac{2}{(1-3x)})
b) (frac{1}{(1+x)})
c) (frac{1}{(1−x)^2})
d) (frac{1}{(1-x2)})
Answer: c
Clarification: Basic generating function is (frac{1}{1-x}). If we differentiate term by term in the power series, we get (1 + x + x2 + x3 +⋯)′ = 1 + 2x + 3x2 + 4x3 +⋯ which is the generating series for 1, 2, 3, 4,….
4. What is the generating function for the generating sequence A = 1, 9, 25, 49,…?
a) 1+(A-x2)
b) (1-A)-1/x
c) (1-A)+1/x2
d) (A-x)/x3
Answer: b
Clarification: The generating function for the sequence A. Using differencing:
A = 1 + 9x + 25x2 + 49x3 + ⋯(1)
−xA = 0 + x + 9x2 + 25x3 + 49x4 + ⋯(2)
(1−x)A = 1 + 8x + 16x2 + 24x3 +⋯. Since 8x + 16x2 + 24x3 + ⋯ = (1-x)A-1 ⇒ 8 + 16x + 24x2 +…= (1-A)-1/x.
5. What is the recurrence relation for the sequence 1, 3, 7, 15, 31, 63,…?
a) an = 3an-1−2an+2
b) an = 3an-1−2an-2
c) an = 3an-1−2an-1
d) an = 3an-1−2an-3
Answer: b
Clarification: The recurrence relation for the sequence 1, 3, 7, 15, 31, 63,… should be an = 3an-1−2an-2. The solution for A: A=1/1 − 3x + 2x2.
6. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….?
a) 1, 5, 14, 30,…
b) 2, 8, 16, 35,…
c) 1, 4, 7, 9, 13,…
d) 4, 8, 9, 14, 28,…
Answer: a
Clarification: The first constant term is 1⋅1, next term will be 1⋅3 + 2⋅1 = 5, the next term: 1⋅5 + 2⋅3 + 3⋅1 = 14, another one: 1⋅7 + 2⋅5 + 3⋅3 + 4⋅1 = 30. The resulting sequence is 1, 5, 14, 30,…
7. What will be the sequence generated by the generating function 4x/(1-x)2?
a) 12, 16, 20, 24,…
b) 1, 3, 5, 7, 9,…
c) 0, 4, 8, 12, 16, 20,…
d) 0, 1, 1, 3, 5, 8, 13,…
Answer: c
Clarification: The sequence should be 0, 4, 8, 12, 16, 20,…for the generating function 4x/(1-x)2, when basic generating function: 1/(1-x).
8. What is the generating function for the sequence with closed formula an=4(7n)+6(−2)n?
a) (4/1−7x)+6!
b) (3/1−8x)
c) (4/1−7x)+(6/1+2x)
d) (6/1-2x)+8
Answer: c
Clarification: For the given sequence after evaluating the formula the generating formula will be (4/1−7x)+(6/1+2x).
9. Suppose G is the generating function for the sequence 4, 7, 10, 13, 16, 19,…, the find a generating function (in terms of G) for the sequence of differences between terms.
a) (1−x)G−4/x
b) (1−x)G−4/x3
c) (1−x)G+6/x
d) (1−x)G−x2
Answer: a
Clarification: (1−x)G = 4 + 3x + 6x2 + 9x3 +⋯ which can be accepted. We can compute it like this:
3 + 6x + 9x2 + ⋯ = (1−x)G−4/x.
10. Find the sequence generated by 1/1−x2−x4.,assume that 1, 1, 2, 3, 5, 8,… has generating function 1/1−x−x2.
a) 0, 0, 1, 1, 2, 3, 5, 8,…
b) 0, 1, 2, 3, 5, 8,…
c) 1, 1, 2, 2, 4, 6, 8,…
d) 1, 4, 3, 5, 7,…
Answer: a
Clarification: Based on the given generating function, the sequence will be 0, 0, 1, 1, 2, 3, 5, 8,… which is generated by 1/1−x2−x4.