Exercise 4.4.7 ($F_{m+n} = F_{m-1} F_n + F_m F_{n+1}$, and $m \mid n \Rightarrow F_m \mid F_n$)

Proof.

(a)

As in the second proof of Problem 6, put for every positive integer $n$, $$A=\left(\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right),X_n=\left(\begin{array}{c}\hfill F_n\hfill \\ \hfill F_{n+1}\hfill \end{array}\right),V_n=\left(\begin{array}{cc}\hfill F_{n-1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n+1}\hfill \end{array}\right).$$

Then, for all $n\in {\mathbb{N}}^{\text{∗}}$, $X_n=A{X}_{n-1},V_n=A{V}_{n-1}$ and

$$V_n=\left(\begin{array}{cc}\hfill F_{n-1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n+1}\hfill \end{array}\right)={\left(\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right)}^n=A^n.$$

(see Problem 6).

Now $X_{n+m}=A^m{X}_n$, so

$$\begin{array}{llll}\hfill \left(\begin{array}{c}\hfill F_{n+m}\hfill \\ \hfill F_{n+m+1}\hfill \end{array}\right)& =A^m{X}_n& \hfill & \\ \hfill & =V_m{X}_n& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill F_{m-1}\hfill & \hfill F_m\hfill \\ \hfill F_m\hfill & \hfill F_{m+1}\hfill \end{array}\right)\left(\begin{array}{c}\hfill F_n\hfill \\ \hfill F_{n+1}\hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{c}\hfill F_{m-1}{F}_n+F_m{F}_{n+1}\hfill \\ \hfill F_m{F}_n+F_m{F}_{n+1}\hfill \end{array}\right).& \hfill & \end{array}$$

In particular, for all positive integers $m,n$,

$$F_{n+m}=F_{m-1}{F}_n+F_m{F}_{n+1}.$$

(Alternatively, we can reason by induction on $n$, but this induction is just a verification of the preceding relations.)

(b)

Let $m$ be a positive integer. We show by induction on $q\ge 1$ the property $$𝒫(q):F_m\mid F_{\mathit{qm}}$$

• $F_m\mid F_m$, so $𝒫(1)$ is true.

• Suppose now that $F_m\mid F_{\mathit{qm}}$ for some $q\ge 1$. Then we apply part (a) with $n=\mathit{qm}$. We obtain

  $$F_{m+\mathit{qm}}=F_{m-1}{F}_{\mathit{qm}}+F_m{F}_{\mathit{qm}+1}.$$

  By the induction hypothesis $F_m\mid F_{\mathit{qm}}$, thus $F_m\mid F_{m-1}{F}_{\mathit{qm}}+F_m{F}_{\mathit{qm}+1}=F_{(q+1)m}$, so $𝒫(q+1)$ is true.

• The induction is done, so for all positive integers $m,n$,

  $$m\mid n\Rightarrow F_m\mid F_n.$$