Solution Manual of "Elementary Linear Algebra": 2. Matrices (Part-1)

This document is the solution manual of “Elementary Linear Algebra” which was written by K. R. Matthews, University of Queensland.
The free printable PDF format lecture can be Downloaded Here

Summary

• Matrix
  A matrix over a field $F$ is a rectangular array of elements from $F$. The symbol $M_{m\times n}(F)$ denotes the collection of all $m\times n$ matrices over $F$.
  Matrices will usually be denoted by capital letters and the equation $A=[a_{ij}]$ means that the element in the $i$-th row and $j$-th column of the matrix $A$ equals $a_{ij}$.
• Equality of matrices
  Matrices $A$, $B$ are said to be equal if $A$ and $B$ have the same size and corresponding elements are equal; i.e. $A$ and $B$ $\in M_{m\times n}(F)$ and $A=[a_{ij}]$, $B=[b_{ij}]$, with $a_{ij}=b_{ij}$ for $1\leq i\leq m$, $1\leq j\leq n$.
• Addition (subtraction) of matrices
  Let $A=[a_{ij}]$ and $B=[b_{ij}]$ be of the same size. Then $A\pm B$ is the matrix obtained by adding (subtracting) corresponding elements of $A$ and $B$; that is $$A\pm B=[a_{ij}]\pm[b_{ij}]=[a_{ij}\pm b_{ij}].$$
• Scalar multiple of a matrix
  Let $A=[a_{ij}]$ and $t\in F$ ($t$ is a scalar). Then $tA$ is the matrix obtained by multiplying all elements of $A$ by $t$; that is $$tA=t[a_{ij}]=[ta_{ij}].$$
• Additive inverse of a matrix
  Let $A=[a_{ij}]$. Then $-A$ is the matrix obtained by replacing the elements of $A$ by their additive inverses; that is $$-A=-[a_{ij}]=[-a_{ij}].$$
• The zero matrix
  For each $m$, $n$ the matrix in $M_{m\times n}(F)$, all of whose elements are zero, is called the zero matrix (of size $m\times n$) and is denoted by the symbol 0.
• Matrix product
  
  • Definition
    Let $A=[a_{ij}]$ be a matrix of size $m\times n$ and $B=[b_{jk}]$ be a matrix of size $n\times p$; that is the number of columns of $A$ equals the number of rows of $B$. Then $AB$ is the $m\times p$ matrix $C=[c_{ik}]$ whose $(i, k)$-th element is defined by the formula $$c_{ik}=\sum_{j=1}^{n}a_{ij}b_{jk}=a_{i1}b_{1k} +\cdots+a_{in}b_{nk}.$$
  • Basic laws
    $$(AB)C=A(BC)$$ $$t(AB)=(tA)B=A(tB)$$ $$(A+B)C=AC+BC$$ $$D(A+B)=DA+DB$$ where the size of $A$, $B$, $C$, $D$ should satisfy the definition of matrix product, and $t$ is a scalar in the field $F$.
• The identity matrix
  The $n\times n$ matrix $I_n=[\delta_{ij}]$, defined by $\delta_{ij}=1$ if $i=j$, $\delta_{ij}=0$ if $i\neq j$, is called the $n\times n$ identity matrix of order $n$. For example, $I_2=\begin{bmatrix}1&0\\0&1 \end{bmatrix}$.
  If $A$ is $m\times n$, then $I_mA=A=AI_n$.
• $k$-th power of a matrix
  If $A$ is an $n\times n$ matrix, $A^k$ is defined recursively as follows: $A_0=I_n$, and $A^{k+1}=A^kA$ for $k\geq0$. For example, $A^1=A^0A=I_nA=A$ and $A^2=A^1A=AA$.
• Mathematical Induction
  If $P_n$ denotes a mathematical statement for each $n\geq1$, satisfying
  (1) $P_1$ is true,
  (2) the truth of $P_n$ implies that of $P_{n+1}$ for each $n\geq1$,
  then $P_n$ is true for all $n\geq1$.

Problems 2.4

1. Let $A$, $B$, $C$, $D$ be matrices defined by $$A=\begin{bmatrix}3 & 0\\ -1 & 2\\ 1 & 1\end{bmatrix}, \, B=\begin{bmatrix}1& 5& 2\\-1& 1& 0\\ -4& 1& 3 \end{bmatrix},\, C=\begin{bmatrix}-3& -1\\ 2& 1\\ 4& 3 \end{bmatrix}, \, D=\begin{bmatrix}4& -1\\ 2& 0 \end{bmatrix}.$$ Which of the following matrices are defined? Compute those matrices which are defined. $$A+B,\ A+C,\ AB,\ BA,\ CD,\ DC,\ D^2.$$
Solution:
$$A+C=\begin{bmatrix}3-3& 0-1\\-1+2& 2+1\\ 1+4& 1+3 \end{bmatrix}=\begin{bmatrix}0& -1\\1& 3\\ 5& 4 \end{bmatrix}$$
$$BA=\begin{bmatrix}1\times3-5\times1+2\times1& 1\times0+5\times2+2\times1\\-1\times3-1\times1+0\times1& -1\times0+1\times2+0\times1\\ -4\times3-1\times1+3\times1&-4\times0+1\times2+3\times1 \end{bmatrix}=\begin{bmatrix}0 &12\\-4&2\\-10&5 \end{bmatrix}$$ $$CD=\begin{bmatrix}-14 &3\\10& -2\\22& -4 \end{bmatrix}$$ $$D^2=\begin{bmatrix}14& -4\\8& -2 \end{bmatrix}$$
2. Let $A=\begin{bmatrix}-1& 0& 1\\ 0& 1& 1 \end{bmatrix}.$ Show that if $B$ is a $3\times2$ such that $AB=I_2$, then $$B=\begin{bmatrix}a& b\\ -a-1& 1-b\\a+1& b \end{bmatrix}$$ for suitable numbers $a$ and $b$. Use the associative law to show that $(BA)^2B=B$.

Solution:
Let $B=\begin{bmatrix}a& b\\c& d\\e& f \end{bmatrix}$, and we have $$AB=\begin{bmatrix}-1& 0& 1\\ 0& 1& 1 \end{bmatrix}\cdot\begin{bmatrix}a& b\\c& d\\e& f \end{bmatrix}=\begin{bmatrix}-a+e &-b+f\\c+e&d+f \end{bmatrix}=I_2=\begin{bmatrix}1& 0\\ 0& 1 \end{bmatrix}$$ Thus $$\begin{cases}-a+e=1\\-b+f=0\\c+e=0\\d+f=1 \end{cases}\Rightarrow\begin{cases}c=-e=-(a+1)=-a-1\\ d=1-f=1-b\\e=a+1\\f=b \end{cases}$$ That is $$B=\begin{bmatrix}a& b\\ -a-1& 1-b\\a+1& b \end{bmatrix}$$ Next $$(BA)^2B=BA\cdot BA\cdot B=B\cdot(AB)\cdot(AB)=B\cdot I_2\cdot I_2=B\cdot I_2=B$$
3. If $A=\begin{bmatrix}a& b\\c& d \end{bmatrix}$, prove that $A^2-(a+d)A+(ad-bc)I_2=0$

Solution:
Since
$$A^2=\begin{bmatrix}a& b\\c& d \end{bmatrix}\cdot\begin{bmatrix}a& b\\c& d \end{bmatrix}=\begin{bmatrix}a^2+bc& ab+bd\\ac+cd& bc+d^2 \end{bmatrix}$$ $$(a+d)\cdot A=\begin{bmatrix}a^2+ad& ab+bd\\ac+cd& ad+d^2 \end{bmatrix}$$ $$(ad-bc)I_2=(ad-bc)\cdot\begin{bmatrix}1& 0\\ 0& 1 \end{bmatrix}=\begin{bmatrix}ad-bc& 0\\ 0& ad-bc \end{bmatrix}$$ Thus $$A^2-(a+d)A+(ad-bc)I_2$$ $$=\begin{bmatrix}a^2+bc& ab+bd\\ac+cd& bc+d^2 \end{bmatrix}- \begin{bmatrix}a^2+ad& ab+bd\\ac+cd& ad+d^2 \end{bmatrix} +\begin{bmatrix}ad-bc& 0\\ 0& ad-bc \end{bmatrix}$$ $$=\begin{bmatrix}0& 0\\0& 0 \end{bmatrix}=0$$
4. If $A=\begin{bmatrix}4& -3\\ 1& 0 \end{bmatrix}$, use the fact $A^2=4A-3I_2$ and the mathematical induction, to prove that $$A^n={3^n-1\over2}A+{3-3^n\over2}I_2,\ \text{if}\ n\geq1.$$
Solution:
Note that according to the previous problem we have $a=4,\ b=-3,\ c=1,\ d=0$ in this problem, and hence we have $A^2-4A+3I_2=0$ which provided by the condition. By using mathematical induction, we have $$P_1: A^1={3-1\over2}A+{3-3\over2}I_2=A$$ is true; And suppose $$P_n: A^n={3^n-1\over2}A+{3-3^n\over2}I_2$$ is true, then we have $$P_{n+1}: A^{n+1}=A\cdot A^n={3^n-1\over2}A^2+{3-3^n\over2}AI_2$$ $$={3^n-1\over2}\cdot(4A-3I_2)+{3-3^n\over2}A$$ $$={4\cdot3^n-4+3-3^n\over2}A- {3^{n+1}-3\over2}I_2$$ $$={3^{n+1}-1\over2}A+{3-3^{n+1}\over2}I_2$$ which is true. Thus the original assumption $P_n$ is true.

