Overview

A recurrence relation defines a sequence using earlier terms.

In counting problems, recurrences are useful when a large object can be built from smaller objects.

For example, the Fibonacci numbers satisfy

Fn=Fn−1+Fn−2.F_n=F_{n-1}+F_{n-2}.

This type of recurrence appears naturally in tiling problems, stair climbing problems, and arrangements with restrictions.

The key idea is:

Count the final object by looking at how it could have ended.

Motivation

Suppose we want to tile a board of length nn using:

  • Squares of length 11,
  • Dominoes of length 22.

Let

TnT_n

be the number of ways to tile a board of length nn.

Look at the last tile.

If the last tile is a square, then the first n−1n-1 positions can be tiled in

Tn−1T_{n-1}

ways.

If the last tile is a domino, then the first n−2n-2 positions can be tiled in

Tn−2T_{n-2}

ways.

Therefore,

Tn=Tn−1+Tn−2.T_n=T_{n-1}+T_{n-2}.

This is the Fibonacci recurrence.

Base Cases

A recurrence is incomplete without base cases.

For the tiling example:

T0=1T_0=1

and

T1=1.T_1=1.

The value

T0=1T_0=1

means there is exactly one way to tile an empty board, use no tiles.

This convention often makes recurrence formulas work cleanly.

Using

Tn=Tn−1+Tn−2,T_n=T_{n-1}+T_{n-2},

we get

T2=2,T_2=2,
T3=3,T_3=3,
T4=5,T_4=5,

and so on.

Building a Recurrence

To build a recurrence, ask:

  1. What quantity should the sequence count?
  2. What is the last step or final piece?
  3. What smaller problem remains after removing it?
  4. What are the base cases?

The hardest part is choosing the right cases so that they do not overlap and do not miss anything.

Tiling With Squares and Dominoes

Example 1

How many ways are there to tile a 1×71\times 7 board using 1×11\times 1 squares and 1×21\times 2 dominoes?

Let

TnT_n

be the number of tilings of a 1×n1\times n board.

As above,

Tn=Tn−1+Tn−2.T_n=T_{n-1}+T_{n-2}.

The base cases are

T0=1,T1=1.T_0=1, \qquad T_1=1.

Now compute:

T2=2,T_2=2,
T3=3,T_3=3,
T4=5,T_4=5,
T5=8,T_5=8,
T6=13,T_6=13,
T7=21.T_7=21.

So there are

2121

tilings.

Stair-Climbing Problems

Recurrences also appear in stair problems.

Suppose a person can climb either 11 step or 22 steps at a time.

Let

SnS_n

be the number of ways to climb nn steps.

The final move is either:

  • A 11-step move from step n−1n-1
  • A 22-step move from step n−2n-2

So

Sn=Sn−1+Sn−2.S_n=S_{n-1}+S_{n-2}.

Again, the Fibonacci recurrence appears.

Tiling With More Tile Sizes

If more tile sizes are allowed, the recurrence changes.

Example 2

How many ways are there to tile a 1×n1\times n board using tiles of lengths 11, 22, and 33?

Let

TnT_n

be the number of tilings.

The last tile can have length 11, 22, or 33.

Therefore,

Tn=Tn−1+Tn−2+Tn−3.T_n=T_{n-1}+T_{n-2}+T_{n-3}.

The base cases are

T0=1,T_0=1,
T1=1,T_1=1,

and

T2=2.T_2=2.

Avoiding Consecutive Objects

Recurrences can count arrangements with restrictions.

Example 3

How many binary strings of length nn have no two consecutive 11's?

Let

AnA_n

be the number of valid strings of length nn.

Look at the end of the string.

If the string ends in 00, then the first n−1n-1 digits can be any valid string. This gives

An−1A_{n-1}

strings.

If the string ends in 11, then the previous digit must be 00. So the string ends in

01.01.

The first n−2n-2 digits can be any valid string. This gives

An−2A_{n-2}

strings.

Therefore,

An=An−1+An−2.A_n=A_{n-1}+A_{n-2}.

The base cases are

A1=2A_1=2

and

A2=3.A_2=3.

