Probability MT22, Recurrence relations
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?
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 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$?
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$?
@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.