Consider the matrix $M = \left( \begin{array} { l l l } 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right)$.\\
Let $\left( a _ { n } \right)$ and $\left( b _ { n } \right)$ be two sequences of integers defined by:
$$a _ { 1 } = 1 , b _ { 1 } = 0 \text { and for every non-zero natural number } n \begin{cases} a _ { n + 1 } & = a _ { n } + b _ { n } \\ b _ { n + 1 } & = 2 a _ { n } \end{cases}$$

\begin{enumerate}
  \item Calculate $a _ { 2 } , b _ { 2 } , a _ { 3 }$ and $b _ { 3 }$.
  \item Give $M ^ { 2 }$.\\
Show that $M ^ { 2 } = M + 2 I$ where $I = \left( \begin{array} { l l l } 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)$ denotes the identity matrix of order 3.\\
It is admitted that for every non-zero natural number $n , M ^ { n } = a _ { n } M + b _ { n } I$, where ( $a _ { n }$ ) and ( $b _ { n }$ ) are the previously defined sequences.
  \item Let $A = \left( \begin{array} { l l } 1 & 1 \\ 2 & 0 \end{array} \right)$ and for every non-zero natural number $n$, let $X _ { n }$ denote the matrix $\binom { a _ { n } } { b _ { n } }$.\\
Let $P = \left( \begin{array} { c c } 1 & 1 \\ 1 & - 2 \end{array} \right)$.\\
a. Verify that, for every non-zero natural number $n , X _ { n + 1 } = A X _ { n }$.\\
b. Without justification, express, for every integer $n \geqslant 2 , X _ { n }$ in terms of $A ^ { n - 1 }$ and $X _ { 1 }$.\\
c. Justify that $P$ is invertible with inverse $\left( \begin{array} { c c } \frac { 2 } { 3 } & \frac { 1 } { 3 } \\ \frac { 1 } { 3 } & - \frac { 1 } { 3 } \end{array} \right)$.\\
Let $P ^ { - 1 }$ denote this matrix.\\
d. Verify that $P ^ { - 1 } A P$ is a diagonal matrix $D$ which you will specify.\\
e. Prove by induction that for every non-zero natural number $n , A ^ { n } = P D ^ { n } P ^ { - 1 }$.\\
f. It is admitted that for every integer $n \geqslant 1$:
$$A ^ { n - 1 } = \left( \begin{array} { l l } 
\frac { 1 } { 3 } \times 2 ^ { n } + \frac { 1 } { 3 } \times ( - 1 ) ^ { n - 1 } & \frac { 1 } { 3 } \times 2 ^ { n - 1 } + \frac { 1 } { 3 } \times ( - 1 ) ^ { n } \\
\frac { 1 } { 3 } \times 2 ^ { n } - \frac { 2 } { 3 } \times ( - 1 ) ^ { n - 1 } & \frac { 1 } { 3 } \times 2 ^ { n - 1 } - \frac { 2 } { 3 } \times ( - 1 ) ^ { n }
\end{array} \right)$$
Deduce that for every integer $n \geqslant 1 , a _ { n } = \frac { 1 } { 3 } \times \left( 2 ^ { n } + ( - 1 ) ^ { n - 1 } \right)$.
  \item Prove that, for every natural number $k , 2 ^ { 4 k } - 1 \equiv 0$ modulo 5.
  \item Let $n$ be a non-zero natural number and a multiple of 4.\\
a. Show that $3 a _ { n }$ is divisible by 5.\\
b. Deduce that $a _ { n }$ is divisible by 5.
\end{enumerate}