GATE CS

Recurrence relations and generating functions

A recurrence relation defines each term of a sequence from earlier terms, and a generating function packs a whole sequence into one power series. For GATE you set up a recurrence for a counting problem, solve linear constant-coefficient recurrences by the characteristic equation, and use generating functions to read off terms, solve recurrences and count selections.

3 previous-year questions · 3 solved · 5 practice questions

Setting up a recurrence

Convention: a sequence is $a_{0}, a_{1}, a_{2}, \dots$ and $n$ runs over $N = {0, 1, 2, \dots}$ unless a question says otherwise. A recurrence gives $a_{n}$ in terms of earlier terms; it determines the sequence only together with enough initial conditions (for a recurrence of order $k$ , the first $k$ consecutive values).

To set up a recurrence for a counting problem, split the objects of size $n$ by what happens at the last position (or the first), so that each case reduces to a smaller count of the same kind. The cases must not overlap and must cover everything.

Procedure for a counting recurrence

Define $a_{n}$ precisely (what is counted, for which $n$ ).
Split the objects of size $n$ by the last symbol, last tile or last step.
Express each case as a count of a smaller size; add the cases.
Compute the initial values by direct listing, including $a_{0}$ if it makes sense.
Test the recurrence on a small $n$ by listing.

Problem	Recurrence	Initial values
Binary strings of length $n$ with no two consecutive 1s	$a_{n} = a_{n - 1} + a_{n - 2}$	$a_{0} = 1, a_{1} = 2$
Tilings of a $1 \times n$ strip with $1 \times 1$ and $1 \times 2$ tiles	$t_{n} = t_{n - 1} + t_{n - 2}$	$t_{0} = 1, t_{1} = 1$
Ways to climb $n$ stairs taking 1 or 2 steps at a time	$s_{n} = s_{n - 1} + s_{n - 2}$	$s_{0} = 1, s_{1} = 1$
Fibonacci numbers	$F_{n} = F_{n - 1} + F_{n - 2}$	$F_{0} = 0, F_{1} = 1$
Lucas numbers	$L_{n} = L_{n - 1} + L_{n - 2}$	$L_{0} = 2, L_{1} = 1$
Minimum moves for the Tower of Hanoi with $n$ discs	$H_{n} = 2 H_{n - 1} + 1$	$H_{0} = 0$
Regions of the plane cut by $n$ lines, no two parallel and no three through one point	$R_{n} = R_{n - 1} + n$	$R_{0} = 1$
Derangements of $n$ objects (permutations with no fixed point)	$D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ for $n \geq 2$	$D_{0} = 1, D_{1} = 0$
Catalan numbers: binary trees with $n$ nodes (unlabelled, left and right child distinguished)	$C_{n} = \sum_{i = 0}^{n - 1} C_{i} C_{n - 1 - i}$ for $n \geq 1$	$C_{0} = 1$

Closed forms for the table

No two consecutive 1s: $a_{n} = F_{n + 2}$ ; tilings and stairs: $t_{n} = s_{n} = F_{n + 1}$ .
Tower of Hanoi: $H_{n} = 2^{n} - 1$ .
Regions: $R_{n} = 1 + \frac{n ( n + 1 )}{2}$ (so $1, 2, 4, 7, 11, \dots$ ).
Derangements: $1, 0, 1, 2, 9, 44, \dots$ ; also $D_{n} = n D_{n - 1} + (- 1)^{n}$ for $n \geq 1$ .
Catalan: $1, 1, 2, 5, 14, 42, \dots$ ; $C_{n}$ also counts strings of $n$ matched pairs of parentheses and triangulations of a convex polygon with $n + 2$ sides.

CATALAN NUMBERS AND DERANGEMENTS

C_{n} = \frac{1}{n + 1} (n 2 n), D_{n} = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}

For $n \geq 0$ ; for example $C_{3} = \frac{1}{4} (3 6) = 5$ and $D_{4} = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 9$ .

Why the first row works: for $n \geq 2$ , a valid string of length $n$ ends in 0 (the first $n - 1$ symbols form any valid string) or ends in 01 (the first $n - 2$ symbols form any valid string). Hence $a_{n} = a_{n - 1} + a_{n - 2}$ for $n \geq 2$ , with $a_{0} = 1$ (the empty string) and $a_{1} = 2$ . Here $a_{2} = 3$ (00, 01, 10), so $a_{n} = F_{n + 2}$ .

WORKED EXAMPLE

Ternary strings over ${a, b, c}$ must not contain two consecutive $a$ 's. Let $a_{n}$ be the number of such strings of length $n$ . Find a recurrence and $a_{3}$ .

Solution

Strings ending in $b$ or $c$ : 2 choices for the last symbol after any valid string of length $n - 1$ , giving $2 a_{n - 1}$ .
Strings ending in $a$ : the symbol before it must be $b$ or $c$ (2 choices), and the first $n - 2$ symbols form any valid string, giving $2 a_{n - 2}$ .
So $a_{n} = 2 a_{n - 1} + 2 a_{n - 2}$ for $n \geq 2$ , with $a_{0} = 1$ and $a_{1} = 3$ .
$a_{2} = 2 \cdot 3 + 2 \cdot 1 = 8$ and $a_{3} = 2 \cdot 8 + 2 \cdot 3 = 22$ .
Check: of the 27 strings of length 3, those containing $aa$ are $aa ?$ (3) and $? aa$ (3), with $aaa$ in both lists, so $3 + 3 - 1 = 5$ ; and $27 - 5 = 22$ .

Answer: $a_{n} = 2 a_{n - 1} + 2 a_{n - 2}$ and $a_{3} = 22$ .

Linear homogeneous recurrences with constant coefficients

A linear homogeneous recurrence of order $k$ with constant coefficients has the form $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}$ with $c_{k} \neq = 0$ . Trying $a_{n} = r^{n}$ gives its characteristic equation.

CHARACTERISTIC EQUATION

r^{k} = c_{1} r^{k - 1} + c_{2} r^{k - 2} + \dots + c_{k}

For $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ ; it has degree $k$ , so $k$ roots over the complex numbers counted with multiplicity. Since $c_{k} \neq = 0$ , no root is 0.

GENERAL SOLUTION, DISTINCT ROOTS

a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots + α_{k} r_{k}^{n}

When all $k$ roots $r_{i}$ are distinct (real or complex); the constants $α_{i}$ come from the $k$ initial conditions.

CONTRIBUTION OF A REPEATED ROOT

a_{n} = (α_{0} + α_{1} n + \dots + α_{m - 1} n^{m - 1}) r^{n}

A root $r$ of multiplicity $m$ contributes this term; add the contributions of all roots.

FIBONACCI AND LUCAS CLOSED FORMS

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}, L_{n} = φ^{n} + ψ^{n}, φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

Roots of $r^{2} = r + 1$ ; $F_{0} = 0, F_{1} = 1$ and $L_{0} = 2, L_{1} = 1$ .

Procedure

Write the characteristic equation and find its roots with multiplicities.
Write the general solution (distinct roots: $α r^{n}$ ; repeated root: polynomial in $n$ times $r^{n}$ ).
Substitute the initial conditions to get linear equations for the constants.
Solve for the constants and check the closed form against several terms.

WORKED EXAMPLE

Solve $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ with $a_{0} = 1$ , $a_{1} = 4$ , and find $a_{5}$ .

Solution

Characteristic equation $r^{2} - 5 r + 6 = 0$ , so $r = 2$ or $r = 3$ .
$a_{n} = α 2^{n} + β 3^{n}$ .
$a_{0}$ : $α + β = 1$ . $a_{1}$ : $2 α + 3 β = 4$ . Hence $β = 2$ , $α = - 1$ .
$a_{n} = 2 \cdot 3^{n} - 2^{n}$ . Check: $a_{2} = 18 - 4 = 14$ and the recurrence gives $5 \cdot 4 - 6 = 14$ .
$a_{5} = 2 \cdot 243 - 32 = 454$ .

Answer: $a_{n} = 2 \cdot 3^{n} - 2^{n}$ and $a_{5} = 454$ .

WORKED EXAMPLE

Solve $a_{n} = 4 a_{n - 1} - 4 a_{n - 2}$ with $a_{0} = 1$ , $a_{1} = 0$ .