5. A sequence of numbers $x_1,\ x_2,\ \cdots,\ x_n,\ \cdots$ satisfies the recurrence relation $x_{n+1}=ax_n+bx_{n-1}$ for $n\geq1$, where $a$ and $b$ are constant. Prove that $$\begin{bmatrix}x_{n+1}\\ x_n \end{bmatrix}=A\begin{bmatrix}x_n\\ x_{n-1} \end{bmatrix},$$ where $A=\begin{bmatrix}a& b\\1& 0 \end{bmatrix}$ and hence express $\begin{bmatrix}x_{n+1}\\x_n \end{bmatrix}$ in terms of $\begin{bmatrix}x_1\\x_0 \end{bmatrix}$.
If $a=4$ and $b=-3$, use the previous question to find a formula for $x_n$ in terms of $x_1$ and $x_0$.

Solution:
It is easy to see that $$A\begin{bmatrix}x_n\\ x_{n-1} \end{bmatrix}=\begin{bmatrix}a& b\\1& 0 \end{bmatrix}\cdot\begin{bmatrix}x_n\\ x_{n-1} \end{bmatrix}=\begin{bmatrix}ax_n+bx_{n-1}\\x_n \end{bmatrix}=\begin{bmatrix}x_{n+1}\\ x_n \end{bmatrix}$$ By recurrence relation we have $$\begin{bmatrix}x_{n+1}\\ x_n \end{bmatrix}=A\begin{bmatrix}x_n\\ x_{n-1} \end{bmatrix}=A\cdot A\begin{bmatrix}x_{n-1}\\ x_{n-2} \end{bmatrix}=A^2\begin{bmatrix}x_{n-1}\\ x_{n-2} \end{bmatrix}=\cdots=A^n\begin{bmatrix}x_{1}\\ x_{0} \end{bmatrix}$$ When $a=4$ and $b=-3$, $A=\begin{bmatrix}4& -3\\1& 0 \end{bmatrix}$, and according to the previous results we have $$\begin{bmatrix}x_{n+1}\\ x_n \end{bmatrix}=A^n\begin{bmatrix}x_{1}\\ x_{0} \end{bmatrix} =\left({3^n-1\over2}A+{3-3^n\over2}I_2\right)\cdot\begin{bmatrix}x_{1}\\ x_{0} \end{bmatrix}$$ $$=\left({3^n-1\over2}\cdot\begin{bmatrix}4& -3\\1& 0 \end{bmatrix}+{3-3^n\over2}\cdot\begin{bmatrix}1& 0\\ 0& 1 \end{bmatrix}\right)\cdot\begin{bmatrix}x_{1}\\ x_{0} \end{bmatrix}$$ $$=\begin{bmatrix}2\cdot(3^n-1)+{3-3^n\over2}&-{3\over2}\cdot (3^n-1)\\ {3^n-1\over2}&{3-3^n\over2}\end{bmatrix}\cdot\begin{bmatrix}x_{1}\\ x_{0} \end{bmatrix}$$ Thus we only need to compute the entry of $(2, 1)$ which is $x_n$: $$x_n={3^n-1\over2}x_1+{3-3^n\over2}x_0.$$
6. Let $A=\begin{bmatrix}2a&-a^2\\1&0 \end{bmatrix}$.
(a) Prove that $$A^n=\begin{bmatrix}(n+1)a^n&-na^{n+1}\\na^{n-1} & (1-n)a^n \end{bmatrix},\ \text{if}\ n\geq1.$$
(b) A sequence $x_0,\ x_1,\ \cdots,\ x_n,\ \cdots$ satisfies $x_{n+1}=2ax_n-a^2x_{n-1}$ for $n\geq1$. Use part (a) and the previous question to prove that $x_n=na^{n-1}x_1+(1-n)a^nx_0$ for $n\geq1$.

