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.

Part A

1. 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$?
2. 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$,

$$u _ { n } ^ { 2 } - u _ { n + 1 } \times u _ { n - 1 } = ( - 1 ) ^ { n - 1 }$$
c. Then prove the conjecture made in question 1.b.

Part B

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

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

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

We are interested in the development of a bacterium. In this exercise, we model its development with the following assumptions: this bacterium has a probability of 0.3 of dying without offspring and a probability of 0.7 of dividing into two daughter bacteria. In the context of this experiment, we admit that the reproduction laws of bacteria are the same for all generations of bacteria whether they are mother or daughter. For any natural integer $n$, we call $p _ { n }$ the probability of obtaining at most $n$ descendants for a bacterium. We admit that, according to this model, the sequence $\left( p _ { n } \right)$ is defined as follows: $p _ { 0 } = 0.3$ and, for any natural integer $n$,
$$p _ { n + 1 } = 0.3 + 0.7 p _ { n } ^ { 2 }$$

1. The spreadsheet below gives approximate values of the sequence $\left( p _ { n } \right)$ a. Determine the exact values of $p _ { 1 }$ and $p _ { 2 }$ (hidden in the spreadsheet) and interpret these values in the context of the problem. b. What is the probability, rounded to $10 ^ { - 3 }$, of obtaining at least 11 generations of bacteria starting from a bacterium of this type? c. Make conjectures about the variations and convergence of the sequence $\left( p _ { n } \right)$.
2. a. Prove by induction on $n$ that, for any natural integer $n , 0 \leqslant p _ { n } \leqslant p _ { n + 1 } \leqslant 0.5$. b. Justify that the sequence $\left( p _ { n } \right)$ is convergent.
3. We call $L$ the limit of the sequence $\left( p _ { n } \right)$. a. Justify that $L$ is a solution of the equation $$0.7 x ^ { 2 } - x + 0.3 = 0$$ b. Then determine the limit of the sequence $\left( p _ { n } \right)$.

	A	B
1	$n$	$p _ { n }$
2	0	0,3
3	1
4	2
5	3	0,40769562
6	4	0,416351
7	5	0,42134371
8	6	0,42427137
9	7	0,42600433
10	8	0,427 03578
11	9	0,42765169
12	10	0,428 02018
13	11	0,42824089
14	12	0,42837318
15	13	0,42845251
16	14	0,42850009
17	15	0,42852863
18	16	0,42854575
19	17	0,42855602

The following function, written in Python language, aims to return the first $n$ terms of the sequence $\left( p _ { n } \right)$.
\begin{verbatim} def suite(n) : p= ... s=[p] for i in range (...) : p=... s.append(p) return (s) \end{verbatim}
Rewrite this function on your answer sheet, completing lines 2, 4 and 5 so that the function suite(n) returns, in the form of a list, the first $n$ terms of the sequence.

Let the sequence $(u_n)$ defined by $u_0 = 0$ and, for all $n \in \mathbb{N}$, $$u_{n+1} = 5u_n - 8n + 6.$$

1. Calculate $u_1$ and $u_2$.
2. Let $n$ be a natural number. Copy and complete the function \texttt{suite\_u} with argument \texttt{n} below, written in Python language, so that it returns the value of $u_n$. \begin{verbatim} def suite_u(n) : u = ... for i in range(1,n+1) : u = ... return u \end{verbatim}
3. a. Prove by induction that, for all $n \in \mathbb{N}$, $u_n \geqslant 2n$. b. Deduce the limit of the sequence $(u_n)$. c. Let $p \in \mathbb{N}^*$. Why can we assert that there exists at least one integer $n_0$ such that, for all natural integers $n$ satisfying $n \geqslant n_0$, $u_n \geqslant 10^p$?
4. Prove that the sequence $(u_n)$ is increasing.
5. We consider the sequence $(v_n)$, defined for all $n \in \mathbb{N}$, by $v_n = u_n - 2n + 1$. a. Below the function \texttt{suite\_u} above, we have written the function \texttt{suite\_v} below: \begin{verbatim} def suite_v(n): L = [] for i in range(n+1) : L.append(suite_u(i) - 2*i + 1) return L \end{verbatim} The command ``L.append'' allows us to add, in the last position, an element to the list $L$. When we enter \texttt{suite\_v(5)} in the console, we obtain the following display: $$\begin{aligned} & \ggg \text{suite\_v}(5) \\ & [1, 5, 25, 125, 625, 3125] \end{aligned}$$ Conjecture, for all natural integer $n$, the expression of $v_{n+1}$ as a function of $v_n$. Prove this conjecture. b. Deduce, for all natural integer $n$, the explicit form of $u_n$ as a function of $n$.

We consider the sequence $(u_n)$ defined by $u_0 = 3$ and, for every natural integer $n$, by:
$$u_{n+1} = 5u_n - 4n - 3$$

1. a. Prove that $u_1 = 12$. b. Determine $u_2$ by detailing the calculation. c. Using a calculator, conjecture the direction of variation and the limit of the sequence $(u_n)$.
2. a. Prove by induction that, for every natural integer $n$, we have: $$u_n \geqslant n + 1.$$ b. Deduce the limit of the sequence $(u_n)$.
3. We consider the sequence $(v_n)$ defined for every natural integer $n$ by: $$v_n = u_n - n - 1$$ a. Prove that the sequence $(v_n)$ is geometric. Give its common ratio and its first term $v_0$. b. Deduce, for every natural integer $n$, the expression of $v_n$ as a function of $n$. c. Deduce that for every natural integer $n$: $$u_n = 2 \times 5^n + n + 1$$ d. Deduce the direction of variation of the sequence $(u_n)$.
4. We consider the function below, written incompletely in Python language and intended to return the smallest natural integer $n$ such that $u_n \geqslant 10^7$. a. Copy the program and complete the two missing instructions. b. What is the value returned by this function? \begin{verbatim} def suite() : u = 3 n = 0 while...: u = ... n = n + 1 return n \end{verbatim}