RMO recurrence relations for combinatorics

October 13, 2025

Theory:
1. First order linear non-homogeneous:
An = f(n).A_(n-1) + g(n)

Solution approach: Divide each term by f(1).f(2)....f(n) and convert it to Bn = B_(n-1) + g'(n) then telescope.

2. First order linear homogeneous:
An = f(n).A_(n-1)

Solution approach: A2/A1 * A3/A2 * A4/A3 ... = f(2).f(3)...

2a. An = k.A_(n-1) (G.P. solution)

3. Second order homogeneous with constant coefficients:
An = k.A_(n-1) + m.A_(n-2)

Two ways to solve this.
3a.
Try to make it Bn = (some constant) * B_(n-1)
Where Bn = An - p.A_(n-1)
To do that do this:
An - p.A_(n-1) = k.A_(n-1) + m.A_(n-2) - p.A_(n-1)
And then by equating coefficients find the value of p.
Now it's a G.P. in Bn. Solve for Bn and then equate that to An - p.A_(n-1).
Now it's a first order linear recurrence. Solve it.

3b. Second method:
Let An = X^n. This will give you a quadratic characteristic equation.
Solve to get roots a,b.
An = p.(a^n) + q.(b^n)
Now find values of p,q by using initial conditions for A0,A1 etc.

Examples: