This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Generating Functions”.

1. What is the sequence depicted by the generating series 4 + 15x^{2} + 10x^{3} + 25x^{5} + 16x^{6}+⋯?

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

Explanation: Consider the coefficients of each x

^{n}term. So a

_{0}=4, since the coefficient of x

_{0}is 4 (x

_{0}=1 so this is the constant term). Since 15 is the coefficient of x

^{2}, so 15 is the term a

_{2}of the sequence. To find a

_{1}check the coefficient of x

_{1}which in this case is 0. So a

_{1}=0. Continuing with these we have a

_{2}=15, a

_{3}=10, a

_{4}=25, and a

_{5}=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-6x^{2}

View Answer

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

Explanation: Basic generating function is \(\frac{1}{1-x}\). If we differentiate term by term in the power series, we get (1 + x + x

^{2}+ x

^{3}+⋯)′ = 1 + 2x + 3x

^{2}+ 4x

^{3}+⋯ 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-x^{2})

b) (1-A)-1/x

c) (1-A)+1/x^{2}

d) (A-x)/x^{3}

View Answer

Explanation: The generating function for the sequence A. Using differencing:

A = 1 + 9x + 25x

^{2}+ 49x

^{3}+ ⋯(1)

−xA = 0 + x + 9x

^{2}+ 25x

^{3}+ 49x

^{4}+ ⋯(2)

(1−x)A = 1 + 8x + 16x

^{2}+ 24x

^{3}+⋯. Since 8x + 16x

^{2}+ 24x

^{3}+ ⋯ = (1-x)A-1 ⇒ 8 + 16x + 24x

^{2}+…= (1-A)-1/x.

5. What is the recurrence relation for the sequence 1, 3, 7, 15, 31, 63,…?

a) a_{n} = 3a_{n-1}−2a_{n+2}

b) a_{n} = 3a_{n-1}−2a_{n-2}

c) a_{n} = 3a_{n-1}−2a_{n-1}

d) a_{n} = 3a_{n-1}−2a_{n-3}

View Answer

Explanation: The recurrence relation for the sequence 1, 3, 7, 15, 31, 63,… should be a

_{n}= 3a

_{n-1}−2a

_{n-2}. The solution for A: A=1/1 − 3x + 2x

^{2}.

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

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

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 a_{n}=4(7^{n})+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

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/x^{3}

c) (1−x)G+6/x

d) (1−x)G−x^{2}

View Answer

Explanation: (1−x)G = 4 + 3x + 6x

^{2}+ 9x

^{3}+⋯ which can be accepted. We can compute it like this:

3 + 6x + 9x

^{2}+ ⋯ = (1−x)G−4/x.

10. Find the sequence generated by 1/1−x^{2}−x^{4}.,assume that 1, 1, 2, 3, 5, 8,… has generating function 1/1−x−x^{2}.

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

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−x

^{2}−x

^{4}.

**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__.