(Candidates who followed the specialization course)
Consider the sequence defined by its first term $u _ { 0 } = 3$ and, for every natural number $n$, by
$$u _ { n + 1 } = 2 u _ { n } + 6$$

1. Prove that, for every natural number $n$, $$u _ { n } = 9 \times 2 ^ { n } - 6$$
2. Prove that, for every integer $n \geqslant 1 , u _ { n }$ is divisible by 6. Define the sequence of integers ( $\nu _ { n }$ ) by, for every natural number $n \geqslant 1 , \nu _ { n } = \frac { u _ { n } } { 6 }$.
3. Consider the statement: ``for every non-zero natural number $n$, $v _ { n }$ is a prime number''. Indicate whether this statement is true or false by justifying the answer.
4. a. Prove that, for every integer $n \geqslant 1 , v _ { n + 1 } - 2 v _ { n } = 1$. b. Deduce that, for every integer $n \geqslant 1 , v _ { n }$ and $v _ { n + 1 }$ are coprime. c. Deduce, for every integer $n \geqslant 1$, the GCD of $u _ { n }$ and $u _ { n + 1 }$.
5. a. Verify that $2 ^ { 4 } \equiv 1 [ 5 ]$. b. Deduce that if $n$ is of the form $4 k + 2$ with $k$ a natural number, then $u _ { n }$ is divisible by 5. c. Is the number $u _ { n }$ divisible by 5 for the other values of the natural number $n$? Justify.

2. We consider the sequence $\left( w _ { n } \right)$ defined by:
$$w _ { 0 } = 0 \text { and, for every natural number } n , w _ { n + 1 } = 3 w _ { n } - 2 n + 3 .$$
Statement 2: For every natural number $n , w _ { n } \geq n$.

Prove that $$\frac { 2 } { 0 ! + 1 ! + 2 ! } + \frac { 3 } { 1 ! + 2 ! + 3 ! } + \cdots + \frac { n } { ( n - 2 ) ! + ( n - 1 ) ! + n ! } = 1 - \frac { 1 } { n ! }$$

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 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) Assume 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}$$ Now 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+1 ) ^ { 2 } + 1 \right) \cdot ( k + 1 ) ! \\ = k \cdot ( k + 1 ) ! + \left\{ ( k + 1 ) ^ { 2 } + 1 \right\} \cdot ( k + 1 ) ! \\ = ( \text{(a)} ) \\ = ( 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 $$\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.
(1) When $n = 1$, (left side) $= \frac { 1 } { 2 }$, (right side) $= 1 - \frac { 1 } { 2 } = \frac { 1 } { 2 }$, so (*) holds.
(2) Assume that (*) 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, for all natural numbers $n$, (*) holds.
What are the expressions that should be filled in for (a), (b), and (c) in the above proof? [3 points]
(1) $\dfrac{\text{(a)}}{\dfrac{m}{(m+1)(m+2)}} \quad \dfrac{\text{(b)}}{1} \quad \dfrac{\text{(c)}}{(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 following is a proof by mathematical induction that the equality $$\sum _ { k = 0 } ^ { n } \frac { { } _ { n } \mathrm { C } _ { k } } { { } _ { n + 4 } \mathrm { C } _ { k } } = \frac { n + 5 } { 5 }$$ holds for all natural numbers $n$.
(1) When $n = 1$, $$( \text { LHS } ) = \frac { { } _ { 1 } \mathrm { C } _ { 0 } } { { } _ { 5 } \mathrm { C } _ { 0 } } + \frac { { } _ { 1 } \mathrm { C } _ { 1 } } { { } _ { 5 } \mathrm { C } _ { 1 } } = \frac { 6 } { 5 } , ( \text { RHS } ) = \frac { 1 + 5 } { 5 } = \frac { 6 } { 5 }$$ so the given equality holds.
(2) Assume that when $n = m$, the equality $$\sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } } = \frac { m + 5 } { 5 }$$ holds. When $n = m + 1$, $$\sum _ { k = 0 } ^ { m + 1 } \frac { { } _ { m + 1 } \mathrm { C } _ { k } } { { } _ { m + 5 } \mathrm { C } _ { k } } = \text { (가) } + \sum _ { k = 0 } ^ { m } \frac { { } _ { m + 1 } \mathrm { C } _ { k + 1 } } { { } _ { m + 5 } \mathrm { C } _ { k + 1 } }$$ For a natural number $l$, $${ } _ { l + 1 } \mathrm { C } _ { k + 1 } = \text { (나) } \cdot { } _ { l } \mathrm { C } _ { k } \quad ( 0 \leqq k \leqq l )$$ so $$\sum _ { k = 0 } ^ { m } \frac { { } _ { m + 1 } \mathrm { C } _ { k + 1 } } { { } _ { m + 5 } \mathrm { C } _ { k + 1 } } = \text { (다) } \cdot \sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } }$$ Therefore, $$\begin{aligned} \sum _ { k = 0 } ^ { m + 1 } \frac { { } _ { m + 1 } \mathrm { C } _ { k } } { { } _ { m + 5 } \mathrm { C } _ { k } } & = \text { (가) } + \text { (다) } \cdot \sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } } \\ & = \frac { m + 6 } { 5 } \end{aligned}$$ Thus, the given equality holds for all natural numbers $n$.
What are the correct values for (가), (나), and (다) in the above process? [3 points] $\begin{array} { l l l l } & \text { (가) } & \text { (나) } & \text { (다) } \\ \text { (1) } & 1 & \frac { l + 2 } { k + 2 } & \frac { m + 4 } { m + 4 } \end{array}$
(2) $1 \quad \frac { l + 1 } { k + 1 } \quad \frac { m + 1 } { m + 5 }$
(3) $1 \quad \frac { l + 1 } { k + 1 } \quad \frac { m + 1 } { m + 4 }$
(4) $m + 1 \quad \frac { l + 1 } { k + 1 } \quad \frac { m + 1 } { m + 5 }$
(5) $m + 1 \quad \frac { l + 2 } { k + 2 } \quad \frac { m + 1 } { m + 4 }$

The following is a proof by mathematical induction that the equality $$\sum _ { k = 0 } ^ { n } \frac { { } _ { n } \mathrm { C } _ { k } } { { } _ { n + 4 } \mathrm { C } _ { k } } = \frac { n + 5 } { 5 }$$ holds for all natural numbers $n$.

(1) When $n = 1$, $$( \text { Left side } ) = \frac { { } _ { 1 } \mathrm { C } _ { 0 } } { { } _ { 5 } \mathrm { C } _ { 0 } } + \frac { { } _ { 1 } \mathrm { C } _ { 1 } } { { } _ { 5 } \mathrm { C } _ { 1 } } = \frac { 6 } { 5 } , ( \text { Right side } ) = \frac { 1 + 5 } { 5 } = \frac { 6 } { 5 }$$ so the given equality holds.
(2) Assume that when $n = m$, the equality $$\sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } } = \frac { m + 5 } { 5 }$$ holds. When $n = m + 1$, $$\sum _ { k = 0 } ^ { m + 1 } \frac { m + 1 } { { } _ { m + 5 } \mathrm { C } _ { k } } = \text { (가) } + \sum _ { k = 0 } ^ { m } \frac { m + 1 } { { } _ { m + 5 } \mathrm { C } _ { k + 1 } }$$ For a natural number $l$, $${ } _ { l + 1 } \mathrm { C } _ { k + 1 } = \text { (나) } \cdot { } _ { l } \mathrm { C } _ { k } \quad ( 0 \leqq k \leqq l )$$ so $$\sum _ { k = 0 } ^ { m } \frac { m + 1 } { { } _ { m + 5 } \mathrm { C } _ { k + 1 } } = \text { (다) } \cdot \sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } }$$ Therefore, $$\begin{aligned} \sum _ { k = 0 } ^ { m + 1 } \frac { m + 1 } { { } _ { m + 5 } \mathrm { C } _ { k } } & = \text { (가) } + \text { (다) } \cdot \sum _ { k = 0 } ^ { m } \frac { { } _ { m } \mathrm { C } _ { k } } { { } _ { m + 4 } \mathrm { C } _ { k } } \\ & = \frac { m + 6 } { 5 } \end{aligned}$$ Thus, the given equality holds for all natural numbers $n$.
Which of the following are correct for (가), (나), and (다)? [3 points]

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

23. Given the set $X = \{ 1,2,3 \} , Y _ { n } = \{ 1,2,3 , m , n \} \left( n \in N ^ { * } \right)$, let $S _ { n } = \left\{ ( a , b ) \mid a \text{ divides } b \text{ or } b \text{ divides } a , a \in X , b \in Y _ { n } \right\}$, and let $f ( n )$ denote the number of elements in set $S _ { n }$.
(1) Write out the value of $f ( 6 )$;
(2) When $n \geq 6$, write out the expression for $f ( n )$ and prove it using mathematical induction.

Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$. The recurrence relation $S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$ holds for all strictly positive integers $k$ and $n$.
I.D.1) Write a recursive Python function to compute the number $S ( n , k )$, by direct application of the formula established in question I.C.
I.D.2) Show that, for $n \geqslant 1$, the computation of $S ( n , k )$ by this recursive function requires at least $\binom { n } { k }$ operations (sums or products).

