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

\textbf{Part A}\\
We consider the sequence $(u_{n})$ defined by: $u_{0} = 1,\ u_{1} = 6$ and, for every natural number $n$:
$$u_{n+2} = 6u_{n+1} - 8u_{n}$$

\begin{enumerate}
  \item Calculate $u_{2}$ and $u_{3}$.
  \item We consider the matrix $A = \left(\begin{array}{cc} 0 & 1 \\ -8 & 6 \end{array}\right)$ and the column matrix $U_{n} = \binom{u_{n}}{u_{n+1}}$. Show that, for every natural number $n$, we have: $U_{n+1} = A U_{n}$.
  \item We also consider the matrices $B = \left(\begin{array}{cc} 2 & -0.5 \\ 4 & -1 \end{array}\right)$ and $C = \left(\begin{array}{cc} -1 & 0.5 \\ -4 & 2 \end{array}\right)$.\\
a. Show by induction that, for every natural number $n$, we have: $A^{n} = 2^{n}B + 4^{n}C$.\\
b. We admit that, for every natural number $n$, we have: $U_{n} = A^{n}U_{0}$. Show that, for every natural number $n$, we have: $u_{n} = 2 \times 4^{n} - 2^{n}$.
\end{enumerate}

\textbf{Part B}\\
We say that a natural number $N$ is perfect when the sum of its (positive) divisors equals $2N$. For example, 6 is a perfect number because its divisors are $1, 2, 3$ and 6 and we have: $1 + 2 + 3 + 6 = 12 = 2 \times 6$. In this part, we seek perfect numbers among the terms of the sequence $(u_{n})$ studied in Part A.

\begin{enumerate}
  \item Verify that, for every natural number $n$, we have: $u_{n} = 2^{n}p_{n}$ with $p_{n} = 2^{n+1} - 1$.
  \item We consider the following algorithm where $N, S, U, P$ and $K$ are natural numbers.
\end{enumerate}