Today we finish Section 4.6 on linear recurrence relations. I'll also use the remaining time for some review.
Friday will be entirely review. Bring questions!
Work through suggested exercises. There are additional practice problems on WeBWorK and on the suggested exercises page.
Homework 11 is on Gradescope and is due Friday.
Math Help Centre: M-F 12:30-5:30 in PAB48/49 and online 6pm-8pm.
My next office hour is Friday 2:30-3:20 in MC130.
Next week: Monday, 4-5; Tuesday, 2-3; Wednesday, 1:30-2:30. All in MC130.
Review sessions next week: TBA.
Final exam: Friday, December 13, 9am to noon.
Section 002 (this section) and Section 003: AH 201 (gym/stage).
Section 001 A-SHEI AH 15; SHEN-Z AH 201 (gym/stage).
Please do the course evaluations for this course!
(1) $x_0 = a_0$, $x_1 = a_1$, $\ldots$, $x_{k-1} = a_{k-1}$, for scalars $a_0, \ldots, a_{k-1}$.
(2) For $n \geq k$, $x_n = c_1 x_{n-1} + c_2 x_{n-2} + \cdots + c_k x_{n-k}\strut$,
where $c_1, \ldots, c_k$ are scalars with $c_k \neq 0$.
The equations in (1) are called the initial conditions.
(a) If $\lambda_1 \neq \lambda_2$, then $x_n = d_1 \lambda_1^n + d_2 \lambda_2^n$
for some scalars $d_1$ and $d_2$.
(b) If $\lambda_1 = \lambda_2$, then $x_n = d_1 \lambda_1^n + d_2 \red{n} \lambda_1^n$
for some scalars $d_1$ and $d_2$.
In either case, $d_1$ and $d_2$ can be determined using the initial conditions.
Example 4.41: The Fibonacci numbers are defined by $f_0 = 0$, $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for $n \geq 2$. So the sequence goes $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $\ldots$
The recurrence has the form $f_n - f_{n-1} - f_{n-2} = 0$, so we should look at the roots of $\lambda^2 - \lambda - 1 = 0$. By the quadratic formula, these are $$ \kern-8ex \frac{-(-1) \pm \sqrt{(-1)^2 - 4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2} $$ So we must have $$ \kern-8ex f_n = d_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + d_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n $$ for some coefficents $d_1$ and $d_2$. The initial conditions tell us: $$ \kern-8ex 0 = f_0 = d_1 \left(\frac{1 + \sqrt{5}}{2}\right)^0 + d_2 \left(\frac{1 - \sqrt{5}}{2}\right)^0 = d_1 + d_2 $$ and $$ \kern-8ex 1 = f_1 = d_1 \left(\frac{1 + \sqrt{5}}{2}\right) + d_2 \left(\frac{1 - \sqrt{5}}{2}\right) $$ The first tells us that $d_2 = - d_1$, and then the second gives us $$ \kern-8ex 1 = d_1 \left(\frac{1 + \sqrt{5}}{2}\right) - d_1 \left(\frac{1 - \sqrt{5}}{2}\right) = 2 \frac{\sqrt{5}}{2} d_1 = \sqrt{5} d_1 $$ so $d_1 =1/\sqrt{5}$ and $d_2 = -1/\sqrt{5}$. We end up with a remarkable formula for the Fibonacci numbers: $$ \kern-8ex f_n = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2}\right)^n $$
Example 4.42: Solve the recurrence relation $x_0 = 1$, $x_1 = 6$ and $x_n = 6 x_{n-1} - 9 x_{n-2}$ for $n \geq 2$.
Solution: The polynomial $\lambda^2 - 6 \lambda + 9$ factors as $(\lambda - 3)^2$, so by case (b) of Theorem 4.38 we must have $$ x_n = d_1 3^n + d_2 n 3^n . $$ Since $$ 1 = x_0 = d_1 \qtext{and} 6 = x_1 = 3 d_1 + 3 d_2 $$ we must have $d_1 = 1$ and $d_2 = 1$, so $$ x_n = (1 + n) 3^n $$ Here's the theorem again:
(a) If $\lambda_1 \neq \lambda_2$, then $x_n = d_1 \lambda_1^n + d_2 \lambda_2^n$
for some scalars $d_1$ and $d_2$.
(b) If $\lambda_1 = \lambda_2$, then $x_n = d_1 \lambda_1^n + d_2 \red{n} \lambda_1^n$
for some scalars $d_1$ and $d_2$.
In either case, $d_1$ and $d_2$ can be determined using the initial conditions.
Case (b) is proven in the text, but doesn't use diagonalization, so we won't be covering it.
There is also a version of the theorem for recurrence relations of higher degree, but again we won't be covering it.
The exam is cumulative, but will focus on material after the midterm (Sections 3.6, 3.7, 4.1, 4.2, 4.3, 4.4, 4.6). Sections 3.3 and 3.5 are also quite important.
Strategies for True/False questions:
Exercise 1(b) from additional problems list: If $A$ and $B$ are diagonalizable $n \times n$ matrices, then so is $AB$.
Solution: Since random matrices are diagonalizable, it will be tricky to find a counterexample by choosing $A$ and $B$, since you then have no control over the product.
Instead, choose $C$ to be non-diagonalizable, e.g. $C = \bmat{rr} 0 & 2 \\ 0 & 0 \emat$. (If it were diagonalizable, it would be similar to the zero matrix, but only the zero matrix is similar to the zero matrix.)
Now pick a random invertible diagonalizable matrix $B$, say $B = \bmat{rr} 2 & 1 \\ 0 & 1 \emat$. If I want $AB = C$, then I must have $A = CB^{-1}$. I computed $CB^{-1}$ and found by luck that it was diagonalizable. (Most random matrices are.)
Now let's work through other problems on that list.
Friday's class is a review session. Please bring questions for me!
Please do the course evaluations for this course! They are very important and any feedback you have is very much appreciated. Let me know what you liked and what could improve.