Discrete Mathematics Questions and Answers – Discrete Probability – Generating Functions

«
»

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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,…
View Answer

Answer: c
Explanation: 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,…
advertisement

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
View Answer

Answer: b
Explanation: 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)}\)
View Answer

Answer: c
Explanation: 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: b
Explanation: 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.
advertisement

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,…
View Answer

Answer: a
Explanation: 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,…
View Answer

Answer: c
Explanation: 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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: a
Explanation: (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.
advertisement

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,…
View Answer

Answer: a
Explanation: 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.

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn