MATH 302 Lecture 16
« previous | Monday, October 24, 2011 | next »
Solving Recurrence Relations
Linear Homogeneous Recurrence Relation of Degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} with constant coefficients:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_n = c_1a_{n-1} + c_2a_{n-2} + \dots + c_ka_{n-k}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1, \ldots, c_k} are constants.
We want to describe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_n = \alpha r^n} in terms of a single equation without any recursion.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha r^n = c_1 \alpha r^{n-1} + c_2 \alpha r^{n-2} + \dots + c_k \alpha r^{n-k}}
Bring all terms to the left-hand side
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cancel{\alpha r^{n-k}}(r^k-c_1r^{k-1}-c_2r^{k-2}-\dots-c_k) = 0}
The parenthesized polynomial is called the characteristic equation.
2 Cases for characteristic equation:
- distinct characteristic roots (Theorems 1 & 3)
- nondistinct characteristic roots (Theorems 2 & 4)
How many ways are there to tile a 2 × n surface area with two types of tiles: 2 × 2 and 2 × 1 . . .
Take a non-homogeneous recurrence relation. Dropping anything that has nothing to do with recursion results in the associated homogeneous equation. Solve this:
- Recurrence Relation: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_n = 2H_{n-1} + 1}
- Assoc. Homog. Eq: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_n = 2H_{n-1}}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r-2 = 0 \rightarrow r=2}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_n = \alpha 2^n} This is the homogeneous form.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_n = C \rightarrow C = 2C + 1 \rightarrow C = -1} This is the particular equation
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} H_n &= \mathrm{homog} + \mathrm{particular} \\ &= \alpha 2^n-1\end{align}}