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).

Recurrence Relations

4 Qs · 2016–2024 · 5 marks · 0.2 marks/paperStandard yield

Take topic test

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… Guide

Type

GATE CSE 2024 Set 2Q15MCQ1 markEasyLet $T(n)$ be the recurrence relation defined as follows: $T(0) = 1,$ $T(1) = 2, \text{ and}$ $T(n) = 5T(n - 1) - 6T(n - 2) \quad \text{for } n \ge 2$ Which one of the following statements is TRUE?
GATE CSE 2023Q15MCQ1 markEasyThe Lucas sequence $L_n$ is defined by the recurrence relation: $L_n = L_{n-1} + L_{n-2}, \quad \text{for } n \ge 3,$ with $L_1 = 1$ and $L_2 = 3$ . Which one of the options given is TRUE?
GATE CSE 2022Q51MSQ2 marksMediumConsider the following recurrence: $f(1) = 1;$ $f(2n) = 2 f(n) - 1, \quad \text{for } n \ge 1;$ $f(2n+1) = 2 f(n) + 1, \quad \text{for } n \ge 1.$ Then, which of the following statements is/are TRUE?
GATE CSE 2016 Set 1Q2MCQ1 markEasyLet $a_n$ be the number of $n$ -bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$ ?

Topic guide

What does GATE test in Recurrence Relations?

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
occasional · MCQ · 1 marks · 2016
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
occasional · MCQ · 1 marks · 2023
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
occasional · MCQ · 1 marks · 2024
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
rare · MSQ · 2 marks · 2022
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.