\textbf{(Candidates who have followed the specialisation course)}

We define the sequence of real numbers $(a_{n})$ by:
$$\begin{cases} a_{0} & = 0 \\ a_{1} & = 1 \\ a_{n+1} & = a_{n} + a_{n-1} \text{ for } n \geqslant 1 \end{cases}$$
This sequence is called the Fibonacci sequence.

\begin{enumerate}
  \item Copy and complete the algorithm below so that at the end of its execution the variable $A$ contains the term $a_{n}$.
\begin{verbatim}
$A \leftarrow 0$
$B \leftarrow 1$
For $i$ going from 1 to $n$ :
    $C \leftarrow A + B$
    $A \leftarrow \ldots$
    $B \leftarrow \ldots$
End For
\end{verbatim}
We thus obtain the first values of the sequence $a_{n}$:
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | c | c | }
\hline
$n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
$a_{n}$ & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 \\
\hline
\end{tabular}
\end{center}
  \item Let the matrix $A = \left(\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right)$.

Calculate $A^{2}$, $A^{3}$ and $A^{4}$.\\
Verify that $A^{5} = \left(\begin{array}{ll} 8 & 5 \\ 5 & 3 \end{array}\right)$.
  \item We can prove, and we will admit, that for every non-zero natural number $n$,
$$A^{n} = \left(\begin{array}{cc} a_{n+1} & a_{n} \\ a_{n} & a_{n-1} \end{array}\right)$$
a. Let $p$ and $q$ be two non-zero natural numbers. Calculate the product $A^{p} \times A^{q}$ and deduce that
$$a_{p+q} = a_{p} \times a_{q+1} + a_{p-1} \times a_{q}$$
b. Deduce that if an integer $r$ divides the integers $a_{p}$ and $a_{q}$, then $r$ also divides $a_{p+q}$.
\end{enumerate}