A Fibonacci Identity by Induction

The Fibonacci sequence is given by:
F_n=F_{n-1}+F_{n-2}, \ \ F_1=1, F_2=1, n \in \Bbb Z

In this question, we will prove that
\forall n,m \in \Bbb Z, \ F_{n+m}=F_{n+1}F_m+F_nF_{m-1}
in two different ways.

a) i) Show that:
\forall n \in \Bbb Z, \begin{pmatrix}F_{n+1} & F_n\\F_n & F_{n-1}\end{pmatrix}= \begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^n

ii) Hence prove that:
\forall n,m \in \Bbb Z, \ F_{n+m}=F_{n+1}F_m+F_nF_{m-1}

b) Prove the theorem directly by induction on n then induction on m.

1 Like

for a) is it meant to be F_{n-1} in the bottom right

yup, sorry about the typo :stuck_out_tongue:

a) i) Assume true for some n=k:

\begin{pmatrix} F_{k+1} & F_k\\ F_k& F_{k-1} \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^k

\begin{pmatrix} F_{k+1} & F_k\\ F_k& F_{k-1} \end{pmatrix}\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix} =\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^k\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}

\begin{pmatrix} F_{k+1}+F_k &F_{k+1} \\ F_k+F_{k-1}&F_k \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{k+1}

\begin{pmatrix} F_{k+2} &F_{k+1} \\ F_{k+1}&F_k \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{k+1}

\therefore if true for some n=k then true for all integer k\geq n

When n=1 we have
\begin{pmatrix} F_2 &F_1 \\ F_1&F_0 \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^1

\therefore by induction it is true for all positive integers n.

ii) from i) we know that \begin{pmatrix} F_{n+m+1} & F_{n+m}\\ F_{n+m}& F_{n+m-1} \end{pmatrix}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{n+m}

And using laws of indices we have

\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{n+m}=\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{n}\begin{pmatrix} 1 &1 \\ 1&0 \end{pmatrix}^{m}=\begin{pmatrix} F_{n+1} & F_{n}\\ F_{n}& F_{n-1} \end{pmatrix}\begin{pmatrix} F_{m+1} & F_{m}\\ F_{m}& F_{m-1} \end{pmatrix}=\begin{pmatrix} ...& F_{n+1}F_{m}+F_{n}F_{m-1}\\ ...& ... \end{pmatrix}

Which gives us:

\begin{pmatrix} F_{n+m+1} & F_{n+m}\\ F_{n+m}& F_{n+m-1} \end{pmatrix}=\begin{pmatrix} ...& F_{n+1}F_{m}+F_{n}F_{m-1}\\ ...& ... \end{pmatrix}

Comparing the elements in the top right corner we can see that F_{n+m}=F_{n+1}F_m+F_nF_{m-1} as required.

b) We’ll do this using 2 inductions; firstly showing it to be true for all n, and the second showing to be true for all m. \therefore together we conclude that it is true for all m and n.

Induction 1
Assume the statement to be true for some n=N-1 and n=N
This gives us 2 identities:

  • F_{(N-1)+m}=F_{N}F_m+F_{N-1}F_{m-1}

  • F_{N+m}=F_{N+1}F_m+F_{N}F_{m-1}

F_{(N+1)+m}=F_{N+m}+F_{N+m-1}=F_{N}F_m+F_{N-1}F_{m-1}+F_{N+1}F_m+F_{N}F_{m-1}
\qquad \qquad \qquad \qquad \qquad \qquad \; \; \;=F_m\left( F_N+F_{N+1} \right)+F_{m-1}\left( F_N+F_{N-1}\right)
\qquad \qquad \qquad \qquad \qquad \qquad \; \; \;=F_mF_{N+2}+F_{m-1}F_{N+1}

\therefore if true for some n=N-1 and n=N then the statement is true for all positive integers n.
When n=0 we have F_m=F_1F_m+F_0F_{m-1}\Rightarrow F_m=F_m
and when n=1 we have F_{1+m}=F_2F_m+F_1F_{m-1}\Rightarrow F_{m+1}=F_m+F_{m-1}

\therefore true for n=0 and n=1 so true for \forall n\in \mathbb{Z}^+

Induction 2
Assume the statement to be true for some m=M-1 and m=M
This gives us 2 identities:

  • F_{n+(M-1)}=F_{n+1}F_{M-1}+F_{n}F_{M-2}

  • F_{n+M}=F_{n+1}F_M+F_{n}F_{M-1}

F_{n+M+1}=F_{n+M}+F_{n+M-1}=F_{n+1}F_M+F_{n}F_{M-1}+F_{n+1}F_{M-1}+F_{n}F_{M-2}
\qquad \qquad \qquad \qquad \qquad \qquad =F_{n+1}\left( F_M+F_{M-1}\right) + F_{n}\left( F_{M-1}+F_{M-2}\right)
\qquad \qquad \qquad \qquad \qquad \qquad=F_{n+1}F_{M+1}+F_nF_M

When m=1 we have F_{n+1}=F_{n+1}F_1+F_nF_0\Rightarrow F_{n+1}=F_{n+1}
and when m=2 F_{n+2}=F_{n+1}F_2+F_nF_1\Rightarrow F_{n+2}=F_{n+1}+F_n

If true for some m=M-1 and m=M then true for all m\geq M-1. Shown true for m=1 and m=2 \therefore true \forall m\in \mathbb{Z}^+

QED

4 Likes

nice!

1 Like