Recurrence Relations: Differences, Solutions, Stability, and Applications

All flashcards

What is a closed-form solution to a recurrence?

A non-recursive expression for a sequence term in terms of its index and initial data.

What is the forward difference of a sequence?

The change between consecutive terms, given by $(\Delta a)_n=a_{n+1}-a_n$.

How are characteristic roots used to solve a constant-coefficient linear recurrence?

They provide building blocks for the solution; initial values determine the constants.

When is a fixed point of $x_n=f(x_{n-1})$ locally stable?

When $f(x^*)=x^*$ and $|f'(x^*)|<1$.

How does Euler's method generate a recurrence?

It updates an approximation by $y_{n+1}=y_n+h f(t_n,y_n)$.

Quiz questions

1. The Fibonacci sequence has $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\geq2$. What is $F_5$?Answer: 5
2. Why is the logistic map $x_{n+1}=r x_n(1-x_n)$ nonlinear in $x_n$?Answer: It includes a product involving $x_n$ and $1-x_n$.
3. For a homogeneous linear recurrence with constant coefficients, when is it asymptotically stable?Answer: When every characteristic root has absolute value less than 1.
4. For $a_n=c_1a_{n-1}+c_2a_{n-2}$, which equation is the characteristic equation?Answer: $\lambda^2-c_1\lambda-c_2=0$
5. Euler's method approximates $y'(t)=f(t,y(t))$ with step size $h$. Which update does it use?Answer: $y_{n+1}=y_n+h f(t_n,y_n)$