# Lecture - Probability MT22, VIII

### 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 homogenous equation
- $v _ n$, a particular solution to the equation

## \[\sum^k _ {j = 0} a _ j u _ {n+k} = f(n)\]
What is the form of the homogenous equation for this recurrence relation?

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

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

What’s the solution to the homogenous equation $aw _ {n+2} + bw _ {n+1} + cw _ n = 0$ for **distinct roots** of the auxillary equation $a\lambda^2 + b\lambda + c = 0$?

**distinct roots**of the auxillary equation $a\lambda^2 + b\lambda + c = 0$?

What’s the solution to the homogenous equation $aw _ {n+2} + bw _ {n+1} + cw _ n = 0$ for **repeated roots** of the auxillary equation $a\lambda^2 + b\lambda + c = 0$?

**repeated roots**of the auxillary equation $a\lambda^2 + b\lambda + c = 0$?

Why can you use the auxillary equation $a\lambda^2 + b\lambda + c = 0$ to solve a homogenous recurrence relation like $aw _ {n+2} + bw _ {n+1} + cw _ n = 0$?

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