Home › Previous year questions › GATE 2022 CS › Question 36GATE 2022 CS – Question 36 Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Multiple choice
Which one of the following is the closed form for the generating function of the sequence $\{a_n\}_{n\ge0}$ defined below? $a_n=\begin{cases}n+1, & n \text{ is odd}\\ 1, & \text{otherwise}\end{cases}$
$\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$ $\frac{x(3-x^2)}{(1-x^2)^2}+\frac{1}{1-x}$ $\frac{2x}{(1-x^2)^2}+\frac{1}{1-x}$ $\frac{x}{(1-x^2)^2}+\frac{1}{1-x}$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (A) $\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$
Explanation $a_n=1$ for even $n$ and $a_n=n+1$ for odd $n$, so $a_n=1+n\cdot[n\text{ odd}]$.
$$G(x)=\sum_{n\ge0}a_nx^n=\underbrace{\sum_{n\ge0}x^n}_{1/(1-x)}+\sum_{n\text{ odd}}nx^n.$$
Let $O(x)=\sum_{n\text{ odd}}x^n=\dfrac x{1-x^2}$. Then $\sum_{n\text{ odd}}nx^n=x\,O'(x)$: $$O'(x)=\frac{(1-x^2)+2x^2}{(1-x^2)^2}=\frac{1+x^2}{(1-x^2)^2},\qquad xO'(x)=\frac{x(1+x^2)}{(1-x^2)^2}.$$
$$G(x)=\frac{x(1+x^2)}{(1-x^2)^2}+\frac1{1-x}:\text{ option (A)}.$$
More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions GATE 2021 CS (CS1) Q29 – There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing… GATE 2020 CS Q52 – The number of permutations of the characters in LILAC so that no character appears in its… GATE 2019 CS Q15 – Let U=\1,2,,n\. Let A=\(x,X) x X,\ X U\. Consider the following two statements on A . I. A… GATE 2018 CS Q11 – Which one of the following is a closed form expression for the generating function of the… GATE 2015 CS (CS1) Q45 – Let a n represent the number of bit strings of length n containing two consecutive 1s.… GATE 2016 CS (CS1) Q12 – Let a n be the number of n-bit strings that do NOT contain two consecutive 1s. Which one… All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →