Question

For any integer $\mathit{m}$, we define the Fibonacci number${\mathit{f}}_{\mathbf{m}}$recursively by${\mathit{f}}_{\mathbf{0}}\mathbf{=}\mathbf{0}\mathbf{,}{\mathit{f}}_{\mathbf{1}}\mathbf{=}\mathbf{1}$and${\mathit{f}}_{\mathbf{j}\mathbf{+}\mathbf{2}}\mathbf{=}{\mathit{f}}_{\mathbf{j}}\mathbf{+}{\mathit{f}}_{\mathbf{j}\mathbf{+}\mathbf{1}}$for all integers$\mathit{j}$.

a. Find the Fibonacci numbers ${\mathit{f}}_{\mathbf{m}}$for $\mathit{m}\mathbf{=}\mathbf{-}\mathbf{5}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}\mathbf{5}$.

b. Based upon your answer in part (a), describe the relationship between ${\mathit{f}}_{\mathbf{-}\mathbf{m}}$and${\mathit{f}}_{\mathbf{m}}$ .(For extra credit, give a formal proof by induction on$\mathit{m}$ .)

Now, let $\mathit{n}$be a positive integer with$\mathit{n}\mathbf{\ge }\mathbf{2}$ . Let$\mathit{V}$ be the two-dimensional subspace of all vectors$\overrightarrow{\mathbf{x}}$ in ${\mathit{ℝ}}^{\mathbf{n}}$such that${\mathit{x}}_{\mathbf{j}\mathbf{+}\mathbf{2}}\mathbf{=}{\mathit{x}}_{\mathbf{j}}\mathbf{+}{\mathit{x}}_{\mathbf{j}\mathbf{+}\mathbf{1}}$ , for all$\mathit{j}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}\mathit{n}\mathbf{-}\mathbf{2}$ . See Exercise 73. Note that, by definition, any $\mathit{n}$consecutive Fibonacci numbers form a vector in$\mathit{V}$ . Consider the basis$\overrightarrow{\mathbf{v}}\mathbf{,}\overrightarrow{\mathbf{w}}$ of $\mathit{V}$with

$\overrightarrow{\mathbf{v}}\mathbf{=}\mathbf{\left[}\begin{array}{c}{\mathbf{f}}_{\mathbf{0}}\\ {\mathbf{f}}_{\mathbf{1}}\\ \mathbf{⋮}\\ {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\\ {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\end{array}\mathbf{\right]}\mathbf{=}\mathbf{\left[}\begin{array}{c}\mathbf{0}\\ \mathbf{1}\\ \mathbf{⋮}\\ {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\\ {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\end{array}\mathbf{\right]}$and$\overrightarrow{\mathbf{w}}\mathbf{=}\mathbf{\left[}\begin{array}{c}{\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{1}}\\ {\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{2}}\\ \mathbf{⋮}\\ {\mathbf{f}}_{\mathbf{-}\mathbf{1}}\\ {\mathbf{f}}_{\mathbf{0}}\end{array}\mathbf{\right]}\mathbf{=}\mathbf{\left[}\begin{array}{c}{\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\\ \mathbf{-}{\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\\ \mathbf{⋮}\\ \mathbf{1}\\ \mathbf{0}\end{array}\mathbf{\right]}$

(In exercise 4.3.73c, we introduce this basis in the case$\mathit{n}\mathbf{=}\mathbf{4}$.) We told that ${\mathbf{\Vert }\overrightarrow{\mathbf{v}}\mathbf{\Vert }}^{\mathbf{2}}\mathbf{=}{\mathbf{\Vert }\overrightarrow{\mathbf{w}}\mathbf{\Vert }}^{\mathbf{2}}\mathbf{=}{\mathit{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}{\mathit{f}}_{\mathbf{n}}$.(For extra credit, give a proof by induction on .)

c.Find the basis$\overrightarrow{\mathbf{v}}\mathbf{,}\overrightarrow{\mathbf{w}}$in the case$\mathit{n}\mathbf{=}\mathbf{6}$. Verify the identity${\mathbf{\Vert }\overrightarrow{\mathbf{v}}\mathbf{\Vert }}^{\mathbf{2}}\mathbf{=}{\mathbf{\Vert }\overrightarrow{\mathbf{w}}\mathbf{\Vert }}^{\mathbf{2}}\mathbf{=}{\mathit{f}}_{\mathbf{5}}{\mathit{f}}_{\mathbf{6}}$. Also, show that$\overrightarrow{\mathbf{v}}$is orthogonal to .

d.Show that$\overrightarrow{v}$is the orthogonal to$\overrightarrow{\mathbf{w}}$for any even positive integer$\mathit{n}$.

e. For an even positive integer$\mathit{n}$ , let $\mathit{P}$be the matrix of the orthogonal projection onto $\mathit{V}$. Show that the first column of$\mathit{P}$ is$\frac{\mathbf{1}}{{\mathbf{f}}_{\mathbf{n}}}\overrightarrow{\mathbf{w}}$ , while the last column is$\frac{\mathbf{1}}{{\mathbf{f}}_{\mathbf{n}}}\overrightarrow{\mathbf{v}}$ . Recall from exercise 73 that $\mathit{P}$is a Hankel matrix, and not that a Hankel matrix is determined by its first and last columns. Conclude that$\mathit{P}\mathbf{=}\frac{\mathbf{1}}{{\mathbf{f}}_{\mathbf{n}}}\mathbf{\left[}\begin{array}{ccccc}{\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{1}}& {\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{2}}& \mathbf{\cdots }& {\mathbf{f}}_{\mathbf{-}\mathbf{1}}& {\mathbf{f}}_{\mathbf{0}}\\ {\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{2}}& {\mathbf{f}}_{\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{3}}& \mathbf{\cdots }& {\mathbf{f}}_{\mathbf{0}}& {\mathbf{f}}_{\mathbf{1}}\\ \mathbf{⋮}& \mathbf{⋮}& \mathbf{\ddots }& \mathbf{⋮}& \mathbf{⋮}\\ {\mathbf{f}}_{\mathbf{-}\mathbf{1}}& {\mathbf{f}}_{\mathbf{0}}& \mathbf{\cdots }& {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{3}}& {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\\ {\mathbf{f}}_{\mathbf{0}}& {\mathbf{f}}_{\mathbf{1}}& \mathbf{\cdots }& {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}& {\mathbf{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\end{array}\mathbf{\right]}$

Meaning that the$\mathit{i}\mathit{j}\mathbf{\text{th}}$ entry of$\mathit{P}$ is$\frac{{\mathbf{f}}_{\mathbf{i}\mathbf{+}\mathbf{j}\mathbf{-}\mathbf{n}\mathbf{-}\mathbf{1}}}{{\mathbf{f}}_{\mathbf{n}}}$ .

f. Find the matrix $\mathit{P}$in the case role="math" localid="1660914532434" $\mathit{n}\mathbf{=}\mathbf{6}$

Short answer

a.The values are$f_{-5}=5,f_{-4}=-3,f_{-3}=2,f_{-2}=-1,f_{-1}=1$ ,$f_0=0,f_1=1,f_2=1,f_3=2,f_4=3,f_5=5$.

b. The relationship between $f_{-m}$and $f_m$is $f_{-m}={(-1)}^{(m+1)}{f}_m$.

c. The basis at$n=6$ are$\overrightarrow{v}=\left[\begin{array}{c}0\\ 1\\ 1\\ 2\\ 3\\ 5\end{array}\right]$ and .$\overrightarrow{w}=\left[\begin{array}{c}5\\ -3\\ 2\\ -1\\ 1\\ 0\end{array}\right]$

d. It is proved that$\overrightarrow{v}$ is orthogonal to $\overrightarrow{w}$for any even arbitrary numbe$n$r .

e. It is proved that$i{j}^{th}$ entry of$P$ is $\frac{f_{i+j-n-1}}{f_n}$.

f. The matrix$P$ at$n=6$ is $P=\left[\begin{array}{cccccc}5& -3& 2& -1& 1& 0\\ -3& 2& -1& 1& 0& 1\\ 2& -1& 1& 0& 1& 1\\ -1& 1& 0& 1& 1& 2\\ 1& 0& 1& 1& 2& 3\\ 0& 1& 1& 2& 3& 5\end{array}\right]$.

Step-by-step solution

 Step 1: Fibonacci sequence 

The${\mathit{n}}^{\mathbf{t}\mathbf{h}}$ term of the Fibonacci sequence is given by ${\mathit{f}}_{\mathbf{n}}\mathbf{=}{\mathit{f}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathit{f}}_{\mathbf{n}\mathbf{-}\mathbf{2}}$.

 Step 2: Find Fibonacci numbers

(a)

It is known that the Fibonacci numbers are given by$f_{j+2}=f_j+f_{j+1}$ which is equivalent to$f_j=f_{j+2}-f_{j+1}$ . So, the Fibonacci numbers for$m=-5,\mathrm{...},5$ are$f_{-5}=5,f_{-4}=-3,f_{-3}=2$ , $f_{-2}=-1,f_{-1}=1$, $f_0=0,f_1=1,f_2=1,f_3=2,f_4=3,f_5=5$.

Thus, the values are$f_{-5}=5,f_{-4}=-3,f_{-3}=2,f_{-2}=-1,f_{-1}=1$ ,$f_0=0,f_1=1,f_2=1$, $f_3=2,f_4=3,f_5=5$.

Find the relationship 

(b)

The value obtained in the part (a) are ,$f_{-5}=5,f_{-4}=-3,f_{-3}=2,f_{-2}=-1,f_{-1}=1$, $f_0=0,f_1=1,f_2=1$.$f_3=2,f_4=3,f_5=5$

Here, it can be easily noticed that$f_{-m}=f_m$ if$m$ is odd, and $f_{-m}=-f_m$if $m$is even. So, the relationship can be interpreted as$f_{-m}={(-1)}^{m+1}{f}_m$ .

Thus, the relationship between$f_{-m}$ and$f_m$ is$f_{-m}={(-1)}^{(m+1)}{f}_m$ .

Find the basis for given n

c)

Here, we have $\overrightarrow{v}=\left[\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_{n-2}\\ f_{n-1}\end{array}\right]$and$\overrightarrow{w}=\left[\begin{array}{c}{f}_{-n+1}\\ f_{-n+2}\\ ⋮\\ f_{-1}\\ f_0\end{array}\right]$.For $n=6$, the basis are$\overrightarrow{v}=\left[\begin{array}{c}{f}_0\\ f_1\\ f_2\\ f_3\\ f_4\\ f_5\end{array}\right]$and $\overrightarrow{w}=\left[\begin{array}{c}{f}_{-5}\\ f_{-4}\\ f_{-3}\\ f_{-2}\\ f_{-1}\\ f_0\end{array}\right]$. Now, take values from part (a) to get, $\overrightarrow{v}=\left[\begin{array}{c}0\\ 1\\ 1\\ 2\\ 3\\ 5\end{array}\right]$and$\overrightarrow{w}=\left[\begin{array}{c}5\\ -3\\ 2\\ -1\\ 1\\ 0\end{array}\right]$.

Now, find the value of ${\Vert \overrightarrow{v}\Vert }^2$:

$\begin{array}{c}{\Vert \overrightarrow{v}\Vert }^2=0^2+1^2+1^2+2^2+3^2+5^2\\ =0+1+1+4+9+25\\ =40\end{array}$

Now, find the value of ${\Vert \overrightarrow{w}\Vert }^2$:

$\begin{array}{c}{\Vert \overrightarrow{w}\Vert }^2=0^2+1^2+1^2+2^2+3^2+5^2\\ =0+1+1+4+9+25\\ =40\end{array}$

So, we get ${\Vert \overrightarrow{v}\Vert }^2={\Vert \overrightarrow{w}\Vert }^2$.Now, find $f_6$:

$\begin{array}{c}{f}_6=f_4+f_5\\ =3+5\\ =8\end{array}$

So, the value of $f_5\cdot f_6$obtained as:

$\begin{array}{c}{f}_5\cdot f_6=5\times 8\\ =40\end{array}$

Therefore, it is proved that${\Vert \overrightarrow{v}\Vert }^2={\Vert \overrightarrow{w}\Vert }^2=f_5{f}_6$ .

Now, to prove if$\overrightarrow{v}$ and $\overrightarrow{w}$are orthogonal, find the$\overrightarrow{v}\cdot \overrightarrow{w}$ :

$\begin{array}{c}\overrightarrow{v}\cdot \overrightarrow{w}=0\times 5+1\times (-3)+1\times 2+2\times (-1)+3\times 1+5\times 0\\ =0-3+2-2+3+0\\ =0\end{array}$

Since, $\overrightarrow{v}\cdot \overrightarrow{w}=0$, therefore, $\overrightarrow{v}$is orthogonal to$\overrightarrow{w}$.

Thus, it is proved that$\overrightarrow{v}$ is orthogonal to$\overrightarrow{w}$ .

Proof of part (d)

(d)

Find the dot product between$\overrightarrow{v}$ and$\overrightarrow{w}$ for arbitrary even number$n$ :

$\begin{array}{c}\overrightarrow{v}\cdot \overrightarrow{w}=f_0\times f_{-n+1}+f_1\times f_{-n+2}+\mathrm{...}+f_{n-2}\times f_{-1}+f_{n-1}\times f_0\\ =f_0\times f_{-n+1}+f_1\times f_{-n+2}+\mathrm{...}+f_0\times f_{n-1}+f_{-1}\times f_{n-2}+f_{-2}\times f_{n-3}+\mathrm{...}\end{array}$

Now, from part (b), we have $f_{-m}={(-1)}^{m+1}{f}_m$. Use thisin the above equations:

$\begin{array}{c}\overrightarrow{v}\cdot \overrightarrow{w}=f_0\times f_{n-1}-f_1\times f_{n-2}+f_2\times f_{n-3}+\mathrm{...}+f_0\times f_{n-1}+f_1\times f_{n-2}-f_2\times f_{n-3}+\mathrm{...}\\ =2f_0\times f_{n-1}\\ =2\times 0\times f_{n-1}\\ =0\end{array}$

So, this implies$\overrightarrow{v}$ is orthogonal to$\overrightarrow{w}$ .

Thus, it is proved that$\overrightarrow{v}$ is orthogonal to$\overrightarrow{w}$for any even arbitrary number $n$.

Find the meaning of ijth entry of P

$i{j}^{th}$(e)

Now, from the previous parts, we have$\overrightarrow{v}$ is orthogonal to $\overrightarrow{w}$, so, the projection matrix $P$onto $V$is given by:

$\begin{array}{c}P=\left(\frac{\overrightarrow{v}}{\Vert \overrightarrow{v}\Vert }\right){\left(\frac{\overrightarrow{v}}{\Vert \overrightarrow{v}\Vert }\right)}^T+\left(\frac{\overrightarrow{w}}{\Vert \overrightarrow{w}\Vert }\right)\left(\frac{\overrightarrow{w}}{\Vert \overrightarrow{w}\Vert }\right)\\ =\frac{\overrightarrow{v}{\overrightarrow{v}}^T}{{\Vert \overrightarrow{v}\Vert }^2}+\frac{\overrightarrow{w}{\overrightarrow{w}}^T}{{\Vert \overrightarrow{w}\Vert }^2}\end{array}$

So, the foremost column of$P$ is given by:

$\begin{array}{c}\frac{1}{{\Vert \overrightarrow{v}\Vert }^2}\left[\begin{array}{c}{v_1}^2\\ v_1{v}_2\\ ⋮\\ v_1{v}_{n-1}\\ v_1{v}_n\end{array}\right]+\frac{1}{{\Vert \overrightarrow{w}\Vert }^2}\left[\begin{array}{c}{w_1}^2\\ w_1{w}_2\\ ⋮\\ w_1{w}_{n-1}\\ w_1{w}_n\end{array}\right]=\frac{v_1}{{\Vert \overrightarrow{v}\Vert }^2}\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_{n-1}\\ v_n\end{array}\right]+\frac{w_1}{{\Vert \overrightarrow{w}\Vert }^2}\left[\begin{array}{c}{w}_1\\ w_2\\ ⋮\\ w_{n-1}\\ w_n\end{array}\right]\\ =\frac{v_1}{{\Vert \overrightarrow{v}\Vert }^2}\overrightarrow{v}+\frac{w_1}{{\Vert \overrightarrow{w}\Vert }^2}\overrightarrow{w}\end{array}$

Now, we have $v_1=f_0=0$and $w_1=f_{n-1}$. So, the first column becomes:

$\begin{array}{c}\frac{v_1}{{\Vert \overrightarrow{v}\Vert }^2}\overrightarrow{v}+\frac{w_1}{{\Vert \overrightarrow{w}\Vert }^2}\overrightarrow{w}=0+\frac{f_{n-1}}{f_{n-1}\times f_n}\overrightarrow{w}\\ =\frac{1}{f_n}\overrightarrow{w}\end{array}$

The last column of$P$ is given by:

$\begin{array}{c}\frac{1}{{\Vert \overrightarrow{v}\Vert }^2}\left[\begin{array}{c}{v}_1{v}_n\\ v_2{v}_n\\ ⋮\\ v_{n-1}{v}_n\\ {v_n}^2\end{array}\right]+\frac{1}{{\Vert \overrightarrow{w}\Vert }^2}\left[\begin{array}{c}{w}_1{w}_n\\ w_2{w}_n\\ ⋮\\ w_{n-1}{w}_n\\ {w_n}^2\end{array}\right]=\frac{v_n}{{\Vert \overrightarrow{v}\Vert }^2}\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_{n-1}\\ v_n\end{array}\right]+\frac{w_1}{{\Vert \overrightarrow{w}\Vert }^2}\left[\begin{array}{c}{w}_1\\ w_2\\ ⋮\\ w_{n-1}\\ w_n\end{array}\right]\\ =\frac{v_n}{{\Vert \overrightarrow{v}\Vert }^2}\overrightarrow{v}+\frac{w_n}{{\Vert \overrightarrow{w}\Vert }^2}\overrightarrow{w}\end{array}$

Now, we have $w_n=f_0=0$and .$v_n=f_{n-1}$ So, the first column becomes:

$\begin{array}{c}\frac{v_1}{{\Vert \overrightarrow{v}\Vert }^2}\overrightarrow{v}+\frac{w_1}{{\Vert \overrightarrow{w}\Vert }^2}\overrightarrow{w}=\frac{f_{n-1}}{f_{n-1}\times f_n}\overrightarrow{v}+0\\ =\frac{1}{f_n}\overrightarrow{v}\end{array}$

So, from above calculation we getthe matrix $P$is given by:

$P=\frac{1}{f_n}\left[\begin{array}{ccccc}{f}_{-n+1}& f_{-n+2}& \cdots & f_{-1}& f_0\\ f_{-n+2}& f_{-n+3}& \cdots & f_0& f_1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ f_{-1}& f_0& \cdots & f_{n-3}& f_{n-2}\\ f_0& f_1& \cdots & f_{n-2}& f_{n-1}\end{array}\right]$

And the entry of$P$ is $\frac{f_{i+j-n-1}}{f_n}$.

Find projection matrix

(f)

Here, we have to find $P$for $n=6$. The matrix $P$is given by:

$\begin{array}{c}P=\left[\begin{array}{cccccc}{f}_{-5}& f_{-4}& f_{-3}& f_{-2}& f_{-1}& f_0\\ f_{-4}& f_{-3}& f_{-2}& f_{-1}& f_0& f_1\\ f_{-3}& f_{-2}& f_{-1}& f_0& f_1& f_2\\ f_{-2}& f_{-1}& f_0& f_1& f_2& f_3\\ f_{-1}& f_0& f_1& f_2& f_3& f_4\\ f_0& f_1& f_2& f_3& f_4& f_5\end{array}\right]\\ =\left[\begin{array}{cccccc}5& -3& 2& -1& 1& 0\\ -3& 2& -1& 1& 0& 1\\ 2& -1& 1& 0& 1& 1\\ -1& 1& 0& 1& 1& 2\\ 1& 0& 1& 1& 2& 3\\ 0& 1& 1& 2& 3& 5\end{array}\right]\end{array}$

Thus, the matrix $P$at$n=6$ is$P=\left[\begin{array}{cccccc}5& -3& 2& -1& 1& 0\\ -3& 2& -1& 1& 0& 1\\ 2& -1& 1& 0& 1& 1\\ -1& 1& 0& 1& 1& 2\\ 1& 0& 1& 1& 2& 3\\ 0& 1& 1& 2& 3& 5\end{array}\right]$ .