Solution

Characteristic equation $r^{2} - 4 r + 4 = (r - 2)^{2} = 0$ : a double root $r = 2$ .
$a_{n} = (α + β n) 2^{n}$ .
$a_{0} = α = 1$ . $a_{1} = 2 (1 + β) = 0$ gives $β = - 1$ .
$a_{n} = (1 - n) 2^{n}$ . Check: $a_{2} = - 4$ by the formula, and $4 \cdot 0 - 4 \cdot 1 = - 4$ from the recurrence.

Answer: $a_{n} = (1 - n) 2^{n}$ .

EXAM TIP

The number of constants equals the order $k$ , and you need exactly $k$ initial conditions. A quick check of $a_{1}$ and $a_{2}$ from both the recurrence and your closed form catches most algebra slips.

Non-homogeneous recurrences

For $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} + f (n)$ , the solution is $a_{n} = a_{n}^{(h)} + a_{n}^{(p)}$ : the general solution of the homogeneous part plus any one particular solution. Find the particular solution by a trial form matched to $f (n)$ , then fix the constants of the homogeneous part using the initial conditions of the full recurrence (not of the homogeneous part alone).

$f (n)$	Trial form $a_{n}^{(p)}$ if the base is not a characteristic root	If the base is a root of multiplicity $m$
constant $s$	$A$	$A n^{m}$ (base is 1)
$s^{n}$	$A s^{n}$	$A n^{m} s^{n}$
polynomial of degree $d$	polynomial of degree $d$ with unknown coefficients	$n^{m} \times$ (polynomial of degree $d$ ), base is 1
polynomial of degree $d$ times $s^{n}$	$s^{n} \times$ (polynomial of degree $d$ )	$n^{m} s^{n} \times$ (polynomial of degree $d$ )

If $f (n)$ is a sum of terms of different kinds (for example $n + 3^{n}$ ), find a particular solution for each term separately and add them.

FIRST-ORDER LINEAR RECURRENCE

a_{n} = c a_{n - 1} + d \Rightarrow a_{n} = c^{n} a_{0} + d \frac{c ^{n} - 1}{c - 1} (c \neq = 1), a_{n} = a_{0} + n d (c = 1)

For $n \geq 1$ with constants $c$ and $d$ . Example: $a_{n} = 2 a_{n - 1} + 1$ , $a_{0} = 0$ gives $2^{n} - 1$ .

WORKED EXAMPLE

Solve $a_{n} = 3 a_{n - 1} - 2 a_{n - 2} + 2^{n}$ with $a_{0} = 0$ , $a_{1} = 1$ .

Solution

Homogeneous part: $r^{2} - 3 r + 2 = 0$ , roots 1 and 2, so $a_{n}^{(h)} = α + β 2^{n}$ .
$f (n) = 2^{n}$ and 2 is a root of multiplicity 1, so try $a_{n}^{(p)} = A n 2^{n}$ .
Substitute and divide by $2^{n}$ : $A n = \frac{3}{2} A (n - 1) - \frac{1}{2} A (n - 2) + 1 = A n - \frac{A}{2} + 1$ , so $A = 2$ .
$a_{n} = α + β 2^{n} + n 2^{n + 1}$ . From $a_{0} = 0$ : $α + β = 0$ . From $a_{1} = 1$ : $α + 2 β + 4 = 1$ , so $α + 2 β = - 3$ . Hence $β = - 3$ , $α = 3$ .
$a_{n} = 3 - 3 \cdot 2^{n} + n 2^{n + 1}$ . Check: $a_{2} = 3 - 12 + 16 = 7$ , and the recurrence gives $3 \cdot 1 - 0 + 4 = 7$ . Also $a_{3} = 3 - 24 + 48 = 27$ and $3 \cdot 7 - 2 \cdot 1 + 8 = 27$ .

Answer: $a_{n} = 3 - 3 \cdot 2^{n} + n 2^{n + 1}$ .

WORKED EXAMPLE

Let $T (1) = 1$ and $T (n) = 2 T (n /2) + n$ for $n = 2, 4, 8, \dots$ (powers of 2). Find $T (n)$ .

Solution

Put $n = 2^{k}$ and $b_{k} = T (2^{k})$ : then $b_{k} = 2 b_{k - 1} + 2^{k}$ for $k \geq 1$ , with $b_{0} = 1$ .
Homogeneous part $α 2^{k}$ ; 2 is a root, so try $A k 2^{k}$ : $A k = A (k - 1) + 1$ gives $A = 1$ .
$b_{k} = α 2^{k} + k 2^{k}$ and $b_{0} = 1$ gives $α = 1$ , so $b_{k} = (k + 1) 2^{k}$ .
With $k = lo g_{2} n$ : $T (n) = n (lo g_{2} n + 1)$ . Check: $T (2) = 2 \cdot 1 + 2 = 4 = 2 \cdot 2$ ; $T (4) = 2 \cdot 4 + 4 = 12 = 4 \cdot 3$ ; $T (8) = 2 \cdot 12 + 8 = 32 = 8 \cdot 4$ .

Answer: $T (n) = n (lo g_{2} n + 1)$ for $n$ a power of 2.

EXAM TIP

If the usual trial form for $f (n)$ already appears in the homogeneous solution, it fails: substituting it into $a_{n} - c_{1} a_{n - 1} - \dots - c_{k} a_{n - k}$ gives 0, which cannot equal a non-zero $f (n)$ . Multiply by $n^{m}$ , where $m$ is the multiplicity of the base as a root. Constants must be fitted after adding the particular solution.

Ordinary generating functions

The ordinary generating function of a sequence $a_{0}, a_{1}, a_{2}, \dots$ is the formal power series $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ . The sequence is the list of coefficients, written $a_{n} = [x^{n}] A (x)$ . Convergence is not needed for counting; we only manipulate coefficients.

GEOMETRIC SERIES

\frac{1}{1 - x} = n \geq 0 \sum x^{n}, \frac{1}{1 - a x} = n \geq 0 \sum a^{n} x^{n}

Coefficients $1, 1, 1, \dots$ and $1, a, a^{2}, \dots$ ; so $1/ (1 + x)$ gives $(- 1)^{n}$ .

LINEAR SEQUENCES

\frac{1}{( 1 - x ) ^{2}} = n \geq 0 \sum (n + 1) x^{n}, \frac{x}{( 1 - x ) ^{2}} = n \geq 0 \sum n x^{n}

Coefficients $1, 2, 3, \dots$ and $0, 1, 2, 3, \dots$ .

NEGATIVE BINOMIAL SERIES

\frac{1}{( 1 - x ) ^{k}} = n \geq 0 \sum (k - 1 n + k - 1) x^{n}, \frac{1}{( 1 - a x ) ^{k}} = n \geq 0 \sum (k - 1 n + k - 1) a^{n} x^{n}

For integer $k \geq 1$ ; $[x^{n}] (1 - x)^{- k}$ counts solutions of $y_{1} + \dots + y_{k} = n$ in non-negative integers.

FINITE SERIES

(1 + x)^{m} = k = 0 \sum m (k m) x^{k}, \frac{1 - x ^{m + 1}}{1 - x} = 1 + x + \dots + x^{m}

For integer $m \geq 0$ ; the second gives a bounded choice of $0$ to $m$ items.

GENERALISED BINOMIAL THEOREM

(1 + x)^{u} = n \geq 0 \sum (n u) x^{n}, (n u) = \frac{u ( u - 1 ) \dots ( u - n + 1 )}{n !}

For any real $u$ , with $(0 u) = 1$ ; for $u = - k$ it gives the negative binomial series with signs, $(n - k) = (- 1)^{n} (n n + k - 1)$ .

SQUARES

n \geq 0 \sum n^{2} x^{n} = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}

Obtained by applying $x \frac{d}{d x}$ to $x / (1 - x)^{2}$ .

Operation on the sequence	Effect on the generating function
Add: $a_{n} + b_{n}$	$A (x) + B (x)$
Scale: $c a_{n}$	$c A (x)$
Shift right: $0, \dots, 0, a_{0}, a_{1}, \dots$ ( $k$ zeros)	$x^{k} A (x)$
Shift left: $a_{n + 1}$ (drop $a_{0}$ )	$\frac{A ( x ) - a _{0}}{x}$
Multiply by $n$ : $n a_{n}$	$x A^{'} (x)$
Partial sums: $a_{0} + \dots + a_{n}$	$\frac{A ( x )}{1 - x}$
Convolution: $\sum_{i = 0}^{n} a_{i} b_{n - i}$	$A (x) B (x)$
Replace $x$ by $x^{2}$ : $a_{0}, 0, a_{1}, 0, \dots$	$A (x^{2})$

To read a sequence off a rational closed form, first divide out any polynomial part if the numerator's degree is not smaller than the denominator's (it changes only the first few coefficients), then split the rest into partial fractions of the type $1/ (1 - a x)^{k}$ and use the series above. For example $\frac{3}{1 - 2 x} + \frac{1}{( 1 - x ) ^{2}}$ has coefficients $3 \cdot 2^{n} + (n + 1)$ .

Solving recurrences with generating functions

Procedure

Multiply the recurrence by $x^{n}$ and sum over all $n$ for which it holds.
Express each sum through $A (x)$ , using the shift rules and the initial terms.
Solve the resulting linear equation for $A (x)$ as a rational function.
Factor the denominator, split into partial fractions, and expand each piece.
Read off $a_{n}$ and check against the first terms.

FIBONACCI AND LUCAS GENERATING FUNCTIONS

n \geq 0 \sum F_{n} x^{n} = \frac{x}{1 - x - x ^{2}}, n \geq 0 \sum L_{n} x^{n} = \frac{2 - x}{1 - x - x ^{2}}

With $F_{0} = 0, F_{1} = 1$ and $L_{0} = 2, L_{1} = 1$ .

WORKED EXAMPLE

Use generating functions to solve $a_{n} = a_{n - 1} + 2 a_{n - 2}$ for $n \geq 2$ , with $a_{0} = 0$ , $a_{1} = 1$ .

Solution

Let $A (x) = \sum a_{n} x^{n}$ . The recurrence holds for $n \geq 2$ , so $A (x) - a_{0} - a_{1} x = x (A (x) - a_{0}) + 2 x^{2} A (x)$ .
With $a_{0} = 0$ , $a_{1} = 1$ : $A (x) - x = x A (x) + 2 x^{2} A (x)$ , so $A (x) (1 - x - 2 x^{2}) = x$ .
$1 - x - 2 x^{2} = (1 - 2 x) (1 + x)$ , so $A (x) = \frac{x}{( 1 - 2 x ) ( 1 + x )}$ .
Partial fractions: $A (x) = \frac{1}{3} (\frac{1}{1 - 2 x} - \frac{1}{1 + x})$ . Check: $\frac{1}{3} \cdot \frac{( 1 + x ) - ( 1 - 2 x )}{( 1 - 2 x ) ( 1 + x )} = \frac{x}{( 1 - 2 x ) ( 1 + x )}$ .
So $a_{n} = \frac{2 ^{n} - ( - 1 ) ^{n}}{3}$ . Check: $a_{2} = 1$ and $a_{1} + 2 a_{0} = 1$ ; $a_{3} = 3$ and $a_{2} + 2 a_{1} = 3$ .

Answer: $a_{n} = \frac{2 ^{n} - ( - 1 ) ^{n}}{3}$ .

CATALAN GENERATING FUNCTION

C (x) = n \geq 0 \sum C_{n} x^{n} = \frac{1 - 1 - 4 x}{2 x}, C (x) = 1 + x C (x)^{2}

The quadratic comes from the convolution $C_{n} = \sum_{i = 0}^{n - 1} C_{i} C_{n - 1 - i}$ ; the minus sign is the root with $C (0) = 1$ . Expanding by the generalised binomial theorem gives $C_{n} = \frac{1}{n + 1} (n 2 n)$ .

EXAM TIP

Before any cancellation with the numerator, the denominator of $A (x)$ is the characteristic polynomial written backwards, $x^{k} p (1/ x)$ : for $r^{2} - r - 2$ you get $1 - x - 2 x^{2}$ . A root $r$ of the characteristic equation corresponds to a factor $1 - r x$ .

Counting with generating functions

To count selections, build one factor per item type: the factor lists the allowed numbers of copies as powers of $x$ . The product's coefficient of $x^{n}$ counts the ways to select $n$ items in total, because multiplying the series adds exponents. Copies within a type are identical and the order of selection does not matter (multisets); equivalently, the coefficient counts ways to put $n$ identical objects into distinct boxes, one box per factor.

Restriction on a variable $y$	Factor
any $y \geq 0$	$\frac{1}{1 - x}$
$y \geq 1$	$\frac{x}{1 - x}$
$0 \leq y \leq m$	$1 + x + \dots + x^{m} = \frac{1 - x ^{m + 1}}{1 - x}$
$y$ even	$\frac{1}{1 - x ^{2}}$
$y$ odd	$\frac{x}{1 - x ^{2}}$
$y$ a multiple of $c$ ( $c \geq 1$ )	$\frac{1}{1 - x ^{c}}$

NON-NEGATIVE INTEGER SOLUTIONS

# {(y_{1}, \dots, y_{k}) : y_{1} + \dots + y_{k} = n, y_{i} \geq 0} = (k - 1 n + k - 1)

For $k \geq 1$ ; the coefficient of $x^{n}$ in $(1 - x)^{- k}$ , i.e. $n$ identical objects into $k$ distinct boxes. With every $y_{i} \geq 1$ the count is $(k - 1 n - 1)$ (for $n \geq k$ ; zero if $n < k$ ).

WORKED EXAMPLE

Find the number of solutions of $y_{1} + y_{2} + y_{3} = 12$ in non-negative even integers.

Solution

Each variable is even, so each factor is $\frac{1}{1 - x ^{2}}$ and the product is $\frac{1}{( 1 - x ^{2} ) ^{3}}$ .
Put $u = x^{2}$ : the coefficient of $x^{12}$ is the coefficient of $u^{6}$ in $(1 - u)^{- 3}$ .
That is $(2 6 + 2) = (2 8) = 28$ .

Answer: 28

EXAM TIP

For an upper bound use $(1 - x^{m + 1})^{k} / (1 - x)^{k}$ and expand the numerator by the binomial theorem; the terms beyond the target degree can be ignored. Also: always state which variable ranges over which values before writing the factor.

PREVIOUS-YEAR QUESTIONS

3 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2018

GATE 2023 CS Q.15

GATE 2023 · CSQ.15 · 1 mark · MCQ

The Lucas sequence $L_{n}$ is defined by the recurrence relation: $L_{n} = L_{n - 1} + L_{n - 2}$ , for $n \geq 3$ , with $L_{1} = 1$ and $L_{2} = 3$ .

Which one of the options given is TRUE?

(A)
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$
(B)
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{3})^{n}$
(C)
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{3})^{n}$
(D)
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}$

