What are common examiner traps in Recurrence Relations?

Assuming the highest characteristic root always dictates the asymptotic bound without solving for the coefficient (e.g., in 2024, c2 = 0 for root 3, making the bound (2n) rather than (3n)). Off-by-one errors in base condition indices (n=0, 1 vs n=1, 2) when substituting into general equations. Incorrect suffix decomposition leading to mismatched coefficients in combinatorial setups (e.g., an = an-1 + an-2 vs an = 2an-1 + an-2). Assuming linear behavior f(2n + k) = 2n + k without evaluating specific counterexamples (e.g., f(5) = 3 ≠ 5). Mixing up odd (2n+1) and even (2n) recursive transitions when evaluating composite inputs. Failing to check base cases (n=0 vs n=1) for parametrized options like f(5 · 2n).

GATE CSE Recurrence Relations PYQs

Standard yield1.3% of Engineering Mathematics

In GATE CS, Recurrence Relations under Engineering Mathematics is tested as a concise 1-mark topic focused on linear homogeneous recurrence relations of degree… Read the guide

Take topic test

Questions: 4
Asked: 2016–2024
Total marks: 5
Marks / paper: 0.2

4 GATE CSE Recurrence Relations PYQs with solutions, from Engineering Mathematics. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Recurrence Relations

Concepts, patterns, formulas and traps distilled from past papers.

In GATE CS, Recurrence Relations under Engineering Mathematics is tested as a concise 1-mark topic focused on linear homogeneous recurrence relations of degree 2. Questions either require setting up a recurrence relation from a combinatorial constraint (e.g., restricted binary strings) or solving a second-order linear recurrence relation using characteristic roots to find either an explicit closed-form formula or its asymptotic tight bound $\Theta(\cdot)$ . All provided PYQs are conceptual, analytical 1-mark multiple-choice questions without diagrams.

Core concepts

Linear homogeneous recurrence relations with constant coefficients
Characteristic polynomial and distinct real/irrational roots
Initial conditions and boundary value solving for constants
Combinatorial state-splitting / suffix conditioning (e.g., strings ending in 0 vs 1)
Asymptotic order of growth ( o ) derived from exact solutions
Piecewise / Parity-based recurrence relations
Mathematical induction on recursively defined functions
Binary representation dynamics (Josephus-style bitwise transformations)
Verification of closed-form expressions via small value computation

Recurring question patterns

Combinatorial Recurrence Modeling
OccasionalMCQ1 marks2016
Given a combinatorial counting problem (e.g., binary strings avoiding specific patterns), identify the matching linear recurrence relation by conditioning on suffix/prefix cases.
Characteristic Equation and Closed-Form Solution
OccasionalMCQ1 marks2023
Solve a second-order linear homogeneous recurrence with constant coefficients and specific initial conditions to determine the exact closed-form expression $a_n = c_1 r_1^n + c_2 r_2^n$ .
Asymptotic Growth of Linear Recurrences
OccasionalMCQ1 marks2024
Given a second-order recurrence and base cases, solve for constants to see if higher-order roots are eliminated ( $c_i = 0$ ), then deduce the tight asymptotic complexity $\Theta(r^n)$ .
Parity-Branching Recurrence Evaluation
RareMSQ2 marks2022
A recurrence defined separately for even inputs ( $2n$ ) and odd inputs ( $2n+1$ ) with a base case. Multiple statements present closed-form expressions for structured input sequences (such as $2^n$ , $2^n-1$ , $c \cdot 2^n$ ) to test for correctness.

Formulas GATE uses

Characteristic Equation for 2nd-Order Linear Homogeneous Recurrence

r^2 - c_1 r - c_2 = 0

Used to find the roots of the recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ .

General Solution for Distinct Real/Irrational Roots

a_n = A r_1^n + B r_2^n

Used to express the general solution when characteristic equation has two distinct roots $r_1 e r_2$ .

Base Case System of Linear Equations

\begin{cases} A r_1^{n_0} + B r_2^{n_0} = a_{n_0} \\ A r_1^{n_0+1} + B r_2^{n_0+1} = a_{n_0+1} \end{cases}

Used to solve for constants $A$ and $B$ given initial values.

Even Argument Step

f(2n) = 2f(n) - 1

Used when the argument is an even positive integer.

Odd Argument Step

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

Used when the argument is an odd positive integer.

Power-of-Two Property

f(2^n) = 1

Closed-form deduction for pure powers of 2 under the defined recurrence.

All-Ones Binary Sequence Property

f(2^n - 1) = 2^n - 1

Closed-form identity for inputs of the form $2^n - 1$ .

Examiner traps in Recurrence Relations

Assuming the highest characteristic root always dictates the asymptotic bound without solving for the coefficient (e.g., in 2024, c2 = 0 for root 3, making the bound (2n) rather than (3n)).
Off-by-one errors in base condition indices (n=0, 1 vs n=1, 2) when substituting into general equations.
Incorrect suffix decomposition leading to mismatched coefficients in combinatorial setups (e.g., an = an-1 + an-2 vs an = 2an-1 + an-2).
Assuming linear behavior f(2n + k) = 2n + k without evaluating specific counterexamples (e.g., f(5) = 3 ≠ 5).
Mixing up odd (2n+1) and even (2n) recursive transitions when evaluating composite inputs.
Failing to check base cases (n=0 vs n=1) for parametrized options like f(5 · 2n).

How questions are asked

Identifying the recurrence equation from a combinatorial description
Selecting the closed-form formula satisfying base conditions and recurrence
Determining the asymptotic tight bound (·) of a recurrence
Multi-statement verification of closed forms for recursive definitions
Value computation of recursively defined sequences at specific indices

Paper trends

In earlier exams (2016), the focus was on setting up the recurrence from a counting problem; recent exams (2023, 2024) focus explicitly on solving characteristic equations, finding constants from initial conditions, and evaluating closed forms or asymptotic bounds.
2024, 2023, 2016
All questions have consistently remained 1-mark standard MCQs testing analytical algebra rather than heavy computational arithmetic.
2024, 2023, 2016
Shift towards multi-select questions (MSQ) where multiple closed-form conjectures about a recursively defined sequence must be proved or disproved.
2022

Difficulty notes

All PYQs in this set are Easy 1-mark problems. Easy items involve standard 2nd-degree characteristic polynomials with easy-to-factor integer or golden-ratio roots ( $r^2-r-1=0$ , $r^2-5r+6=0$ ). Medium questions could involve repeated roots ( $a_n = (c_1 + c_2 n)r^n$ ), non-homogeneous terms, or MSQ formats with multiple properties evaluated.