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.

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}

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: $$\left\{\begin{aligned} u_1 &= \frac{1}{\mathrm{e}} \\ u_{n+1} &= \frac{1}{\mathrm{e}}\left(1 + \frac{1}{n}\right)u_n \text{ for all integer } n \geqslant 1. \end{aligned}\right.$$

1. Calculate the exact values of $u_2$ and $u_3$. Details of calculations should be shown.
2. We consider a function written in Python language which, for a given natural integer $n$, displays the term $u_n$. Complete lines $L_2$ and $L_4$ of this program. \begin{verbatim} L1 def u(n): L2 ................. L3 for i in range(1, n): L4 u=................. L5 return u \end{verbatim}
3. We admit that all terms of the sequence $(u_n)$ are strictly positive. a. Show that for all non-zero natural integer $n$, we have: $1 + \dfrac{1}{n} \leqslant \mathrm{e}$. b. Deduce that the sequence $(u_n)$ is decreasing. c. Is the sequence $(u_n)$ convergent? Justify your answer.
4. a. Show by induction that for all non-zero natural integer, we have: $u_n = \dfrac{n}{\mathrm{e}^n}$. b. Deduce, if it exists, the limit of the sequence $(u_n)$.

Consider a pyramid with a square base formed of identical balls stacked on top of each other:

• the $1^{\text{st}}$ level, located at the highest level, is composed of 1 ball;
• the $2^{\mathrm{nd}}$ level, just below, is composed of 4 balls;
• the $3^{\mathrm{rd}}$ level has 9 balls;
• the $n$-th level has $n^{2}$ balls.

For any integer $n \geqslant 1$, we denote by $u_{n}$ the number of balls that make up the $n$-th level from the top of the pyramid. Thus, $u_{n} = n^{2}$.

1. Calculate the total number of balls in a pyramid with 4 levels.
2. Consider the sequence $(S_{n})$ defined for any integer $n \geqslant 1$ by $$S_{n} = u_{1} + u_{2} + \ldots + u_{n}.$$ a. Calculate $S_{5}$ and interpret this result. b. Consider the pyramid function below written incompletely in Python. Copy and complete on your paper the box below so that, for any non-zero natural integer $n$, the instruction \texttt{pyramide(n)} returns the number of balls making up a pyramid with $n$ levels. \begin{verbatim} def pyramide(n) : S = 0 for i in range(1, n+1): S = ... return... \end{verbatim} c. Verify that for any natural integer $n$: $$\frac{n(n+1)(2n+1)}{6} + (n+1)^{2} = \frac{(n+1)(n+2)[2(n+1)+1]}{6}$$ d. Prove by induction that for any integer $n \geqslant 1$: $$S_{n} = \frac{n(n+1)(2n+1)}{6}.$$
3. A merchant wishes to arrange oranges in a pyramid with a square base. He has 200 oranges. How many oranges does he use to build the largest possible pyramid?

The following is a proof by mathematical induction that the inequality $$\sum _ { i = 1 } ^ { 2 n + 1 } \frac { 1 } { n + i } = \frac { 1 } { n + 1 } + \frac { 1 } { n + 2 } + \cdots + \frac { 1 } { 3 n + 1 } > 1$$ holds for all natural numbers $n$.
For a natural number $n$, let $a _ { n } = \frac { 1 } { n + 1 } + \frac { 1 } { n + 2 } + \cdots + \frac { 1 } { 3 n + 1 }$. We need to show that $a _ { n } > 1$.
(1) When $n = 1$, $a _ { 1 } = \frac { 1 } { 2 } + \frac { 1 } { 3 } + \frac { 1 } { 4 } > 1$.
(2) Assume that when $n = k$, $a _ { k } > 1$. $$\begin{aligned} & \text{When } n = k + 1 \\ & \begin{aligned} a _ { k + 1 } & = \frac { 1 } { k + 2 } + \frac { 1 } { k + 3 } + \cdots + \frac { 1 } { 3 k + 4 } \\ & = a _ { k } + \left( \frac { 1 } { 3 k + 2 } + \frac { 1 } { 3 k + 3 } + \frac { 1 } { 3 k + 4 } \right) \end{aligned} \end{aligned}$$ On the other hand, $( 3 k + 2 ) ( 3 k + 4 )$ $\square$ (b) $( 3 k + 3 ) ^ { 2 }$, so $$\frac { 1 } { 3 k + 2 } + \frac { 1 } { 3 k + 4 } > \text{(c)}$$ Since $a _ { k } > 1$, $$a _ { k + 1 } > a _ { k } + \left( \frac { 1 } { 3 k + 3 } + \text{(c)} \right) \text{(a)} > 1$$ Therefore, by (1) and (2), $a _ { n } > 1$ for all natural numbers $n$.
What are the correct values for (a), (b), and (c) in the above proof? [3 points]

(a)	(b)	(c)
(1) $\frac { 1 } { k + 1 }$	$>$	$\frac { 2 } { 3 k + 3 }$
(2) $\frac { 1 } { k + 1 }$	$<$	$\frac { 2 } { 3 k + 3 }$
(3) $\frac { 1 } { k + 1 }$	$<$	$\frac { 4 } { 3 k + 3 }$
(4) $\frac { 2 } { k + 1 }$	$>$	$\frac { 4 } { 3 k + 3 }$
(5) $\frac { 2 } { k + 1 }$	$<$	$\frac { 1 } { k + 1 }$

The following is a proof by mathematical induction that the inequality $$\sum _ { i = 1 } ^ { 2 n + 1 } \frac { 1 } { n + i } = \frac { 1 } { n + 1 } + \frac { 1 } { n + 2 } + \cdots + \frac { 1 } { 3 n + 1 } > 1$$ holds for all natural numbers $n$.
$\langle$Proof$\rangle$ For a natural number $n$, let $a _ { n } = \frac { 1 } { n + 1 } + \frac { 1 } { n + 2 } + \cdots + \frac { 1 } { 3 n + 1 }$. It suffices to show that $a _ { n } > 1$.
(1) When $n = 1$, $a _ { 1 } = \frac { 1 } { 2 } + \frac { 1 } { 3 } + \frac { 1 } { 4 } > 1$.
(2) Assume that $a _ { k } > 1$ when $n = k$. $$\begin{aligned} & \text{When } n = k + 1, \\ & \begin{aligned} a _ { k + 1 } & = \frac { 1 } { k + 2 } + \frac { 1 } { k + 3 } + \cdots + \frac { 1 } { 3 k + 4 } \\ & = a _ { k } + \left( \frac { 1 } { 3 k + 2 } + \frac { 1 } { 3 k + 3 } + \frac { 1 } { 3 k + 4 } \right) \end{aligned} \end{aligned}$$ □
On the other hand, $( 3 k + 2 ) ( 3 k + 4 )$ (나) $( 3 k + 3 ) ^ { 2 }$, so $$\frac { 1 } { 3 k + 2 } + \frac { 1 } { 3 k + 4 } > \text{ (다) }$$ Since $a _ { k } > 1$, $$a _ { k + 1 } > a _ { k } + \left( \frac { 1 } { 3 k + 3 } + \text{ (다) } \right) \text{ (가) } > 1$$ Therefore, by (1) and (2), $a _ { n } > 1$ for all natural numbers $n$.
What are the correct expressions for (가), (나), and (다) in the above proof? [3 points]

(가)	(나)	(다)
(1) $\frac { 1 } { k + 1 }$	$<$	$\frac { 2 } { 3 k + 3 }$
(2) $\frac { 1 } { k + 1 }$	$>$	$\frac { 2 } { 3 k + 3 }$
(3) $\frac { 1 } { k + 1 }$	$<$	$\frac { 2 } { 3 k + 4 }$
(4) $\frac { 2 } { k + 1 }$	$>$	$\frac { 2 } { 3 k + 4 }$
(5) $\frac { 2 } { k + 1 }$	$<$	$\frac { 2 } { 3 k + 3 }$

The following proves by mathematical induction that for all natural numbers $n$, $$\sum _ { k = 1 } ^ { n } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { n } \right) = \frac { n ( 5 n + 3 ) } { 4 }$$ holds.
(1) When $n = 1$, (left side) $= 2$, (right side) $= 2$, so the given equation holds.
(2) Assume that when $n = m$, the equation holds: $$\begin{aligned} & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { m } \right) \\ = & \frac { m ( 5 m + 3 ) } { 4 } \end{aligned}$$ Now we show that it holds when $n = m + 1$. $$\begin{aligned} & \sum _ { k = 1 } ^ { m + 1 } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) + \frac { \text { (가) } } { m + 1 } \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { \sqrt { \text { (나) } } } \right) \\ \quad & \quad + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) + \frac { \text { (가) } } { m + 1 } \\ = & \frac { m ( 5 m + 3 ) } { 4 } + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m + 1 } \text { (다) } \\ = & \frac { ( m + 1 ) ( 5 m + 8 ) } { 4 } \end{aligned}$$ Therefore, the equation also holds when $n = m + 1$. Thus, the given equation holds for all natural numbers $n$. What are the correct values for (가), (나), and (다) in the above proof? [4 points]

	(가)	(나)	(다)
(1)	$5 m - 3$	$m$	$5 k + 2$
(2)	$5 m - 3$	$m + 1$	$5 k + 2$
(3)	$5 m + 2$	$m$	$5 k - 3$
(4)	$5 m + 2$	$m$	$5 k + 2$
(5)	$5 m + 2$	$m + 1$	$5 k - 3$

The following is a proof by mathematical induction that for all natural numbers $n$,
$$\sum _ { k = 1 } ^ { n } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { n } \right) = \frac { n ( 5 n + 3 ) } { 4 }$$
holds.

(1) When $n = 1$, (left side) $= 2$, (right side) $= 2$, so the given equation holds.
(2) Assume that the equation holds when $n = m$:
$$\begin{aligned} & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { m } \right) \\ = & \frac { m ( 5 m + 3 ) } { 4 } \end{aligned}$$
Now we show that it holds when $n = m + 1$.
$$\begin{aligned} & \sum _ { k = 1 } ^ { m + 1 } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) + \frac { \text { (가) } } { m + 1 } \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { \sqrt { \text { (나) } } } \right) \\ \quad & \quad + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) + \frac { \text { (가) } } { m + 1 } \\ = & \frac { m ( 5 m + 3 ) } { 4 } + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m + 1 } \text { (다) } \\ = & \frac { ( m + 1 ) ( 5 m + 8 ) } { 4 } \end{aligned}$$
Therefore, the equation also holds when $n = m + 1$. Thus, the given equation holds for all natural numbers $n$.
What should be filled in for (가), (나), and (다) in the above proof? [4 points]

	(가)	(나)	(다)
(1)	$5 m - 3$	$m$	$5 k + 2$
(2)	$5 m - 3$	$m + 1$	$5 k + 2$
(3)	$5 m + 2$	$m$	$5 k - 3$
(4)	$5 m + 2$	$m$	$5 k + 2$
(5)	$5 m + 2$	$m + 1$	$5 k - 3$

The following proves by mathematical induction that for all natural numbers $n$,
$$\left( 1 ^ { 2 } + 1 \right) \cdot 1 ! + \left( 2 ^ { 2 } + 1 \right) \cdot 2 ! + \cdots + \left( n ^ { 2 } + 1 \right) \cdot n ! = n \cdot ( n + 1 ) !$$
holds.

(1) When $n = 1$, (left side) = 2, (right side) = 2, so the given equation holds.
(2) Assuming it holds when $n = k$,
$$\begin{aligned} \left( 1 ^ { 2 } + 1 \right) \cdot 1 ! & + \left( 2 ^ { 2 } + 1 \right) \cdot 2 ! + \cdots \\ & + \left( k ^ { 2 } + 1 \right) \cdot k ! = k \cdot ( k + 1 ) ! \end{aligned}$$
We show that it holds when $n = k + 1$.
$$\begin{aligned} \left( 1 ^ { 2 } + 1 \right) \cdot 1 ! + \left( 2 ^ { 2 } + 1 \right) \cdot 2 ! + \cdots + \left( k ^ { 2 } + 1 \right) \cdot k ! + \left\{ ( k + 1 ) ^ { 2 } + 1 \right\} \cdot ( k + 1 ) ! \\ = ( \text{ (A) } ) + \left\{ ( k + 1 ) ^ { 2 } + 1 \right\} \cdot ( k + 1 ) ! \\ = ( k + 1 ) \cdot \text{((B))} \cdot ( k + 1 ) ! \\ = \text{ ((C)) } \end{aligned}$$
Therefore, it also holds when $n = k + 1$. Thus, the given equation holds for all natural numbers $n$.
Which expressions are correct for (A), (B), and (C) in the above proof? [3 points]

	$\underline { ( \text{ (A) } ) }$	$\underline { ( \text{ (B) } ) }$	$\underline { ( \text{ (C) } ) }$
