\documentclass[a4paper,11pt]{article}
\usepackage[frenchb]{babel}
\usepackage{amsfonts, amsmath, amssymb, mathrsfs}
\setlength{\topmargin}{-15mm}
\setlength{\oddsidemargin}{-15mm}
\setlength{\textwidth}{18.5 cm}
\setlength{\textheight}{25 cm}
\parindent=0pt
\begin{document}

%Source HEC 1994 m94ag1e


%Num{\'e}rotation
\renewcommand{\labelenumi}{\textbf{\arabic{enumi}.}}
\renewcommand{\labelenumii}{\textbf{\alph{enumii}.}}

%Macros
\renewcommand{\leq}{\,\leqslant\,}
\renewcommand{\geq}{\,\geqslant\,}
\newcommand{\NomPropre}[1]{#1}
\newcommand{\binomial}[2]{C_{#1}^{#2}}
\newcommand{\abs}[1]{\left | #1 \right |}
\newcommand{\D}{\mathop{\rm{} d}}
\newcommand{\integ}[4]{\displaystyle{\int_{#1}^{#2}#3  \ \D #4}}
\newcommand{\integrale}[3]{\displaystyle{\int_{#1}^{#2}#3}}
\newcommand{\somme}[3]{\sum_{#1}^{#2}\limits{#3}}
\newcommand{\matrice}[1]{\begin{pmatrix} #1 \end{pmatrix}}



\begin{center}
\textbf{\textit{{\large {\'E}COLE DES HAUTES {\'E}TUDES COMMERCIALES}}}

\textbf{\textit{{\large MATH{\'E}MATIQUES 1}}}

\textit{OPTION G{\'E}N{\'E}RALE}
\end{center}

L'objet du probl{\`e}me est l'{\'e}tude d'une approximation de $\ln{(n!)}$ pour les grandes valeurs de l'entier $n$.

\bigskip
Dans la partie I, on {\'e}tablit des majorations qui seront utilis{\'e}es dans les parties II et III.

Dans la partie II, on {\'e}tudie une suite permettant d'obtenir une premi{\`e}re approximation de $\ln{(n!)}$.

Dans la partie III, on {\'e}tablit deux {\'e}valuations plus pr{\'e}cises de $\ln{(n!)}$ puis une approximation g{\'e}n{\'e}rale.

Enfin, dans la partie IV, on {\'e}tudie un algorithme permettant d'expliciter cette approximation g{\'e}n{\'e}rale.

Cette derni{\`e}re partie utilise uniquement les notations et les r{\'e}sultats de la partie III.

\medskip
Dans tout le probl{\`e}me, $p$ d{\'e}signe un entier naturel fix{\'e} et $n$ un entier variable sup{\'e}rieur ou {\'e}gal {\`a} $1$.

{\'E}tant donn{\'e}s deux entiers $i$ et $j$ tels que $0 {\leq} j {\leq} i$, on note $\binomial{i}{j} = \dfrac{i!}{j! (i-j)!}$ avec la convention usuelle $0! = 1$.

\textbf{PARTIE I.}

\begin{enumerate}
\item %I.1.
V{\'e}rifier que : $\forall t {\neq} 1 \quad \dfrac{1}{1-t} = 1 + t + t^{2} + {\dots} + t^{p+1} + \dfrac{t^{p+2}}{1-t}$.

En d{\'e}duire : $\forall k {\geq} 2 \quad -\ln{\left(1 - \dfrac{1}{k}\right)} = \dfrac{1}{k} + \dfrac{1}{2k^{2}} + {\dots} + \dfrac{1}{(p+2) k^{p+2}} + \integ{0}{1/k}{\dfrac{t^{p+2}}{1-t}}{t}$

puis que : $\forall k {\geq} 2 \quad  -\ln{\left(1 - \dfrac{1}{k}\right)} = \dfrac{1}{k} + \dfrac{1}{2k^{2}} + {\dots} + \dfrac{1}{(p+2) k^{p+2}} + \dfrac{\alpha(k)}{k^{p+3}}$ avec $0 {\leq} \alpha(k) {\leq} \dfrac{2}{p+3}$.

\item %I.2.
On d{\'e}signe par $M$ un r{\'e}el positif et on envisage une s{\'e}rie r{\'e}elle $\somme{k=2}{+{\infty}}{z_{k}}$ dont le terme g{\'e}n{\'e}ral $z_{k}$ v{\'e}rifie $\abs{z_{k}} {\leq} \dfrac{M}{k^{p+2}}$.

Justifier la convergence de la s{\'e}rie $\somme{k=2}{+{\infty}}{z_{k}}$.

Prouver que : $\forall n {\geq} 1 \quad \forall m {\geq} n+1 \quad \dfrac{1}{(n+1)^{p+2}} + \dfrac{1}{(n+2)^{p+2}} + {\dots} + \dfrac{1}{k^{p+2}} + {\dots} + \dfrac{1}{m^{p+2}} {\leq} \integrale{n}{m}{\dfrac{\D t}{t^{p+2}}}$.

En d{\'e}duire : $\forall n {\geq} 1 \quad \forall m {\geq} n+1 \quad \dfrac{1}{(n+1)^{p+2}} + \dfrac{1}{(n+2)^{p+2}} + {\dots} + \dfrac{1}{k^{p+2}} + {\dots} + \dfrac{1}{m^{p+2}} {\leq} \dfrac{1}{p+1} \dfrac{1}{n^{p+1}}$

puis que : $\forall n {\geq} 1 \quad \abs{\somme{k=n+1}{+{\infty}}{z_{k}}} {\leq} \dfrac{M}{p+1} \dfrac{1}{n^{p+1}}$.
\end{enumerate}

\textbf{PARTIE II : une premi{\`e}re approximation de $\ln{(n!)}$.}

\begin{enumerate}
\item %II.1
\textit{Expression de $\ln{(n!)}$ {\`a} l'aide d'une suite.}

\begin{enumerate}
\item %II.1.a
On consid{\`e}re la suite $(v_{k})_{k{\geq}2}$ d{\'e}finie par $v_{k} = \ln{k} - \integ{k-1}{k}{\ln{t}}{t}$.

Prouver que : $\forall n {\geq} 2 \quad \ln{(n!)} = \somme{k=2}{n}{v_{k}} + \integ{1}{n}{\ln{t}}{t}$.

Expliciter $\integ{1}{n}{\ln{t}}{t}$.

\item %II.1.b.
{\'E}tablir que : $\forall k {\geq} 2 \quad v_{k} = \integ{0}{1}{\left(\ln{k} - \ln{(k-u)}\right)}{u}$

En d{\'e}duire que : $\forall k {\geq} 2 \quad v_{k} = \dfrac{1}{2} \left(\ln{k} - \ln{(k-1)}\right) - \integ{0}{1}{\dfrac{u - 1/2}{k-u}}{u}$.

Dans la suite de cette partie on pose $w_{k} = \integ{0}{1}{\dfrac{u - 1/2}{k-u}}{u}$ pour $k {\geq} 2$.

\item %II.1.c.
Montrer que : $\forall n {\geq} 2 \quad \ln{(n!)} = n \ln{n} - n + \dfrac{1}{2} \ln{n} + 1 - \somme{k=2}{n}{w_{k}}$.
\end{enumerate}

\item %II.2.
\textit{{\'E}tude de la suite $(w_{k})_{k{\geq}2}$.}

Prouver que $w_{k} =\dfrac{1}{2} \integ{0}{1}{\dfrac{u-u^{2}}{(k-u)^{2}}}{u}$ pour $k {\geq} 2$.

En d{\'e}duire que $0 {\leq} w_{k} {\leq} \dfrac{1}{12 (k-1)^{2}}$.

Ainsi, la s{\'e}rie $\somme{k=2}{+{\infty}}{w_{k}}$ converge. On admettra que sa somme a pour valeur $1 - \dfrac{1}{2} \ln{(2\pi)}$.

\textit{On note d{\'e}sormais, dans toute la suite du probl{\`e}me, $(\varepsilon_{n})_{n{\geq}1}$ la suite d{\'e}finie par $\varepsilon_{n} = \somme{k=n+1}{+{\infty}}{w_{k}}$.}

\item %II.3.
\textit{{\'E}valuation asymptotique de $\ln{(n!)}$.}

Montrer que : $\forall n {\geq}1 \quad \ln{(n!)} = n \ln{n} - n + \dfrac{1}{2} \ln{n} + \dfrac{1}{2} \ln{(2\pi)} + \varepsilon_{n}$ \hspace{1cm} \textit{(1)}

\item %II.4.
\textit{Majoration du reste $\varepsilon_{n}$.}

En utilisant la seconde question de la premi{\`e}re partie, {\'e}tablir que : 
$0 {\leq} \varepsilon_{n} {\leq} \dfrac{1}{12(n-1)}$ pour $n {\geq} 2$.
\end{enumerate}

\textbf{PARTIE III : une approximation g{\'e}n{\'e}rale de $\ln{(n!)}$.}

Cette partie a pour objet d'{\'e}tudier plus pr{\'e}cis{\'e}ment le comportement asymptotique de la suite $(\varepsilon_{n})_{n{\geq}1}$.

\begin{enumerate}
\item %III.1.
\textit{{\'E}valuation de $\varepsilon_{k-1} - \varepsilon_{k}$.}

{\`A} l'aide de l'{\'e}galit{\'e} \textit{(1)} de la partie II, {\'e}tablir que :

$\forall k {\geq} 2 \quad \varepsilon_{k-1} - \varepsilon_{k} = - \left(k - \dfrac{1}{2}\right) \ln{\left(1 - \dfrac{1}{k}\right)} - 1$.

D{\'e}duire de la question 1. de la partie I que :

$\forall k {\geq} 2 \quad \varepsilon_{k-1} - \varepsilon_{k} = \somme{i=1}{p}{\dfrac{b_{i}}{k^{i+1}}} + \dfrac{\delta(k)}{k^{p+2}}$ avec $b_{i} = \dfrac{i}{2 (i+1)(i+2)}$ et $\abs{\delta(k)} {\leq} 1$ \hspace{5mm} \textit{(2)}.

\item %III.2.
\textit{Une premi{\`e}re {\'e}valuation de $\varepsilon_{n}$.}

Dans cette question, on fixe $p = 1$ de sorte que \textit{(2)} s'{\'e}crit $\varepsilon_{k-1} - \varepsilon_{k} = \dfrac{1}{12k^{2}} + \dfrac{\delta(k)}{k^{3}}$ et on pose $r_{k} = \varepsilon_{k} - \dfrac{c_{1}}{k}$, $c_{1}$ d{\'e}signant un nombre r{\'e}el.
\begin{enumerate}
\item %III.2.a.
Montrer que : $\forall k {\geq} 2 \quad \dfrac{1}{1-\dfrac{1}{k}} = 1 + \dfrac{1}{k} + \dfrac{\beta(k)}{k^{2}}$ avec $0 {\leq} \beta(k) {\leq} 2$.

\item %III.2.b.
D{\'e}terminer $c_{1}$ de sorte que $\abs{r_{k-1} - r_{k}} {\leq} \dfrac{7}{6k^{3}}$ pour $k {\geq} 2$.

Le r{\'e}el $c_{1}$ {\'e}tant ainsi choisi, {\'e}tablir que :

$\forall n {\geq} 1 \quad \abs{\somme{k=n+1}{+{\infty}}{\left(r_{k-1}-r_{k}\right)}} {\leq} \dfrac{7}{12n^{2}}$.

\item %III.2.c.
Prouver que $\somme{k=n+1}{+{\infty}}{\left(r_{k-1}-r_{k}\right)} = r_{n}$ et en d{\'e}duire :

$\forall n {\geq} 1 \quad \ln{(n!)} = n \ln{n} - n + \dfrac{1}{2} \ln{n} + \dfrac{1}{2} \ln{(2\pi)} + \dfrac{1}{12n} + \dfrac{\lambda_{1}(n)}{n^{2}}$
avec $\abs{\lambda_{1}(n)} {\leq} \dfrac{7}{12}$.
\end{enumerate}

\item %III.3.
\textit{Une seconde {\'e}valuation de $\varepsilon_{n}$.}

Dans cette question, on fixe $p = 2$ de sorte que \textit{(2)} s'{\'e}crit 
$\varepsilon_{k-1} - \varepsilon_{k} = \dfrac{1}{12k^{2}} + \dfrac{1}{12k^{3}} + \dfrac{\delta(k)}{k^{4}}$
et on pose $r_{k} = \varepsilon_{k} - \dfrac{1}{12k} - \dfrac{c_{2}}{k^{2}}$, $c_{2}$ d{\'e}signant un nombre r{\'e}el.
\begin{enumerate}
\item %III.3.a
Montrer que :

$\forall k {\geq} 2 \quad \dfrac{1}{1-\dfrac{1}{k}} = 1 + \dfrac{1}{k} + \dfrac{1}{k^{2}} + \dfrac{\beta_{1}(k)}{k^{3}}$ avec $0 {\leq} \beta_{1}(k) {\leq} 2$.

{\`A} l'aide de la question \textbf{2.a.}, prouver que :

$\forall k {\geq} 2 \quad \dfrac{1}{\left(1-\dfrac{1}{k}\right)^{2}} = 1 + \dfrac{2}{k} + \dfrac{\beta_{2}(k)}{k^{2}}$
avec $0 {\leq} \beta_{2}(k) {\leq} 8$.

\item %III.3.b
V{\'e}rifier que :

$\forall k {\geq} 2 \quad r_{k-1} - r_{k} = \dfrac{-2 c_{2}}{k^{3}} + \left(\delta(k) - \dfrac{1}{12} \beta_{1}(k) - c_{2} \beta_{2}(k)\right) \dfrac{1}{k^{4}}$.

D{\'e}terminer $c_{2}$ de sorte que $\abs{r_{k-1} - r_{k}} {\leq} \dfrac{7}{6 k^{4}}$ pour $k {\geq} 2$.

\item %III.3.c
Prouver que :

$\forall n {\geq} 1 \quad \ln{(n!)} = n \ln{n} - n + \dfrac{1}{2} \ln{n} + \dfrac{1}{2} \ln{(2\pi)} + \dfrac{1}{12 n} + \dfrac{\lambda_{2}(n)}{n^{3}}$
avec $\abs{\lambda_{2}(n)} {\leq} \dfrac{7}{18}$.
\end{enumerate}

\textit{D{\'e}sormais, dans toute la suite du probl{\`e}me, $p$ d{\'e}signe un entier fix{\'e} non nul.}

\item %III.4.
\textit{{\'E}tude d'un syst{\`e}me auxiliaire.}

Les r{\'e}els $b_{1}$, $b_{2}$, {\dots}, $b_{p}$ {\'e}tant d{\'e}finis dans la premi{\`e}re question de cette partie, on envisage le syst{\`e}me $S$ de $p$ {\'e}quations lin{\'e}aires aux $p$ inconnues $x_{1}$, $x_{2}$, {\dots}, $x_{p}$ qui s'{\'e}crit $AX = B$ avec $X = \matrice{x_{1} \\ x_{2} \\ \vdots \\ x_{n}}$, $B = \matrice{b_{1} \\ b_{2} \\ \vdots \\ b_{n}}$ et $A$ la matrice carr{\'e}e d'ordre $p$ dont l'{\'e}l{\'e}ment $a_{i,j}$ situ{\'e} {\`a} l'intersection de la $i^{\mbox{i{\`e}me}}$ ligne et de la $j^{\mbox{i{\`e}me}}$ colonne est $a_{i,j} = \binomial{i}{j-1}$ pour $j {\leq} i$ et $a_{i,j} = 0$ pour $j > i$.

Que valent les {\'e}l{\'e}ments diagonaux de $A$ ?

Montrer que $S$ admet une solution et une seule que l'on notera $(c_{1}, c_{2}, {\dots}, c_{p})$.

\item %III.5
\textit{{\'E}valuation asymptotique de $\varepsilon_{n}$.}

On pose dans cette question $r_{k} = \varepsilon_{k} - \somme{q=1}{p}{\dfrac{c_{q}}{k^{q}}}$ pour $k {\geq} 1$, $(c_{1}, c_{2}, {\dots}, c_{p})$ {\'e}tant la solution du syst{\`e}me pr{\'e}c{\'e}dent.
\begin{enumerate}
\item %III.5.a
En appliquant la formule de \NomPropre{Taylor} avec reste int{\'e}gral {\`a} un ordre convenable {\`a} la fonction $t \mapsto \dfrac{1}{(1-t)^{q}}$, $q$ d{\'e}signant un entier compris entre $1$ et $p$ , montrer que :

$\forall k {\geq} 2 \quad \dfrac{1}{\left(1-\dfrac{1}{k}\right)^{q}} = 1 + \binomial{q}{1} \dfrac{1}{k} + \binomial{q+1}{2} \dfrac{1}{k^{2}} + {\dots} + \binomial{p}{p-q+1} \dfrac{1}{k^{p-q+1}} + \dfrac{q(q+1){\dots}(p+1)}{(p-q+1)!} \integ{0}{1/k}{\dfrac{\left(1/k - t\right)^{p-q+1}}{(1-t)^{p+2}}}{t}$.

Prouver que : $0 {\leq} \integ{0}{1/k}{\dfrac{\left(1/k - t\right)^{p-q+1}}{(1-t)^{p+2}}}{t} {\leq} \left(\dfrac{k}{k-1}\right)^{p+2} \integ{0}{1/k}{u^{p-q+1}}{u}$.

En d{\'e}duire que :

$\forall k {\geq} 2 \quad \dfrac{1}{\left(1-\dfrac{1}{k}\right)^{q}} = 1 + \binomial{q}{1} \dfrac{1}{k} + \binomial{q+1}{2} \dfrac{1}{k^{2}} + {\dots} + \binomial{p}{p-q+1} \dfrac{1}{k^{p-q+1}} + \dfrac{\beta_{q}(k)}{k^{p-q+2}}$ avec $0 {\leq} \beta_{q}(k) {\leq} \binomial{p+1}{q-1} 2^{p+2}$.

\item %III.5.b
En remarquant que $\somme{q=1}{p}{\dfrac{c_{q}}{(k-1)^{q}}} - \somme{q=1}{p}{\dfrac{c_{q}}{k^{q}}} = \somme{q=1}{p}{\dfrac{c_{q}}{k^{q}} \left(\dfrac{1}{\left(1 - \dfrac{1}{k}\right)^{q}} - 1\right)}$, montrer que :

$\forall k {\geq} 2 \quad \somme{q=1}{p}{\dfrac{c_{q}}{(k-1)^{q}}} - \somme{q=1}{p}{\dfrac{c_{q}}{k^{q}}} = \somme{i=1}{p}{\dfrac{\mu_{i}}{k^{i+1}}} + \left(\somme{q=1}{p}{c_{q} \beta_{q}(k)}\right) \dfrac{1}{k^{p+2}}$ avec $\mu_{i} = \somme{j=1}{i}{a_{i,j} c_{j}}$.

\item %III.5.c.
On pose $m_{p} = \max{\left(\abs{c_{1}}, \abs{c_{2}}, {\dots}, \abs{c_{p}}\right)}$ et $M_{p} = 1 + 2^{2p+3} m_{p}$.

Prouver que :

$\forall k {\geq} 2 \quad \abs{r_{k-1} - r_{k}} {\leq} \dfrac{M_{p}}{k^{p+2}}$.

\item %IIII.5.d.
En d{\'e}duire que :

$\forall n {\geq} 1 \quad \ln{(n!)} = n \ln{n} - n + \dfrac{1}{2} \ln{n} + \dfrac{1}{2} \ln{(2\pi)} + \somme{q=1}{p}{\dfrac{c_{q}}{n^{q}}} + \dfrac{\lambda_{p}(n)}{n^{p+1}}$ avec $\abs{\lambda_{p}(n)} {\leq} \dfrac{M_{p}}{p+1}$.
\end{enumerate}
\end{enumerate}

\textbf{PARTIE IV : {\'E}tude d'un algorithme.}

On se propose d'{\'e}tudier dans cette partie un algorithme de calcul des coefficients $c_{1}$, $c_{2}$, {\dots}, $c_{p}$ intervenant dans
l'approximation de $\ln{(n!)}$.

On rappelle que ces coefficients constituent la solution du syst{\`e}me $S$ d{\'e}fini dans la question \textbf{4} de la partie III.

On appelle co{\^u}t d'un algorithme le nombre total d'additions, de soustractions, de multiplications et de divisions effectu{\'e}es au cours de la mise en {\oe{}}uvre de l'algorithme.

L'entier $p$ {\'e}tant d{\'e}clar{\'e} en constante, on effectue les d{\'e}clarations suivantes :
\begin{verbatim}
type vecteur : array[1..p] of real ;
       matrice : array[1..p, 1..p] of real;
var B, C : vecteur;
     A : matrice;
\end{verbatim}

\begin{enumerate}
\item %IV.1.
{\'E}crire \texttt{Procedure SecondMembre(var B : vecteur)} dont le r{\^o}le consiste {\`a} calculer le second membre $B$ du syst{\`e}me $S$.

D{\'e}terminer un {\'e}quivalent de son co{\^u}t lorsque $p$ tend vers $+{\infty}$.

\item %IV.2.
On envisage la proc{\'e}dure suivante :
\begin{verbatim}
procedure Coefficients(var A : matrice);
var i,j : integer;
begin
  A[1, 1] := 1;
  for j:=2 to p do A[1, j]:=0;
  for i:=2 to p do begin
     A[i, 1] :=1 ;
     for j:=2 to i-1 do A[i,j]  := A[i-1, j-1] + A[i-1,j] ;
    A[i,i] :=i;
    for j:=i+1 to p do A[i, j] := 0;
  end ;
end ;
\end{verbatim}
Expliquer le r{\^o}le de cette proc{\'e}dure

D{\'e}terminer un {\'e}quivalent de son co{\^u}t lorsque $p$ tend vers $+{\infty}$.

\item %IV.3
{\'E}crire \texttt{procedure Approximation(A:matrice; B:vecteur; var C:vecteur)} de sorte que, apr{\`e}s les appels de \texttt{SecondMembre(B)} et de \texttt{Coefficients(A)}, l'appel de \texttt{Approximation(A, B, C)} produise \texttt{C} tel que $\rm{C[i] = c}_{\rm{i}}$ pour $i$ de $1$ {\`a} $p$.

D{\'e}terminer un {\'e}quivalent de son co{\^u}t lorsque $p$ tend vers $+{\infty}$.

\item %IV.4.
D{\'e}terminer un {\'e}quivalent, lorsque $p$ tend vers $+{\infty}$, du co{\^u}t total de d{\'e}termination des coefficients $c_{1}$, $c_{2}$, {\dots}, $c_{p}$.
\end{enumerate}

\end{document}

