# Notes - Probability MT22, Recurrence relations

> Source: https://ollybritton.com/notes/uni/prelims/mt22/probability/notes/recurrence-relations/ · Updated: 2025-10-21 · Tags: uni, notes

- [Course - Probability](https://ollybritton.com/notes/uni/prelims/mt22/probability/)

### Flashcards
Given a recurrence relation $u_n$, what two things do you need to add together to get the general solution?::

- $w_n$, the solution to the homogeneous equation
- $v_n$, a particular solution to the equation

$$\sum^k_{j = 0} a_j u_{n+j} = f(n)$$ What is the form of the homogeneous equation for this recurrence relation?::

$$
\sum^k_{j = 0} a_j u_{n+j} = 0
$$

Say you had the recurrence relation $u_{n+1} = 2u_n + 1$. What particular solution would you try?::

$$
u_n = C
$$

@example~

Say you had the recurrence relation $u_{n+1} = 2u_n + 2n$. What particular solution would you try?::

$$
u_n = Cn + D
$$

@example~

What’s the solution to the homogeneous equation $aw_{n+2} + bw_{n+1} + cw_n = 0$ for **distinct roots** of the auxiliary equation $a\lambda^2 + b\lambda + c = 0$?::

$$
w_n = A\lambda_1^n + B\lambda_2^n
$$

What’s the solution to the homogeneous equation $aw_{n+2} + bw_{n+1} + cw_n = 0$ for **repeated roots** of the auxiliary equation $a\lambda^2 + b\lambda + c = 0$?::

$$
w_n = (A + Bn)\lambda^n
$$

@Justify why you can use the auxiliary equation $a\lambda^2 + b\lambda + c = 0$ to solve a homogeneous recurrence relation like $aw_{n+2} + bw_{n+1} + cw_n = 0$.::

You guess that $w_n = \lambda^n$ and then factorise.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt