Recurrence relation

You already know one. In an arithmetic progression, each term is the one before plus d. As a recurrence, aₙ = aₙ₋₁ + d. You also need a starting term, a₁, to get going.

The Olympiad syllabus calls this idea recursion. It is a strong counting tool. When a count is hard to find directly, you ask how the answer for n links to the answers for smaller cases.

A small example

You climb a staircase taking 1 or 2 steps at a time. In how many ways can you climb 5 steps? Call the number of ways for n steps W(n).

• Your last move is either 1 step or 2 steps.
• If it was 1 step, you first climbed n - 1 steps. If it was 2, you first climbed n - 2.
• So W(n) = W(n - 1) + W(n - 2).
• W(1) = 1 and W(2) = 2. Then W(3) = 3, W(4) = 5 and W(5) = 8.

Check W(3) by listing: 1+1+1, 1+2 and 2+1. That is 3 ways. The answers 1, 2, 3, 5, 8 are Fibonacci numbers, where each is the sum of the two before.

Where it fits

NCERT's Class 9 book introduces recursive rules for sequences. Using them to count, as above, goes beyond the Class 10 board syllabus. HBCSE's syllabus for the Mathematical Olympiad names it under combinatorics, as recursion. The Mathematics Teachers' Association (India), MTA(I), conducts IOQM, the first stage of the Mathematical Olympiad Programme that HBCSE organises for NBHM.

About the author

Mohit Sardana

Chief Architect

An engineer (B.Tech, Computer Science) with over 20 years of preparing students for entrance exams, including as Dean at FIITJEE and Vice-President at Aakash. He is the chief architect of the TRUpreBoards evaluation engine.

Mohit Sardana on LinkedIn