We denote by $n$ the integer part of $\frac{N}{2}$. We have $R_N(X) = U_N(X)^2$. We now assume that $U_{N}$ is odd.
For $j \in \mathbb{N}$, the polynomials $P_j$ are defined by $P_{j}(X) = \frac{1}{2^{j} j!} \frac{d^{j}}{dX^{j}}\left[(X^{2}-1)^{j}\right]$, and $g_j = \int_{-1}^{1} P_j(x)^2\,dx$.
Express $a_{N}$ again in terms of the $g_{\ell}$.

We denote by $n$ the integer part of $\frac{N}{2}$. For $j \in \mathbb{N}$, the polynomials $P_j$ are defined by $P_{j}(X) = \frac{1}{2^{j} j!} \frac{d^{j}}{dX^{j}}\left[(X^{2}-1)^{j}\right]$, and $g_j = \int_{-1}^{1} P_j(x)^2\,dx$.
Discuss, depending on the parity of $n$, the value of $a_{N}$. We will give its explicit value.

We denote by $n$ the integer part of $\frac{N}{2}$. For $j \in \mathbb{N}$, the polynomials $P_j$ are defined by $P_{j}(X) = \frac{1}{2^{j} j!} \frac{d^{j}}{dX^{j}}\left[(X^{2}-1)^{j}\right]$.
Give the explicit formula for $R_{N}$, in terms of the polynomials $P_{j}$.

Let $n$ be a non-zero natural number. Show by induction $$\forall k \in \llbracket 0, 2^n - 1 \rrbracket, \quad k \in \operatorname{Im} \Phi_n$$ where $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.

Let $k$ be a non-negative integer. We define the function $f _ { k }$ from the interval $[ - 1,1 ]$ to itself by $f _ { k } ( x ) = \cos ( k \arccos x )$.
a) Expand the expression $f _ { k + 1 } ( x ) + f _ { k - 1 } ( x )$, and deduce the relation $$\forall x \in [ - 1,1 ] \quad f _ { k + 1 } ( x ) = 2 x f _ { k } ( x ) - f _ { k - 1 } ( x )$$
b) Deduce that $f _ { k }$ identifies on $[ - 1,1 ]$ with a polynomial $T _ { k }$, of degree $k$, with the same parity as $k$.

Using the recurrence relation $2\beta_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \beta_k \beta_{n-k}$ and the analogous relation $2\alpha_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \alpha_k \alpha_{n-k}$ with $\alpha_0 = \beta_0 = 1$, deduce that $\beta_n = \alpha_n$ for every $n \in \mathbb{N}$.

Show that, for all $n \in \mathbb{N}$ and $\theta \in \mathbb{R}$, $T_n(\cos\theta) = \cos(n\theta)$.
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 $\left( U _ { n } \right) _ { n \in \mathbb { N } }$ be the sequence of polynomials defined by $U _ { 0 } = 1 , U _ { 1 } = X - 1$ and $\forall n \in \mathbb { N } , U _ { n + 2 } = ( X - 2 ) U _ { n + 1 } - U _ { n }$. For all $n \in \mathbb { N }$, show that $U _ { n }$ is monic of degree $n$, and determine the value of $U _ { n } ( 0 )$.

Let $\left( U _ { n } \right) _ { n \in \mathbb { N } }$ be the sequence of polynomials defined by $U _ { 0 } = 1 , U _ { 1 } = X - 1$ and $\forall n \in \mathbb { N } , U _ { n + 2 } = ( X - 2 ) U _ { n + 1 } - U _ { n }$, with the inner product $$( P \mid Q ) = \frac { 2 } { \pi } \int _ { 0 } ^ { 1 } P ( 4 x ) Q ( 4 x ) \frac { \sqrt { 1 - x } } { \sqrt { x } } \mathrm { ~d} x .$$ Deduce that $\left( U _ { n } \right) _ { n \in \mathbb { N } }$ is an orthogonal system and that, for all $n \in \mathbb { N } , \left\| U _ { n } \right\| = 1$. To calculate the value of $( U _ { m } \mid U _ { n } )$, one may perform the change of variable $x = \cos ^ { 2 } \theta$.

For all $n \in \mathbb { N }$, set $\mu _ { n } = \left( X ^ { n } \mid 1 \right)$ with the inner product $$( P \mid Q ) = \frac { 2 } { \pi } \int _ { 0 } ^ { 1 } P ( 4 x ) Q ( 4 x ) \frac { \sqrt { 1 - x } } { \sqrt { x } } \mathrm { ~d} x .$$ Deduce that $\forall n \in \mathbb { N } , \mu _ { n } = C _ { n }$.