The sequence \(F_n\), for \(n = 0, 1, 2, \ldots\), is defined by \(F_0 = 0\), \(F_1 = 1\) and by \(F_{n+2} = F_{n+1} + F_n\) for \(n \geqslant 0\).
Prove by induction that, for all positive integers \(n\),
\[\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \mathbf{Q}^n,\]
where the matrix \(\mathbf{Q}\) is given by
\[\mathbf{Q} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.\]
- By considering the matrix \(\mathbf{Q}^n\), show that \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) for all positive integers \(n\).
- By considering the matrix \(\mathbf{Q}^{m+n}\), show that \(F_{m+n} = F_{m+1}F_n + F_m F_{n-1}\) for all positive integers \(m\) and \(n\).
- Show that \(\mathbf{Q}^2 = \mathbf{I} + \mathbf{Q}\).
In the following parts, you may use without proof the Binomial Theorem for matrices:
\[(\mathbf{I} + \mathbf{A})^n = \sum_{k=0}^{n} \binom{n}{k} \mathbf{A}^k.\]
- Show that, for all positive integers \(n\),
\[F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_k\,.\]
- Show that, for all positive integers \(n\),
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} 2^k F_k\]
and also that
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} F_{n+k}\,.\]
- Show that, for all positive integers \(n\),
\[\sum_{k=0}^{n} (-1)^{n+k} \binom{n}{k} F_{n+k} = 0\,.\]