Students often put two different recurrence tools into the same mental box. The Master Theorem handles divide-and-conquer running times such as T(n)=aT(n/b)+f(n). Characteristic roots handle linear recurrences such as a(n)=5a(n-1)-6a(n-2).
The characteristic-root method turns a(n)=5a(n-1)-6a(n-2) into the quadratic x^2-5x+6=0 and reads the answer straight off its roots. Generating functions pack the whole sequence into a single rational function and recover the same answer by partial fractions. Both routes land on a(n)=3^n-2^n, and the agreement is not a coincidence.
Linear recurrences with constant coefficients
A linear recurrence with constant coefficients has the general shape:
a(n)=c1a(n-1)+c2a(n-2)+...+cka(n-k)+f(n)
The coefficients c1 through ck are constants. If f(n)=0, the recurrence is homogeneous. If f(n) is nonzero, it is non-homogeneous.
The characteristic-root method first solves the homogeneous part. For a non-homogeneous recurrence, we then find one particular solution matching the form of f(n) and add it to the homogeneous solution.
This is not the Master Theorem for GATE. That theorem applies when the recurrence shrinks the input, usually from n to n/b, and models recursive work. If the recurrence moves through consecutive indices n-1, n-2, and so on with constant coefficients, think characteristic equation.
The characteristic-root method
For a second-order homogeneous recurrence
a(n)=c1a(n-1)+c2a(n-2),
try a solution of the form a(n)=x^n. Substitution gives:
x^n=c1x^(n-1)+c2x^(n-2).
Divide by x^(n-2) to obtain the characteristic equation:
x^2-c1x-c2=0.
The root pattern determines the form of the solution:
Root case | General solution |
|---|---|
Distinct real roots r1 and r2 | a(n)=A(r1^n)+B(r2^n) |
Repeated root r | a(n)=(A+Bn)r^n |
Complex roots in polar form R(cos theta ± i sin theta) | a(n)=R^n[A cos(n theta)+B sin(n theta)] |
Initial conditions determine A and B. A second-order recurrence normally needs two initial values because two constants must be fixed.
Worked example by characteristic roots
Solve:
a(n)=5a(n-1)-6a(n-2), with a(0)=0 and a(1)=1.
Move every recurrence coefficient into the characteristic equation carefully:
x^2-5x+6=0
(x-2)(x-3)=0.
The roots are 2 and 3, which are distinct. Therefore:
a(n)=A(2^n)+B(3^n).
Apply a(0)=0:
A(2^0)+B(3^0)=0
A+B=0.
Apply a(1)=1:
2A+3B=1.
From A+B=0, A=-B. Substitute into the second equation:
2(-B)+3B=1
B=1, so A=-1.
The closed form is:
a(n)=3^n-2^n.
Check the first two generated values against the recurrence. For n=2, the formula gives 3^2-2^2=9-4=5. The recurrence gives 5a(1)-6a(0)=5(1)-6(0)=5. For n=3, the formula gives 27-8=19. The recurrence gives 5a(2)-6a(1)=5(5)-6(1)=25-6=19. Both checks agree.
Extending that check gives a short table you can rebuild in the margin of a question paper:
n | From the recurrence | From 3^n-2^n |
|---|---|---|
0 | 0 (given) | 1-1=0 |
1 | 1 (given) | 3-2=1 |
2 | 5(1)-6(0)=5 | 9-4=5 |
3 | 5(5)-6(1)=19 | 27-8=19 |
4 | 5(19)-6(5)=65 | 81-16=65 |
5 | 5(65)-6(19)=211 | 243-32=211 |
Repeated roots: a worked example
The repeated-root rule is the one candidates most often misapply under time pressure, so it is worth working once. Solve:
a(n)=4a(n-1)-4a(n-2), with a(0)=1 and a(1)=6.
The characteristic equation is
x^2-4x+4=0
(x-2)^2=0.
The root 2 appears twice, so the general solution is a(n)=(A+Bn)2^n. Writing A(2^n)+B(2^n) instead collapses to a single constant and can never satisfy two independent initial conditions.
Apply a(0)=1: A=1. Apply a(1)=6: (A+B)(2)=6, so 1+B=3 and B=2.
a(n)=(1+2n)2^n.
Check n=2: the formula gives (1+4)(4)=20, and the recurrence gives 4a(1)-4a(0)=24-4=20. Check n=3: the formula gives (1+6)(8)=56, and the recurrence gives 4(20)-4(6)=80-24=56.
The same recurrence by generating functions
Define the ordinary generating function:
G(x)=sum from n=0 to infinity of a(n)x^n.
The recurrence is valid for n>=2. Multiply it by x^n and sum over n>=2. The left side is G(x)-a(0)-a(1)x. The first shifted sum on the right is 5x[G(x)-a(0)], and the second is -6x^2G(x). Thus:
G(x)-a(1)x-a(0)=5x[G(x)-a(0)]-6x^2G(x).
Insert a(0)=0 and a(1)=1:
G(x)-x=5xG(x)-6x^2G(x).
Collect the G(x) terms:
G(x)(1-5x+6x^2)=x,
so
G(x)=x/[(1-2x)(1-3x)].
Now use partial fractions:
G(x)=-1/(1-2x)+1/(1-3x).
Because 1/(1-rx) generates the coefficients r^n, the coefficient of x^n in G(x) is:
-2^n+3^n=3^n-2^n.
The result matches the characteristic-root solution exactly. This agreement is also an error check. If the generating-function numerator or partial fractions produce a different initial coefficient, revisit the index shift before proceeding.
The two routes agree because the denominator is the characteristic polynomial with its coefficients reversed. Reverse 1, -5, 6 in x^2-5x+6 and you get 6x^2-5x+1, which is the 1-5x+6x^2 that collected out of the sum. Its factors (1-2x)(1-3x) therefore carry 1/2 and 1/3, the reciprocals of the roots 2 and 3. Each factor 1/(1-rx) expands into a geometric series whose coefficients are r^n, which is precisely the A(r^n) term the characteristic method writes down. Partial fractions then supply the constants that initial conditions supply on the other route.
A non-homogeneous recurrence: a(n)=2a(n-1)+1
Solve a(n)=2a(n-1)+1 with a(0)=0.
The homogeneous equation a(n)=2a(n-1) gives a_h(n)=A2^n. For a particular solution, try a constant p. Substitute it into the full recurrence:
p=2p+1, so p=-1.
Combine the two parts:
a(n)=A2^n-1.
Use a(0)=0:
A-1=0, so A=1.
Therefore a(n)=2^n-1. A direct check gives a(1)=1 and 2a(0)+1=1; a(2)=3 and 2a(1)+1=3.
The trial form must not duplicate a homogeneous solution. If it clashes with a characteristic root, multiply the trial by n enough times to make it independent.
Traps that break the solution
Using the wrong theorem. Consecutive-index linear recurrences use characteristic roots. Divide-and-conquer recurrences may use the Master Theorem.
Repeating the same root term. A repeated root r gives (A+Bn)r^n, not Ar^n+Br^n.
Losing a sign. For a(n)=c1a(n-1)+c2a(n-2), the equation is x^2-c1x-c2=0. If c2 itself is negative, subtracting it creates a plus.
Shifting a generating function carelessly. Write the missing initial terms explicitly. They determine the numerator.
Applying the wrong initial indices. Substitute n=0 and n=1 into the general solution exactly as given.
Guessing a clashing particular solution. Multiply the guess by n when its form is already part of the homogeneous answer.
How GATE tests recurrence relations
Questions may ask for a closed form, a particular sequence value, the recurrence corresponding to a stated solution, or a counting model that leads to a recurrence. Binary strings with restrictions are a common bridge between counting and recurrences, so the permutations and combinations method is useful background.
Discrete Mathematics coverage is fixed for each cycle in the brochure on the official GATE portal of the organising IIT. Confirm the current list there instead of assuming an old weightage. Use the GATE preparation category to organise revision around the rest of the syllabus.
For a timed question, write the first three sequence values in the margin before solving. They expose a copied initial condition and give you cheap values for checking the final formula. After finding a closed form, substitute n=0 and n=1, then test one value produced by the recurrence itself. These checks take less time than rebuilding a solution after a sign error.
Short version and next step
For a homogeneous linear recurrence, form the characteristic equation, choose the solution shape from the roots, and fit the constants with the initial values. Generating functions encode the same sequence and provide a second route when shifts or non-homogeneous terms become awkward.
Now re-solve a(n)=5a(n-1)-6a(n-2) without looking at the steps. You should reach a(n)=3^n-2^n by roots and recover the same coefficients from G(x). Continue through the discrete-maths sequence in GATE Guidance by Sanchit Sir. KnowledgeGate's question bank carries about 1,300 Discrete Mathematics questions for turning the method into exam-speed recall.
