chapter

Recurrences and Generating Functions Short Notes for GATE CS

Recurrences and Generating Functions short notes for GATE CS: 7 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questi

recurrences and generating functions short notes

Summary: The Generating Function Cheat Sheet

.smart-card { font-family: system-ui, sans-serif; padding: 1.5rem; border-radius: 12px; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); } h3 { color: var(--color-primary); margin-top: 0; } .cheat-grid { display: grid; grid-template-columns: 1fr; gap: 1rem; } .cheat-item { background: color-mix(in srgb, var(--color-primary) 10%, transparent); padding: 0.8rem; border-radius: 6px; } .cheat-label { font-size: 0.8rem; font-weight: 700; text-transform: uppercase; color: var(--color-muted); margin-bottom: 0.3rem; display: block; } .math-inline { font-family: monospace; } Quick Reference Core Transforms {1} ⟹ \frac{1}{1 - x} {n + 1} ⟹ \frac{1}{( 1 - x ) ^{2}} {r^{n}} ⟹ \frac{1}{1 - r x} Key Operations x A (x) ⟹ Shift right by 1 A (x) B (x) ⟹ Convolution Extraction Rule \frac{1}{( 1 - x ) ^{k}} ⟹ (k - 1 n + k - 1) Mindset Treat as Formal Power Series. Ignore convergence. Check boundary terms.

The Characteristic Equation

The Characteristic Equation Summary If a homogeneous recurrence is written with all terms on one side as A_{0} a_{n} + A_{1} a_{n - 1} + A_{2} a_{n - 2} + \dots + A_{k} a_{n - k} = 0, with A_{0} \neq = 0, then its characteristic equation is A_{0} r^{k} + A_{1} r^{k - 1} + A_{2} r^{k - 2} + \dots + A_{k} = 0. For the common normalized form a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}, move everything to one side: a_{n} - c_{1} a_{n - 1} - c_{2} a_{n - 2} - \dots - c_{k} a_{n - k} = 0. Therefore the characteristic equation is r^{k} - c_{1} r^{k - 1} - c_{2} r^{k - 2} - \dots - c_{k} = 0. The roots of this polynomial are called the characteristic roots .

The Master Theorem

The Master Theorem For T (n) = a T (n / b) + f (n) where a \geq 1, b > 1 : Compute the critical exponent : E = lo g_{b} a . Compare f (n) with n^{E} : Case 1 (Leaves dominate): If f (n) = O (n^{E - ϵ}) for some constant ϵ > 0 : T (n) = Θ (n^{E}) Case 2 (Balanced): If f (n) = Θ (n^{E}) : T (n) = Θ (n^{E} lo g n) Case 3 (Root dominates): If f (n) = Ω (n^{E + ϵ}) for some constant ϵ > 0, and the regularity condition a \cdot f (n / b) \leq c \cdot f (n) holds for some constant c < 1 and all sufficiently large n : T (n) = Θ (f (n)) Note: The regularity condition in Case 3 ensures f (n) does not fluctuate wildly as it shrinks.

4 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Consider the recurrence a_{n} = 5 a_{n - 1} - 6 a_{n - 2} . Which of the following statements about its characteristic equation is TRUE?

Question 2

Level 1: Warm-up

The generating function for a sequence is A (x) = \frac{1}{1 - 3 x} . What is the maximum value of n for which the coefficient of x^{n} is strictly less than 100?

Question 3

Level 1: Warm-up

Assertion (A): The general solution to the recurrence a_{n} = 4 a_{n - 1} - 3 a_{n - 2} is a_{n} = α_{1} 3^{n} + α_{2} 1 . Reason (R): The characteristic roots of the recurrence are 3 and 1 .

Question 4

Level 1: Warm-up

For the divide-and-conquer recurrence T (n) = 8 T (n /2) + n^{k}, what is the maximum integer value of k for which the Master Theorem yields T (n) = Θ (n^{3}) ?

Question 5

Level 1: Warm-up