$( 1 ) k \cdot ( k + 1 ) !$	$k ^ { 2 } + 2 k + 1$	$( k + 1 ) !$
$( 2 ) k \cdot ( k + 1 ) !$	$k ^ { 2 } + 3 k + 2$	$( k + 2 ) !$
$( 3 ) k \cdot ( k + 1 ) !$	$k ^ { 2 } + 3 k + 2$	$( k + 1 ) !$
$( 4 ) ( k + 1 ) \cdot ( k + 1 ) !$	$k ^ { 2 } + 3 k + 2$	$( k + 2 ) !$
$( 5 ) ( k + 1 ) \cdot ( k + 1 ) !$	$k ^ { 2 } + 2 k + 1$	$( k + 1 ) !$

The sequence $\left\{ a _ { n } \right\}$ satisfies
$$\left\{ \begin{array} { l } a _ { 1 } = \frac { 1 } { 2 } \\ ( n + 1 ) ( n + 2 ) a _ { n + 1 } = n ^ { 2 } a _ { n } \quad ( n = 1,2,3 , \cdots ) \end{array} \right.$$
The following is a proof by mathematical induction that for all natural numbers $n$,
$$\sum _ { k = 1 } ^ { n } a _ { k } = \sum _ { k = 1 }^{n} \frac { 1 } { k ^ { 2 } } - \frac { n } { n + 1 }$$
holds. $\langle$Proof$\rangle$
(1) When $n = 1$, (left side) $= \frac { 1 } { 2 }$, (right side) $= 1 - \frac { 1 } { 2 } = \frac { 1 } { 2 }$, so (*) holds.
(2) Assume (*) holds when $n = m$: $$\sum _ { k = 1 } ^ { m } a _ { k } = \sum _ { k = 1 } ^ { m } \frac { 1 } { k ^ { 2 } } - \frac { m } { m + 1 }$$
Now show that (*) holds when $n = m + 1$.
$$\begin{aligned} & \sum _ { k = 1 } ^ { m + 1 } a _ { k } = \sum _ { k = 1 } ^ { m } \frac { 1 } { k ^ { 2 } } - \frac { m } { m + 1 } + a _ { m + 1 } \\ = & \sum _ { k = 1 } ^ { m } \frac { 1 } { k ^ { 2 } } - \frac { m } { m + 1 } + \square \text { (a) } a _ { m } \\ = & \sum _ { k = 1 } ^ { m } \frac { 1 } { k ^ { 2 } } - \frac { m } { m + 1 } \\ & \quad + \frac { m ^ { 2 } } { ( m + 1 ) ( m + 2 ) } \cdot \frac { ( m - 1 ) ^ { 2 } } { m ( m + 1 ) } \cdot \cdots \cdot \frac { 1 ^ { 2 } } { 2 \cdot 3 } a _ { 1 } \end{aligned}$$
Therefore, (*) also holds when $n = m + 1$. Thus, (*) holds for all natural numbers $n$.
Which expressions are correct for (a), (b), and (c) in the above proof? [3 points]
(1) $\dfrac{\text{(a)}}{m} \quad \dfrac{\text{(b)}}{(m+1)(m+2)} \quad \dfrac{\text{(c)}}{\frac{1}{(m+1)^2(m+2)}} \quad \dfrac{1}{(m+1)(m+2)^2}$
(2) $\dfrac{m}{(m+1)(m+2)} \quad \dfrac{m}{(m+1)^2(m+2)} \quad \dfrac{1}{(m+1)(m+2)}$
(3) $\dfrac{m^2}{(m+1)(m+2)} \quad \dfrac{1}{(m+1)^2(m+2)} \quad \dfrac{1}{(m+1)(m+2)^2}$
(4) $\dfrac{m^2}{(m+1)(m+2)} \quad \dfrac{1}{(m+1)^2(m+2)} \quad \dfrac{1}{(m+1)(m+2)}$
(5) $\dfrac{m^2}{(m+1)(m+2)} \quad \dfrac{m}{(m+1)^2(m+2)} \quad \dfrac{1}{(m+1)(m+2)^2}$

The sequence $\left\{ a _ { n } \right\}$ satisfies $a _ { 1 } = 3 , a _ { n + 1 } = 3 a _ { n } - 4 n$ .
(1) Calculate $a _ { 2 } , a _ { 3 }$ , conjecture the general term formula of $\left\{ a _ { n } \right\}$ and prove it;
(2) Find the sum $S _ { n }$ of the first $n$ terms of the sequence $\left\{ 2 ^ { n } a _ { n } \right\}$ .

Given that the domain of function $f ( x )$ is $\mathbb { R }$ , $f ( x ) > f ( x - 1 ) + f ( x - 2 )$ , and when $x < 3$ , $f ( x ) = x$ , then the following conclusion that must be correct is
A. $f ( 10 ) > 100$
B. $f ( 20 ) > 1000$
C. $f ( 10 ) < 1000$
D. $f ( 20 ) < 10000$

We prove Broyden's theorem by induction on the dimension. We assume the result holds up to rank $n - 1$ and we write $O$ in the form of a block matrix $$O = \left( \begin{array} { l l } P & r \\ { } ^ { t } q & \alpha \end{array} \right)$$ where $P \in M _ { n - 1 } ( \mathbb { R } )$ and thus $r , q \in \mathbb { R } ^ { n - 1 }$ and $\alpha \in \mathbb { R }$.
Treat the case $| \alpha | = 1$.

We fix a natural number $p$ greater than or equal to 2. Show that every upper triangular and invertible matrix admits at least one upper triangular $p$-th root.
One may prove by induction on $n \geqslant 1$ the following property: $$\forall B \in \mathcal { T } _ { n } ( \mathbb { C } ) \cap \mathrm { GL } _ { n } ( \mathbb { C } ) , \quad \exists A \in \mathcal { T } _ { n } ( \mathbb { C } ) \quad \text { such that } \left\{ \begin{array} { l } A ^ { p } = B \\ \forall ( i , j ) \in \llbracket 1 , n \rrbracket ^ { 2 } , \frac { a _ { i , i } } { a _ { j , j } } \notin \mathcal { V } _ { p } \end{array} \right.$$

We fix a symplectic form $\omega$ on $E$. Show by induction that there exists a basis $\widetilde { \mathcal { B } }$ of $E$ such that $$\operatorname { Mat } _ { \widetilde { \mathcal { B } } } ( \omega ) = \left( \begin{array} { c c c c } J _ { 2 } & 0 & \cdots & 0 \\ 0 & J _ { 2 } & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & J _ { 2 } \end{array} \right)$$

Prove by induction that, for all integers $n \in \mathbb{N}^{*}$, there exists a unique polynomial $R_{n} \in \mathbb{R}_{n}[X]$ such that, for all $x \in ]-1,1[$, $$\sum_{p=1}^{+\infty} p^{n} x^{p} = \frac{R_{n}(x)}{(1-x)^{n+1}}$$

For all $n$ in $\mathbb{N}$, determine the degree of $T_n$, then show that $\left(T_k\right)_{0 \leqslant k \leqslant n}$ is a basis of $\mathbb{C}_n[X]$.
The sequence of polynomials $\left(T_n\right)_{n \in \mathbb{N}}$ is defined by $T_0 = 1, T_1 = X$ and $\forall n \in \mathbb{N}, T_{n+2} = 2X T_{n+1} - T_n$.

For all $n$ in $\mathbb{N}$, determine the degree of $T_n$, then show that $\left(T_k\right)_{0 \leqslant k \leqslant n}$ is a basis of $\mathbb{C}_n[X]$.
The sequence of polynomials $\left(T_n\right)_{n \in \mathbb{N}}$ is defined by $T_0 = 1, T_1 = X$ and $\forall n \in \mathbb{N}, T_{n+2} = 2X T_{n+1} - T_n$.

Let $I$ be an interval of $\mathbf{R}$. Let $f : I \rightarrow \mathbf{R}$ be a convex function. Show that, for all $p \in \mathbf{N}^\star$, for all $(\lambda_1, \ldots, \lambda_p) \in (\mathbf{R}_+)^p$ such that $\sum_{i=1}^p \lambda_i = 1$ and for all $(x_1, \ldots, x_p) \in I^p$, we have: $$f\left(\sum_{i=1}^p \lambda_i x_i\right) \leq \sum_{i=1}^p \lambda_i f(x_i)$$ Hint: You may proceed by induction on $p$.

Let $I$ be an interval of $\mathbf { R }$. Let $f : I \rightarrow \mathbf { R }$ be a convex function. Show that, for all $p \in \mathbf { N } ^ { \star }$, for all $\left( \lambda _ { 1 } , \ldots , \lambda _ { p } \right) \in \left( \mathbf { R } _ { + } \right) ^ { p }$ such that $\sum _ { i = 1 } ^ { p } \lambda _ { i } = 1$ and for all $\left( x _ { 1 } , \ldots , x _ { p } \right) \in I ^ { p }$, we have:
$$f \left( \sum _ { i = 1 } ^ { p } \lambda _ { i } x _ { i } \right) \leq \sum _ { i = 1 } ^ { p } \lambda _ { i } f \left( x _ { i } \right)$$
Hint: You may proceed by induction on $p$.

Let $M \in S_n^+(\mathbf{R})$ be a non-zero matrix. Show the inequality $\frac{\operatorname{Tr}(M)}{n} \geq \operatorname{det}^{1/n}(M)$.
Hint: You may show that $x \mapsto -\ln(x)$ is convex on $\mathbf{R}_+^\star$.

Let $M \in S _ { n } ^ { + } ( \mathbf { R } )$ be a non-zero matrix. Show the inequality $\frac { \operatorname { Tr } ( M ) } { n } \geq \operatorname { det } ^ { 1 / n } ( M )$.
Hint: You may show that $x \mapsto - \ln ( x )$ is convex on $\mathbf { R } _ { + } ^ { \star }$.

Let $X$ be a non-empty finite set and $c : X \rightarrow \{0,1\}^+$ an injective application. We say that $c$ is a binary code on $X$. We further assume that $c$ is a prefix code, that is, for all $x \neq y$ in $X$, $c(x)$ is not a prefix of $c(y)$. We define $\bar{c} : X \rightarrow \{0,1\}^*$ such that for all $x \in X$, $c(x) = c(x)_1 \cdot \bar{c}(x)$ where $c(x)_1$ is the first element of the word $c(x)$.
(a) Verify that for all $x \neq y \in X$, if $c(x)_1 = c(y)_1$ then $\bar{c}(x) \neq \bar{c}(y)$ and $\bar{c}(x)$ is not a prefix of $\bar{c}(y)$.
(b) For $a \in \{0,1\}$ we denote $X_a = \{x \in X \mid c(x)_1 = a\}$. Show that if $X_a$ contains at least two elements, then the restriction of $\bar{c}$ to $X_a$ is a prefix code on $X_a$.
(c) Deduce that $\sum_{x \in X} 2^{-|c(x)|} \leq 1$. (Hint: One may decompose the sum into a sum over $X_0$ and $X_1$ and reason by induction on $L(c) = \max\{|c(x)| \mid x \in X\}$)