Lecture - Probability MT22, VIII

Created: November 05, 2022

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?
\[\sum^k_{j = 0} a_j u_{n+k} = 0\]

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

Say you had the recurrence relation $u _ {n+1} = 2u _ n + 2n$. What particular solution would you try?
\[u_n = Cn + D\]

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$?
\[w_n = A\lambda_1^n + B\lambda_2^n\]

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$?
\[w_n = (A + Bn)\lambda^n\]

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.



Related posts