Answer and solution

GATE 2023 CS Q.15: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.15: answer and solution

GATE 2022 CS Q.36

GATE 2022 · CSQ.36 · 2 marks · MCQ

Which one of the following is the closed form for the generating function of the sequence ${a_{n}}_{n \geq 0}$ defined below?

a_{n} = {n + 1, 1, n is odd otherwise

(A)
$\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(B)
$\frac{x ( 3 - x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(C)
$\frac{2 x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(D)
$\frac{x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$

Answer and solution

GATE 2022 CS Q.36: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.36: answer and solution

GATE 2018 CS Q.1

GATE 2018 · CSQ.1 · 1 mark · MCQ

Which one of the following is a closed form expression for the generating function of the sequence ${a_{n}}$ , where $a_{n} = 2 n + 3$ for all $n = 0, 1, 2, \dots$ ?

(A)
$\frac{3}{( 1 - x ) ^{2}}$
(B)
$\frac{3 x}{( 1 - x ) ^{2}}$
(C)
$\frac{2 - x}{( 1 - x ) ^{2}}$
(D)
$\frac{3 - x}{( 1 - x ) ^{2}}$

Answer and solution

GATE 2018 CS Q.1: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.1: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · NAT

Let $a_{n}$ be the number of binary strings of length $n$ that do not contain three consecutive 0s, with $a_{0} = 1$ . Find $a_{6}$ .

Answer and solution

Answer: $44$

For $n \geq 3$ , split a valid string by its ending: 1, 10 or 100, each after any valid string of length $n - 1$ , $n - 2$ or $n - 3$ . (Ending 000 is not allowed.)
So $a_{n} = a_{n - 1} + a_{n - 2} + a_{n - 3}$ for $n \geq 3$ , with $a_{0} = 1$ , $a_{1} = 2$ , $a_{2} = 4$ .
$a_{3} = 7$ (only 000 is excluded), $a_{4} = 13$ , $a_{5} = 24$ , $a_{6} = 24 + 13 + 7 = 44$ .

PRACTICE 22 marks · MCQ

The sequence satisfies $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ for $n \geq 2$ with $a_{0} = 2$ and $a_{1} = 9$ . Which is the closed form for $a_{n}$ ?

(A)
$2 \cdot 3^{n} + n$
(B)
$(n + 2) 3^{n}$
(C)
$(3 n + 2) 3^{n}$
(D)
$(2 n + 2) 3^{n}$

Answer and solution

Answer: (B)

Characteristic equation $r^{2} - 6 r + 9 = (r - 3)^{2} = 0$ , a double root 3.
$a_{n} = (α + β n) 3^{n}$ . $a_{0} = α = 2$ .
$a_{1} = 3 (2 + β) = 9$ gives $β = 1$ .
$a_{n} = (n + 2) 3^{n}$ . Check $a_{2} = 4 \cdot 9 = 36$ and $6 \cdot 9 - 9 \cdot 2 = 36$ .

PRACTICE 32 marks · MSQ

Let $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ be an ordinary generating function. Which of the following statements are correct?

(A)
The coefficient of $x^{n}$ in $\frac{1}{( 1 - x ) ^{2}}$ is $n + 1$ .
(B)
$\frac{x}{( 1 - x ) ^{2}}$ is the generating function of $0, 1, 2, 3, \dots$ .
(C)
$\frac{1}{1 + x}$ is the generating function of the constant sequence $1, 1, 1, \dots$ .
(D)
The coefficient of $x^{4}$ in $\frac{1}{( 1 - x ) ^{3}}$ is 15.

Answer and solution

Answer: (A), (B), (D)

A: true, $\frac{1}{( 1 - x ) ^{2}}$ gives $1, 2, 3, \dots$ .
B: true, it is $x$ times the series of A.
C: false, $\frac{1}{1 + x} = \sum (- 1)^{n} x^{n}$ , giving $1, - 1, 1, \dots$ .
D: true, $(2 4 + 2) = 15$ .

PRACTICE 42 marks · NAT

How many solutions does $y_{1} + y_{2} + y_{3} = 10$ have, where each $y_{i}$ is an integer with $0 \leq y_{i} \leq 5$ ?

Answer and solution

Answer: $21$

Coefficient of $x^{10}$ in $(1 - x^{6})^{3} (1 - x)^{- 3}$ .
$(1 - x^{6})^{3} = 1 - 3 x^{6} + 3 x^{12} - \dots$ ; the $x^{12}$ term does not reach degree 10.
Count $= (2 12) - 3 (2 6) = 66 - 45 = 21$ .
Check by symmetry: $z_{i} = 5 - y_{i}$ gives $z_{1} + z_{2} + z_{3} = 5$ , and then $z_{i} \leq 5$ automatically, so $(2 7) = 21$ .

PRACTICE 51 mark · MCQ

Let $a_{0} = 1$ and $a_{n} = 3 a_{n - 1} + 4$ for $n \geq 1$ . What is $a_{6}$ ?

(A)
2185
(B)
2187
(C)
1457
(D)
2191

Answer and solution

Answer: (A)

Homogeneous solution $α 3^{n}$ ; the constant 4 gives a particular solution $A$ with $A = 3 A + 4$ , so $A = - 2$ .
$a_{n} = α 3^{n} - 2$ and $a_{0} = 1$ gives $α = 3$ , so $a_{n} = 3^{n + 1} - 2$ .
$a_{6} = 3^{7} - 2 = 2187 - 2 = 2185$ . Check: $a_{1} = 7$ from both the formula and the recurrence.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

recurrence relations, generating functions

Preparing in Kolkata? IAE Academy's course for GATE CSE.