\textbf{Exercise 4 — Candidates who have followed the specialization course}

We call Fibonacci sequence the sequence $( u _ { n } )$ defined by $u _ { 0 } = 0 , u _ { 1 } = 1$ and, for every natural integer $n$,

$$u _ { n + 2 } = u _ { n + 1 } + u _ { n }$$

We admit that, for every natural integer $n$, $u _ { n }$ is a natural integer.\\
Parts A and B can be treated independently.

\section*{Part A}
\begin{enumerate}
  \item a. Calculate the terms of the Fibonacci sequence up to $u _ { 10 }$.\\
b. What can be conjectured about the GCD of $u _ { n }$ and $u _ { n + 1 }$ for every natural integer $n$?
  \item We define the sequence $\left( v _ { n } \right)$ by $v _ { n } = u _ { n } ^ { 2 } - u _ { n + 1 } \times u _ { n - 1 }$ for every non-zero natural integer $n$.\\
a. Prove that, for every non-zero natural integer $n$, $v _ { n + 1 } = - v _ { n }$.\\
b. Deduce that, for every non-zero natural integer $n$,
\end{enumerate}

$$u _ { n } ^ { 2 } - u _ { n + 1 } \times u _ { n - 1 } = ( - 1 ) ^ { n - 1 }$$

c. Then prove the conjecture made in question 1.b.

\section*{Part B}
We consider the matrix $F = \left( \begin{array} { l l } 1 & 1 \\ 1 & 0 \end{array} \right)$.

\begin{enumerate}
  \item Calculate $F ^ { 2 }$ and $F ^ { 3 }$. You may use a calculator.
  \item Prove by induction that, for every non-zero natural integer $n$,
\end{enumerate}

$$F ^ { n } = \left( \begin{array} { c c } u_{n+1} & u_n \\ u_n & u_{n-1} \end{array} \right)$$