Consider the recurrence defined by: f (1) = 1 f (2 n) = 2 f (n) f (2 n + 1) = 2 f (n) + 1 Assertion (A): The value of f (7) is 7. Reason (R): f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7 .

Question 6

Level 1: Warm-up

Let A (x) = \frac{1}{1 - x} be the generating function for the sequence a_{n} = 1 . We form a new generating function B (x) = x^{3} A (x) . What is the minimum number of leading zero coefficients in the sequence corresponding to B (x) ?

Question 7

Level 1: Warm-up

Consider the recurrence relation for Binary Search: T (n) = T (n /2) + Θ (1) . Which of the following bounds is TRUE for the solution of this recurrence?

Question 8

Level 1: Warm-up

A generating function packs the sequence a_{n} into A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} . If the sequence is defined by a_{n} = 2^{n}, what is the value of the coefficient of x^{3} in A (x) ?

Question 9

Level 1: Warm-up

Which of the following recurrence relations is a linear homogeneous recurrence with constant coefficients?

Question 10

Level 1: Warm-up

For the Merge Sort algorithm, the recurrence relation is T (n) = 2 T (n /2) + Θ (n) . What is the minimum depth of the recursion tree when the input size is n = 32 ?

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Recurrences and Generating Functions Short Notes for GATE CS

Recurrences and Generating Functions short notes for GATE CS: 7 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Summary: The Generating Function Cheat Sheet

Quick Reference

Core Transforms

{1} ⟹ \frac{1}{1 - x}

{n + 1} ⟹ \frac{1}{( 1 - x ) ^{2}}

{r^{n}} ⟹ \frac{1}{1 - r x}

Key Operations

x A (x) ⟹

Shift right by 1

A (x) B (x) ⟹

Convolution

Extraction Rule

\frac{1}{( 1 - x ) ^{k}} ⟹ (k - 1 n + k - 1)

Mindset

Treat as Formal Power Series. Ignore convergence. Check boundary terms.

The Characteristic Equation

Summary

If a homogeneous recurrence is written with all terms on one side as

A_{0} a_{n} + A_{1} a_{n - 1} + A_{2} a_{n - 2} + \dots + A_{k} a_{n - k} = 0,

with $A_{0} \neq = 0$ , then its characteristic equation is

A_{0} r^{k} + A_{1} r^{k - 1} + A_{2} r^{k - 2} + \dots + A_{k} = 0.

For the common normalized form

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k},

move everything to one side:

a_{n} - c_{1} a_{n - 1} - c_{2} a_{n - 2} - \dots - c_{k} a_{n - k} = 0.

Therefore the characteristic equation is

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

The roots of this polynomial are called the characteristic roots.

The Master Theorem

For $T (n) = a T (n / b) + f (n)$ where $a \geq 1, b > 1$ :

Compute the critical exponent: $E = lo g_{b} a$ . Compare $f (n)$ with $n^{E}$ :

Case 1 (Leaves dominate):

If $f (n) = O (n^{E - ϵ})$ for some constant $ϵ > 0$ :

$T (n) = Θ (n^{E})$

Case 2 (Balanced):

If $f (n) = Θ (n^{E})$ :

$T (n) = Θ (n^{E} lo g n)$

Case 3 (Root dominates):

If $f (n) = Ω (n^{E + ϵ})$ for some constant $ϵ > 0$ , and the regularity condition $a \cdot f (n / b) \leq c \cdot f (n)$ holds for some constant $c < 1$ and all sufficiently large $n$ :

$T (n) = Θ (f (n))$

Note: The regularity condition in Case 3 ensures $f (n)$ does not fluctuate wildly as it shrinks.

Exam Pattern: Piecewise Even-Odd Recurrences

Examiners frequently test divide-and-conquer logic using piecewise definitions based on parity.

Standard Form:

Base case: $f (1) = c$
Even rule: $f (2 n) = g (f (n))$
Odd rule: $f (2 n + 1) = h (f (n))$

Why this format?

Checking if a number is even or odd is equivalent to checking its least significant bit in binary. Dividing by 2 is a right-shift in binary. These recurrences are secretly processing the binary representation of $n$ bit-by-bit from right to left.

Strategy:

Compute small values manually.
Write the index $n$ in binary next to $f (n)$ .
Look for a mapping between the bits and the output.

Recurrences and Generating Functions: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

Consider the recurrence $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ . Which of the following statements about its characteristic equation is TRUE?

A.
The characteristic equation is $r^{2} - 5 r - 6 = 0$ .
B.
The characteristic roots are $2$ and $3$ .
C.
The characteristic equation is $r^{2} + 5 r + 6 = 0$ .
D.
The characteristic roots are $- 2$ and $- 3$ .

Correct Answer:

Step-by-Step Solution

Key idea: For a recurrence $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}$ , the characteristic equation is $r^{2} - c_{1} r - c_{2} = 0$ .

Step 1: Identify coefficients from $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ . Here $c_{1} = 5$ and $c_{2} = - 6$ .

Step 2: Form the characteristic equation: $r^{2} - 5 r - (- 6) = 0 ⟹ r^{2} - 5 r + 6 = 0$ .

Step 3: Solve the quadratic equation. Factor it: $(r - 2) (r - 3) = 0$ .

Step 4: The roots are $r = 2$ and $r = 3$ .

Answer: The characteristic roots are 2 and 3.

Question 2 · Engineering Mathematics MCQ

The generating function for a sequence is $A (x) = \frac{1}{1 - 3 x}$ . What is the maximum value of $n$ for which the coefficient of $x^{n}$ is strictly less than 100?

A.
3
B.
5
C.
4
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: The generating function $\frac{1}{1 - r x}$ corresponds to the geometric sequence $a_{n} = r^{n}$ . Here, $r = 3$ , so $a_{n} = 3^{n}$ .

Step 1: Identify the sequence formula. $A (x) = \frac{1}{1 - 3 x} ⟹ a_{n} = 3^{n}$ .

Step 2: We need the maximum $n$ such that $3^{n} < 100$ .

Step 3: Test powers of 3:

$3^{1} = 3$

$3^{2} = 9$

$3^{3} = 27$

$3^{4} = 81$

$3^{5} = 243$

Step 4: Since $3^{4} = 81 < 100$ and $3^{5} = 243 > 100$ , the maximum $n$ is 4.

Answer: 4

Question 3 · Engineering Mathematics MCQ

Assertion (A): The general solution to the recurrence $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$ is $a_{n} = α_{1} 3^{n} + α_{2} 1$ .

Reason (R): The characteristic roots of the recurrence are $3$ and $1$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is false but R is true.
D.
A is true but R is false.

Correct Answer:

Step-by-Step Solution

Key idea: For distinct characteristic roots $r_{1}, r_{2}$ , the general solution is $a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n}$ . Both roots must be raised to the power $n$ .

Step 1: Evaluate Reason (R). The recurrence is $a_{n} - 4 a_{n - 1} + 3 a_{n - 2} = 0$ .

Step 2: Characteristic equation: $r^{2} - 4 r + 3 = 0 ⟹ (r - 3) (r - 1) = 0$ . Roots are 3 and 1. So R is TRUE.

Step 3: Evaluate Assertion (A). The general solution must be $a_{n} = α_{1} 3^{n} + α_{2} 1^{n}$ .

Step 4: The assertion writes the second term as $α_{2} 1$ , omitting the exponent $n$ . This is mathematically incorrect for a sequence solution. So A is FALSE.

Answer: A is false but R is true.

Question 4 · Engineering Mathematics MCQ

For the divide-and-conquer recurrence $T (n) = 8 T (n /2) + n^{k}$ , what is the maximum integer value of $k$ for which the Master Theorem yields $T (n) = Θ (n^{3})$ ?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: The Master Theorem compares $f (n)$ against $n^{E}$ where $E = lo g_{b} a$ . Case 1 applies when $f (n)$ grows strictly slower than $n^{E}$ .

Step 1: Identify parameters from $T (n) = 8 T (n /2) + n^{k}$ . Here $a = 8$ , $b = 2$ , and $f (n) = n^{k}$ .

Step 2: Compute the critical exponent $E = lo g_{2} 8 = 3$ .

Step 3: We want $T (n) = Θ (n^{3}) = Θ (n^{E})$ . This corresponds to Case 1 (Leaves dominate).

Step 4: Case 1 requires $f (n) = O (n^{E - ϵ})$ for some $ϵ > 0$ . This means $n^{k}$ must grow strictly slower than $n^{3}$ , so $k < 3$ .

Step 5: The maximum integer value of $k$ strictly less than 3 is 2.

Answer: 2

Question 5 · Engineering Mathematics MCQ

Consider the recurrence defined by:

$f (1) = 1$

$f (2 n) = 2 f (n)$

$f (2 n + 1) = 2 f (n) + 1$

Assertion (A): The value of $f (7)$ is 7.

Reason (R): $f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: To evaluate piecewise even-odd recurrences, apply the correct rule based on the parity of the index, working down to the base case.

Step 1: Evaluate Assertion (A) by computing $f (7)$ .

Since 7 is odd, use $f (2 n + 1) = 2 f (n) + 1$ with $2 n + 1 = 7 ⟹ n = 3$ .

$f (7) = 2 f (3) + 1$ .

Step 2: Compute $f (3)$ . Since 3 is odd, use the odd rule with $2 n + 1 = 3 ⟹ n = 1$ .

$f (3) = 2 f (1) + 1 = 2 (1) + 1 = 3$ .

Step 3: Substitute back into $f (7)$ .

$f (7) = 2 (3) + 1 = 7$ . Assertion (A) is TRUE.

Step 4: Evaluate Reason (R).

R states: $f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7$ .

This matches our exact derivation step-by-step. Reason (R) is TRUE and correctly explains (A).

Answer: Both A and R are true and R is the correct explanation of A.

Question 6 · Engineering Mathematics MCQ

Let $A (x) = \frac{1}{1 - x}$ be the generating function for the sequence $a_{n} = 1$ . We form a new generating function $B (x) = x^{3} A (x)$ . What is the minimum number of leading zero coefficients in the sequence corresponding to $B (x)$ ?

A.
3
B.
2
C.
4
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: Multiplying a generating function by $x^{k}$ shifts the entire sequence to the right by $k$ positions, inserting $k$ zeros at the beginning.

Step 1: Identify the shift operation. $B (x) = x^{3} A (x)$ means the sequence is shifted right by 3.

Step 2: The original sequence is $1, 1, 1, 1, \dots$ (starting at $n = 0$ ).

Step 3: Shifting right by 3 inserts three zeros at indices $n = 0, 1, 2$ .

Step 4: The new sequence is $0, 0, 0, 1, 1, \dots$ .

Step 5: The number of leading zero coefficients is exactly 3.

Answer: 3

Question 7 · Engineering Mathematics MCQ

Consider the recurrence relation for Binary Search: $T (n) = T (n /2) + Θ (1)$ . Which of the following bounds is TRUE for the solution of this recurrence?

A.
$T (n) = Θ (n)$
B.
$T (n) = Θ (lo g n)$
C.
$T (n) = Θ (n lo g n)$
D.
$T (n) = Θ (1)$

Correct Answer:

Step-by-Step Solution

Key idea: The Master Theorem solves $T (n) = a T (n / b) + f (n)$ by comparing $f (n)$ to $n^{E}$ where $E = lo g_{b} a$ .

Step 1: Identify parameters from $T (n) = T (n /2) + Θ (1)$ . Here $a = 1$ , $b = 2$ , and $f (n) = Θ (1)$ .

Step 2: Compute the critical exponent $E = lo g_{2} 1 = 0$ .

Step 3: Compare $f (n)$ with $n^{E}$ . We have $f (n) = Θ (1)$ and $n^{E} = n^{0} = 1$ .

Step 4: Since $f (n) = Θ (n^{E})$ , this falls under Case 2 of the Master Theorem.

Step 5: Case 2 yields $T (n) = Θ (n^{E} lo g n) = Θ (1 \cdot lo g n) = Θ (lo g n)$ .

Answer: $T (n) = Θ (lo g n)$

Question 8 · Engineering Mathematics MCQ

A generating function packs the sequence $a_{n}$ into $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ . If the sequence is defined by $a_{n} = 2^{n}$ , what is the value of the coefficient of $x^{3}$ in $A (x)$ ?

A.
8
B.
6
C.
9
D.
16

Correct Answer:

Step-by-Step Solution

Key idea: The coefficient of $x^{n}$ in the generating function $A (x)$ is exactly the $n$ -th term of the sequence $a_{n}$ .

Step 1: Identify the sequence formula from the problem statement, which is $a_{n} = 2^{n}$ .

Step 2: We need the coefficient of $x^{3}$ , which corresponds to the index $n = 3$ .

Step 3: Substitute $n = 3$ into the sequence formula: $a_{3} = 2^{3} = 8$ .

Answer: 8

Question 9 · Engineering Mathematics MCQ

Which of the following recurrence relations is a linear homogeneous recurrence with constant coefficients?

A.
$a_{n} = 3 a_{n - 1} + 2$
B.
$a_{n} = n a_{n - 1} - a_{n - 2}$
C.
$a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$
D.
$a_{n} = a_{n - 1}^{2} + 2 a_{n - 2}$

Correct Answer:

Step-by-Step Solution

Key idea: A linear homogeneous recurrence with constant coefficients must have previous terms multiplied only by fixed constants, with no standalone terms and no non-linear operations.

Step 1: Check option A: $a_{n} = 3 a_{n - 1} + 2$ . The "+ 2" makes it non-homogeneous.

Step 2: Check option B: $a_{n} = n a_{n - 1} - a_{n - 2}$ . The multiplier " $n$ " means it does not have constant coefficients.

Step 3: Check option C: $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$ . The terms are linear, coefficients (4 and -3) are constant, and there is no standalone term. This fits all criteria.

Step 4: Check option D: $a_{n} = a_{n - 1}^{2} + 2 a_{n - 2}$ . The squared term makes it non-linear.

Answer: $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$

Question 10 · Engineering Mathematics MCQ

For the Merge Sort algorithm, the recurrence relation is $T (n) = 2 T (n /2) + Θ (n)$ . What is the minimum depth of the recursion tree when the input size is $n = 32$ ?

A.
4
B.
5
C.
16
D.
32

Correct Answer:

Step-by-Step Solution

Key idea: In a divide-and-conquer recurrence $T (n) = a T (n / b)$ , the problem size is divided by $b$ at each level. The depth of the recursion tree is the number of times you can divide $n$ by $b$ until you reach the base case (size 1).

Step 1: Identify the division factor $b$ from the recurrence. Here, $b = 2$ .

Step 2: The depth $d$ satisfies $n / b^{d} = 1$ , which means $b^{d} = n$ .

Step 3: Substitute $n = 32$ and $b = 2$ : $2^{d} = 32$ .

Step 4: Solve for $d$ : $d = lo g_{2} 32 = 5$ .

Answer: 5

recurrences and generating functions short notes

Summary: The Generating Function Cheat Sheet

Quick Reference

The Characteristic Equation

The Characteristic Equation

The Master Theorem

The Master Theorem

Try a question

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Recurrences and Generating Functions Short Notes for GATE CS

Summary: The Generating Function Cheat Sheet

Quick Reference

The Characteristic Equation

The Characteristic Equation

The Master Theorem

The Master Theorem

Exam Pattern: Piecewise Even-Odd Recurrences

Exam Pattern: Piecewise Even-Odd Recurrences

Recurrences and Generating Functions: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit