\textbf{Exercise 4 — For candidates who have followed the speciality course}

We consider the matrix $M = \left( \begin{array} { l l } 2 & 3 \\ 1 & 2 \end{array} \right)$ and the sequences of natural numbers $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by:\\
$u _ { 0 } = 1 , v _ { 0 } = 0$, and for every natural number $n , \binom { u _ { n + 1 } } { v _ { n + 1 } } = M \binom { u _ { n } } { v _ { n } }$.\\
The two parts can be treated independently.

\section*{Part A}
The first terms of the sequence $\left( v _ { n } \right)$ have been calculated:

\begin{center}
\begin{tabular}{ | c | c | 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 & 11 & 12 \\
\hline
$v _ { n }$ & 0 & 1 & 4 & 15 & 56 & 209 & 780 & 2911 & 10864 & 40545 & 151316 & 564719 & 2107560 \\
\hline
\end{tabular}
\end{center}

\begin{enumerate}
  \item Conjecture the possible values of the units digit of the terms of the sequence $\left( v _ { n } \right)$.
  \item It is admitted that for every natural number $n , \binom { u _ { n + 3 } } { v _ { n + 3 } } = M ^ { 3 } \binom { u _ { n } } { v _ { n } }$.\\
a. Justify that for every natural number $n , \left\{ \begin{array} { l } u _ { n + 3 } = 26 u _ { n } + 45 v _ { n } \\ v _ { n + 3 } = 15 u _ { n } + 26 v _ { n } \end{array} \right.$.\\
b. Deduce that for every natural number $n : v _ { n + 3 } \equiv v _ { n } [ 5 ]$.
  \item Let $r$ be a fixed natural number. Prove, using a proof by induction, that, for every natural number $q , v _ { 3 q + r } \equiv v _ { r }$ [5].
  \item Deduce that for every natural number $n$ the term $v _ { n }$ is congruent to 0, to 1 or to 4 modulo 5.
  \item Conclude regarding the set of values taken by the units digit of the terms of the sequence $\left( v _ { n } \right)$.
\end{enumerate}

\section*{Part B}
The objective of this part is to prove that $\sqrt { 3 }$ is not a rational number using the matrix $M$.

To do this, we perform a proof by contradiction and assume that $\sqrt { 3 }$ is a rational number. In this case, $\sqrt { 3 }$ can be written in the form of an irreducible fraction $\frac { p } { q }$ where $p$ and $q$ are non-zero natural numbers, with $q$ the smallest possible natural number.

\begin{enumerate}
  \item Show that $q < p < 2 q$.
  \item It is admitted that the matrix $M$ is invertible. Give its inverse $M ^ { - 1 }$ (no justification is expected).\\
Let the pair $\left( p ^ { \prime } ; q ^ { \prime } \right)$ be defined by $\binom { p ^ { \prime } } { q ^ { \prime } } = M ^ { - 1 } \binom { p } { q }$.
  \item a. Verify that $p ^ { \prime } = 2 p - 3 q$ and that $q ^ { \prime } = - p + 2 q$.\\
b. Justify that ( $p ^ { \prime } ; q ^ { \prime }$ ) is a pair of relative integers.\\
c. Recall that $p = q \sqrt { 3 }$. Show that $p ^ { \prime } = q ^ { \prime } \sqrt { 3 }$.\\
d. Show that $0 < q ^ { \prime } < q$.\\
e. Deduce that $\sqrt { 3 }$ is not a rational number.
\end{enumerate}