Recurrences With Several States

Sometimes one sequence is not enough.

If a problem has different ending types, it may be useful to define multiple states.

Example 4

How many length-nn strings made from AA and BB have no three consecutive AA's?

Let

xnx_n

be the number of valid strings of length nn ending in BB.

Let

yny_n

be the number ending in exactly one AA.

Let

znz_n

be the number ending in exactly two consecutive AA's.

Then

xn+1=xn+yn+zn,x_{n+1}=x_n+y_n+z_n,

because we may add BB to any valid string.

Also,

yn+1=xn,y_{n+1}=x_n,

because to end in exactly one AA, the previous character must be BB.

Finally,

zn+1=yn,z_{n+1}=y_n,

because to end in exactly two consecutive AA's, the previous string must have ended in exactly one AA.

The total number of valid strings is

xn+yn+zn.x_n+y_n+z_n.

This state method is often cleaner than trying to force one recurrence too early.

Solving Simple Linear Recurrences

Some recurrences can be solved exactly.

For example,

Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}

has a closed form, but in most contest counting problems we only need to compute terms up to a certain value.

For recurrences like

an=2an−1,a_n=2a_{n-1},

the solution is exponential.

If

a0=1,a_0=1,

then

an=2n.a_n=2^n.

If

an=an−1+3a_n=a_{n-1}+3

with

a0=2,a_0=2,

then

an=2+3n.a_n=2+3n.

The form of the recurrence reflects the growth of the counting process.

Worked Examples

Example 5

A rabbit can jump either 11, 22, or 33 spaces at a time. How many ways can it reach space 66?

Let

RnR_n

be the number of ways to reach space nn.

The last jump could have size 11, 22, or 33, so

Rn=Rn−1+Rn−2+Rn−3.R_n=R_{n-1}+R_{n-2}+R_{n-3}.

Use base cases:

R0=1,R1=1,R2=2.R_0=1, \qquad R_1=1, \qquad R_2=2.

Then

R3=R2+R1+R0=4,R_3=R_2+R_1+R_0=4,
R4=R3+R2+R1=7,R_4=R_3+R_2+R_1=7,
R5=R4+R3+R2=13,R_5=R_4+R_3+R_2=13,
R6=R5+R4+R3=24.R_6=R_5+R_4+R_3=24.

So there are

2424

ways.

Example 6

How many ways are there to tile a 1×81\times 8 board using only dominoes of length 22 and trominoes of length 33?

Let

TnT_n

be the number of tilings of length nn.

The last tile has length 22 or 33, so

Tn=Tn−2+Tn−3.T_n=T_{n-2}+T_{n-3}.

We use

T0=1,T_0=1,
T1=0,T_1=0,

and

T2=1.T_2=1.

Then

T3=1,T_3=1,
T4=T2+T1=1,T_4=T_2+T_1=1,
T5=T3+T2=2,T_5=T_3+T_2=2,
T6=T4+T3=2,T_6=T_4+T_3=2,
T7=T5+T4=3,T_7=T_5+T_4=3,
T8=T6+T5=4.T_8=T_6+T_5=4.

So there are

44

tilings.

Key Contest Insight

Recurrence problems are usually solved by looking at the last step.

If the final choice leaves a smaller version of the same problem, a recurrence is likely useful.

The most important part is choosing cases that are:

  • Complete
  • Non-overlapping
  • Easy to translate into smaller subproblems

Strategy Tips

  • Define the sequence clearly
  • Decide what ana_n counts
  • Look at the last tile, last step, or last symbol
  • Write the recurrence from smaller cases
  • Choose base cases carefully
  • Use a0=1a_0=1 when counting empty constructions
  • If one sequence is not enough, introduce multiple states
  • Compute terms patiently and check small cases

Common Pitfalls

  • Forgetting base cases
  • Using the wrong value for the empty case
  • Double-counting overlapping cases
  • Missing a possible final step
  • Defining ana_n vaguely
  • Trying to solve a recurrence before setting it up correctly

Practice Problems

StatusSourceProblem NameDifficultyTags

Module Progress:

Join the Discord Community!

Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.