Solution:
(a) Using mathematical induction: $$P_1: A^1=\begin{bmatrix}(1+1)a&-a^2\\1&0 \end{bmatrix}=A$$ is true; Suppose that $$P_n: A^n=\begin{bmatrix}(n+1)a^n&-na^{n+1}\\na^{n-1} & (1-n)a^n \end{bmatrix}$$ is true, and we have $$P_{n+1}: A^{n+1}=A\cdot A^n=\begin{bmatrix}2a&-a^2\\1&0 \end{bmatrix}\cdot\begin{bmatrix}(n+1)a^n&-na^{n+1}\\na^{n-1} & (1-n)a^n \end{bmatrix}$$ $$=\begin{bmatrix}(2n+2)a^{n+1}-na^{n+1}&-2na^{n+2}-(1-n)a^{n+2}\\(n+1)a^{n} & -na^{n+1} \end{bmatrix}$$ $$=\begin{bmatrix}(n+2)a^{n+1}&-(n+1)a^{n+2}\\(n+1)a^{n} & -na^{n+1} \end{bmatrix}$$ follows the form of $A^{n}$, and hence the original assumption $P_n$ is true.

(b) Since $x_{n+1}=2ax_n-a^2x_{n-1}$, we have $$\begin{bmatrix}x_{n+1}\\x_n \end{bmatrix}=\begin{bmatrix}2a&-a^2\\1&0\end{bmatrix}\cdot\begin{bmatrix}x_n\\x_{n-1} \end{bmatrix} = A^{n}\cdot\begin{bmatrix}x_1\\x_0 \end{bmatrix}$$ $$=\begin{bmatrix}(n+1)a^n&-na^{n+1}\\na^{n-1} & (1-n)a^n \end{bmatrix}\cdot\begin{bmatrix}x_1\\x_0 \end{bmatrix}$$ Thus the entry of $(2, 1)$ is $x_n$: $$x_n=na^{n-1}x_1+(1-n)a^nx_0.$$
7. Let $A=\begin{bmatrix}a&b\\c&d \end{bmatrix}$ and suppose that $\lambda_1$ and $\lambda_2$ are the roots of the quadratic polynomial $x^2-(a+d)x+(ad-bc).$ ($\lambda_1$ and $\lambda_2$ may be equal.)
Let $k_n$ be defined by $k_0=0$, $k_1=1$ and for $n\geq2$ $$k_n=\sum_{i=1}^{n}\lambda_1^{n-i}\lambda_2^{i-1}.$$ Prove that $$k_{n+1}=(\lambda_1+\lambda_2)k_n-\lambda_1\lambda_2k_{n-1},$$ if $n\geq1$. Also prove that $$k_n=\begin{cases}\displaystyle{(\lambda_1^{n}-\lambda_2^{n}) \over (\lambda_1-\lambda_2)}& \mbox{if} \lambda_1\neq\lambda_2,\\ n\lambda_1^{n-1} & \mbox{if} \lambda_1=\lambda_2.\end{cases}$$ Use mathematical induction to prove that if $n\geq1$, $$A^n=k_nA-\lambda_1\lambda_2k_{n-1}I_2.$$
Solution:
First, we prove $k_{n+1}=(\lambda_1+\lambda_2)k_n-\lambda_1\lambda_2k_{n-1}$.
$$(\lambda_1+\lambda_2)k_n-\lambda_1\lambda_2k_{n-1} =(\lambda_1+\lambda_2(\lambda_1^{n-1}+\lambda_1^{n-2} \lambda_2 +\cdots+\lambda_1\lambda_2^{n-2}+\lambda_2^{n-1})$$ $$-\lambda_1\lambda_2(\lambda_1^{n-2}+\lambda_1^{n-3}\lambda_2 +\cdots+\lambda_1\lambda_2^{n-3}+\lambda_2^{n-2})$$ $$=(\lambda_1^{n}+\lambda_1^{n-1}\lambda_2+\cdots+\lambda_1^2 \lambda_2^{n-2}+\lambda_1\lambda_2^{n-1}) + (\lambda_1^{n-1}\lambda_2+\lambda_1^{n-2}\lambda_2^2+\cdots +\lambda_1\lambda_2^{n-1}+\lambda_2^{n})$$ $$-(\lambda_1^{n-1}\lambda_2+\lambda_1^{n-2}\lambda_2^2+\cdots +\lambda_1\lambda_2^{n-1}+\lambda_2^{n})$$ $$=\lambda_1^{n}+\lambda_1^{n-1}\lambda_2+\cdots+\lambda_1^2 \lambda_2^{n-2}+\lambda_1\lambda_2^{n-1} =\sum_{i=1}^{n}\lambda_1^{n+1-i}\lambda_2^{i-1}=k_{n+1}$$
Next, we prove $$k_n=\begin{cases}\displaystyle{(\lambda_1^{n}-\lambda_2^{n}) \over (\lambda_1-\lambda_2)}& \mbox{if}\ \lambda_1\neq\lambda_2,\\ n\lambda_1^{n-1} & \mbox{if}\ \lambda_1=\lambda_2.\end{cases}$$

• If $\lambda_1=\lambda_2$
  $$k_n=\sum_{i=1}^{n}\lambda_1^{n-i}\lambda_1^{i-1}= \sum_{i=1}^{n}\lambda_1^{n-1} = n\cdot\lambda_1^{n-1}$$
• If $\lambda_1\neq\lambda_2$
  $$(\lambda_1-\lambda_2)k_n=(\lambda_1-\lambda_2)(\lambda_1^{n-1}+\lambda_1^{n-2} \lambda_2 +\cdots+\lambda_1\lambda_2^{n-2}+\lambda_2^{n-1})$$ $$= (\lambda_1^{n}+\lambda_1^{n-1}\lambda_2+\cdots+\lambda_1^2 \lambda_2^{n-2}+\lambda_1\lambda_2^{n-1}) - (\lambda_1^{n-1}\lambda_2+\lambda_1^{n-2}\lambda_2^2+\cdots +\lambda_1\lambda_2^{n-1}+\lambda_2^{n}) =\lambda_1^{n}-\lambda_2^{n}$$ $$\Rightarrow k_n= {(\lambda_1^{n}-\lambda_2^{n}) \over (\lambda_1-\lambda_2)}$$

Finally, we prove $A^n=k_nA-\lambda_1\lambda_2k_{n-1}I_2$. By mathematical induction, we have $$P_1: A=k_1A-\lambda_1\lambda_2 k_0I_2 = A$$ is true. And suppose that $$P_n: A^n=k_nA-\lambda_1\lambda_2k_{n-1}I_2$$ is true. Then we have $$P_{n+1}: A^{n+1} = AA^{n} = k_nA^2-\lambda_1\lambda_2k_{n-1}I_2A$$ From problem 3, we know that $A^2=(a+d)A-(ad-bc)I_2$. And we have the following conclusion by basic algebra $$\begin{cases}\lambda_1+\lambda_2=a+d\\ \lambda_1\lambda_2=ad-bc, \end{cases}$$ thus $$A^{n+1} = k_n[(a+d)A-(ad-bc)I_2]-\lambda_1\lambda_2k_{n-1}A$$ $$=k_n(\lambda_1+\lambda_2)A-k_n\lambda_1\lambda_2I_2 -\lambda_1\lambda_2k_{n-1}A$$ $$=[k_n(\lambda_1+\lambda_2)-\lambda_1\lambda_2k_{n-1}]A - k_n\lambda_1\lambda_2I_2$$ $$=k_{n+1}A- \lambda_1\lambda_2k_nI_2$$ which follows the same form of $A^n$ and hence the assumption of $P_n$ is true.

8. Use Question 7 to prove that if $A=\begin{bmatrix}1&2\\2&1 \end{bmatrix}$, then $$A^{n}={3^n\over2}\begin{bmatrix}1&1\\1&1 \end{bmatrix}+{(-1)^{n-1}\over2}\begin{bmatrix}-1&1\\1&-1 \end{bmatrix}$$ if $n\geq1$.

Solution:
$\lambda_1$ and $\lambda_2$ are the roots of $$x^2-x-3=(x-3)(x+1) \Rightarrow \lambda_1=3,\ \lambda_2=1$$ Note that $\lambda_1\neq\lambda_2$ and use the formula from the previous problem we have $$k_n={3^n-(-1)^n\over3-(-1)}={3^n-(-1)^n\over4},\ k_{n-1}={3^{n-1}- (-1)^{n-1}\over4}$$ Hence $$A^{n}=k_nA-\lambda_1\lambda_2k_{n-1}I_2$$ $$={3^n-(-1)^n\over4}\cdot\begin{bmatrix}1&2\\2&1 \end{bmatrix} +3\cdot{3^{n-1}- (-1)^{n-1}\over4}\cdot\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}$$ $$={3^n + (-1)^{n-1} \over4} \cdot \begin{bmatrix}1&2\\2&1 \end{bmatrix} +{3^{n} - 3\cdot(-1)^{n-1}\over4}\cdot\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}$$ $$=\begin{bmatrix}\displaystyle{3^n+(-1)^{n-1} +3^n -3\cdot(-1)^{n-1} \over 4} & \displaystyle{3^n+(-1)^{n-1} \over 2}\\ \displaystyle{3^n+(-1)^{n-1} \over 2} & \displaystyle{3^n+(-1)^{n-1} +3^n -3\cdot(-1)^{n-1} \over 4}\end{bmatrix}$$ $$=\begin{bmatrix}\displaystyle{3^n\over 2} - {(-1)^{n-1}\over 2} & \displaystyle{3^n\over 2} + {(-1)^{n-1}\over 2}\\ \displaystyle{3^n\over 2} + {(-1)^{n-1}\over 2} & \displaystyle{3^n\over 2} - {(-1)^{n-1}\over 2}\end{bmatrix}$$ $$= {3^n\over2} \begin{bmatrix}1&1\\1&1 \end{bmatrix} +{(-1)^{n-1}\over2} \begin{bmatrix}-1&1\\1&-1 \end{bmatrix}$$
9. The Fibonacci numbers are defined by the equations $F_0=0$, $F_1=1$ and $F_{n+1}=F_n+F_{n-1}$ if $n\geq1$. Prove that $$F_n={1\over\sqrt{5}}\left(\left({1+\sqrt{5}\over2}\right)^n -\left({1-\sqrt{5}\over2}\right)^n\right)$$
Solution:
Since $F_{n+1}=F_n+F_{n-1}$, we have $$\begin{bmatrix}F_{n+1}\\ F_{n} \end{bmatrix}=\begin{bmatrix}1 & 1\\ 1 & 0 \end{bmatrix}\cdot\begin{bmatrix}F_{n}\\ F_{n-1} \end{bmatrix}= A\cdot\begin{bmatrix}F_{n}\\ F_{n-1} \end{bmatrix} = A^{n}\cdot\begin{bmatrix}F_{1}\\ F_{0} \end{bmatrix} = A^{n}\cdot \begin{bmatrix}1 \\ 0 \end{bmatrix}$$ where $A = \begin{bmatrix}1 & 1\\ 1 & 0 \end{bmatrix}$. From problem 7, we know $\lambda_1$ and $\lambda_2$ are the roots of $x^2-x-1\Rightarrow \lambda_1={1+\sqrt{5}\over2},\ \lambda_2={1-\sqrt{5}\over2}$. And $$k_n={\lambda_1^n-\lambda_2^n\over\lambda_1-\lambda_2} = {\left({1+\sqrt{5}\over2}\right)^n-\left({1-\sqrt{5}\over2}\right)^n \over\sqrt{5}}$$ $$\Rightarrow A^{n}=k_nA-\lambda_1\lambda_2k_{n-1}I_2=k_nA+k_{n-1}I_2$$ Hence $$\begin{bmatrix}F_{n+1}\\ F_{n} \end{bmatrix} = A^{n}\cdot \begin{bmatrix}1 \\ 0 \end{bmatrix} = (k_nA+k_{n-1}I_2)\cdot \begin{bmatrix}1 \\ 0 \end{bmatrix}$$ $$= \begin{bmatrix}k_n+k_{n-1} & k_n\\k_n& k_{n-1}\end{bmatrix} \cdot \begin{bmatrix}1 \\ 0 \end{bmatrix}= \begin{bmatrix}k_n+k_{n-1}\\ k_n\end{bmatrix}$$ That is, $$F_n=k_n = {1 \over\sqrt{5}}\cdot \left(\left({1+\sqrt{5}\over2}\right)^n - \left({1-\sqrt{5}\over2}\right)^n\right)$$
10. Let $r > 1$ be an integer. Let $a$ and $b$ be arbitrary positive integers. Sequences $x_n$ and $y_n$ of positive integers are defined in terms of $a$ and $b$ by the recurrence relations $$x_{n+1}=x_n+ry_n$$ $$y_{n+1} = x_n + y_n,$$ for $n\geq0$, where $x_0=a$ and $y_0=b$.
Use Question 7 to prove that $$\lim_{n\to\infty}{x_n\over y_n}=\sqrt{r}$$
Solution:
$$\begin{bmatrix}x_{n+1}\\ y_{n+1} \end{bmatrix} = \begin{bmatrix}1 & r\\1 & 1 \end{bmatrix} \cdot \begin{bmatrix}x_{n}\\ y_{n} \end{bmatrix} = A\cdot \begin{bmatrix}x_{n}\\ y_{n} \end{bmatrix} = A^{n+1}\cdot \begin{bmatrix}x_{0}\\ y_{0} \end{bmatrix} = A^{n+1}\cdot \begin{bmatrix}a\\ b \end{bmatrix}$$ where $A = \begin{bmatrix}1 & r\\1 & 1 \end{bmatrix}$.
$\lambda_1$ and $\lambda_2$ are the roots of $x^2-2x+(1-r)$, hence $$\lambda_1=1+\sqrt{r},\ \lambda_2 = 1-\sqrt{r}\Rightarrow k_n={\lambda_1^n-\lambda_2^n\over \lambda_1-\lambda_2} ={\lambda_1^n-\lambda_2^n\over 2\sqrt{r}}$$ And $$A^{n} = k_nA-\lambda_1\lambda_2k_{n-1}I_2 = k_nA-(1-r)k_{n-1}I_2$$ $$\Rightarrow \begin{bmatrix}x_{n}\\ y_{n} \end{bmatrix} = (k_nA-(1-r)k_{n-1}I_2)\cdot \begin{bmatrix}a\\ b \end{bmatrix}$$ $$=\left(\begin{bmatrix}k_n & rk_n\\k_n & k_n \end{bmatrix}-\begin{bmatrix}(1-r)k_{n-1} & 0\\0 & (1-r)k_{n-1} \end{bmatrix}\right) \cdot \begin{bmatrix}a\\ b \end{bmatrix}$$ $$= \begin{bmatrix}k_n-(1-r)k_{n-1} & rk_n\\k_n & k_n-(1-r)k_{n-1} \end{bmatrix}\cdot \begin{bmatrix}a\\ b \end{bmatrix}$$ $$=\begin{bmatrix}a(k_n-(1-r)k_{n-1}) + brk_n\\ ak_n + b(k_n-(1-r)k_{n-1}) \end{bmatrix}$$ Since $$\lim_{n\to\infty}{k_n\over k_{n-1}}=\lim_{n\to\infty}{\lambda_1^{n}-\lambda_2^{n}\over \lambda_1^{n-1}-\lambda_2^{n-1}} = \lim_{n\to\infty} {\lambda_1^n\left(1-\left(\displaystyle{\lambda_2\over\lambda_1} \right)^n\right) \over \lambda_1^{n-1}\left(1-\left(\displaystyle {\lambda_2\over\lambda_1} \right)^{n-1}\right)} = \lambda_1 = 1+\sqrt{r}$$ Thus $$\lim_{n\to\infty}{x_n\over y_n}=\lim_{n\to\infty} {a(k_n-(1-r)k_{n-1}) + brk_n \over ak_n + b(k_n-(1-r)k_{n-1})}$$ $$=\lim_{n\to\infty} {a(1+\sqrt{r}-(1-r))+br(1+\sqrt{r}) \over a(1+\sqrt{r}) + b(1+\sqrt{r}-(1-r))}$$ $$=\lim_{n\to\infty} {a(\sqrt{r} + r) + br(1+\sqrt{r}) \over a(1+\sqrt{r}) + b(\sqrt{r}+r)}$$ $$=\lim_{n\to\infty}{\sqrt{r}[a(1+\sqrt{r}) + b(\sqrt{r}+r)] \over a(1+\sqrt{r}) + b(\sqrt{r}+r)} = \sqrt{r}$$