Solution pour le challenge n° 52

En expérimentant avec de petites valeurs de $n,$ on conjecture que cette somme est égale à $n.$

Posons donc :

$x_{n}=\sum_{k=1}^{n}\,\frac{k\:k!}{n^{k+1}}\,\binom{n}{k}$

et montrons que $x_{n}=1.$ Voici quatre méthodes (la quatrième méthode conduit à une formule beaucoup plus générale …).

Méthode 1 (proposée par Hervé CLAVIER, enseignant)

Pour tout $n\geqslant1$ :

$\begin{eqnarray*}x_{n} & = & \sum_{k=1}^{n}\frac{k\:k!}{n^{k+1}}\:\frac{n!}{k!\thinspace\left(n-k\right)!}\\& = & \left(n-1\right)!\sum_{k=1}^{n}\frac{k}{n^{k}\left(n-k\right)!} \end{eqnarray*}$

En posant $j=n-k,$ il vient :

$\begin{eqnarray*}x_{n} & = & \left(n-1\right)!\sum_{j=0}^{n-1}\frac{n-j}{n^{n-j}\thinspace j!}\\ & = & \frac{\left(n-1\right)!}{n^{n}}\sum_{j=0}^{n-1}\frac{n^{j}\left(n-j\right)}{j!}\end{eqnarray*}$

Or :

$\begin{eqnarray*}\sum_{j=0}^{n-1}\frac{n^{j}\left(n-j\right)}{j!} & = & n+\sum_{j=1}^{n-1}\left(\frac{n^{j+1}}{j!}-\frac{n^{j}}{\left(j-1\right)!}\right)\end{eqnarray*}$

ce qui fait apparaître une sommation télescopique. Il reste après simplification :

$\sum_{j=0}^{n-1}\frac{n^{j}\left(n-j\right)}{j!}=n+\left(\frac{n^{n}}{\left(n-1\right)!}-n\right)=\frac{n^{n}}{\left(n-1\right)!}$

d’où finalement : $x_{n}=1.$

Méthode 2 (probabiliste)

On considère dans ce qui suit, une urne contenant $n$ boules numérotées de 1 à $n$ (avec $n\geqslant2).$

On effectue une succession de tirages d’une boule, avec remise, et l’on note $N$ la variable aléatoire indiquant le rang du tirage au cours duquel, pour la première fois, on obtient une boule déjà obtenue auparavant.

Une boule donnée peut réapparaître dès le second tirage et, au plus tard, lors du $\left(n+1\right)$ -ème tirage. On voit donc facilement que l’ensemble des valeurs atteintes par $N$ est :

$N\left(\Omega\right)=\left\llbracket 2,n+1\right\rrbracket$

Pour tout $k\in\left\llbracket 1,n\right\rrbracket ,$ l’événement $\left(N>k\right)$ se réalise lorsque les $k$ premières boules tirées portent des numéros tous distincts, et dans ce cas seulement. Il existe au total $n^{k}$ tirages équiprobables des $k$ premières boules, parmi lesquels $n\left(n-1\right)\cdots\left(n-k+1\right)=\frac{n!}{\left(n-k\right)!}$ sont tels que les $k$ boules tirées soient toutes distinctes. Ainsi :

$\mathbb{P}\left(N>k\right)=\frac{n!}{n^{k}\left(n-k\right)!}$

Comme :

$\left(N>k\right)=\left(N=k+1\right)\cup\left(N>k+1\right)$

(union disjointe), il en résulte que :

$\begin{eqnarray*}\mathbb{P}\left(N=k+1\right) & = & \mathbb{P}\left(N>k\right)-\mathbb{P}\left(N>k+1\right)\end{eqnarray*}$

Si $k\in\left\llbracket 1,n-1\right\rrbracket ,$ ceci nous donne :

$\begin{eqnarray*}\mathbb{P}\left(N=k+1\right) & = & \frac{n!}{n^{k}\left(n-k\right)!}-\frac{n!}{n^{k+1}\left(n-k-1\right)!}\\ & = & \frac{n!}{n^{k}\left(n-k-1\right)!}\left(\frac{1}{n-k}-\frac{1}{n}\right)\\ & = & \frac{n!\thinspace k}{n^{k+1}\left(n-k\right)!}\\ & = & \frac{k\thinspace k!}{n^{k+1}}\thinspace\binom{n}{k}\end{eqnarray*}$

et cette dernière expression est encore valable pour $k=n,$ puisque :

$\mathbb{P}\left(X=n+1\right)=\frac{n!}{n^{n}}$

En effet, aux $n$ premiers lancers sont associés $n^{n}$ tirages équiprobables, parmi lesquels $n!$ produisent des numéros tous distincts.

Au final, la relation :

$\sum_{k=1}^{n}\mathbb{P}\left(N=k+1\right)=1$

prend la forme :

$\boxed{\sum_{k=1}^{n}\frac{k\thinspace k!}{n^{k+1}}\thinspace\binom{n}{k}=1}$

Méthode 3 (un parfum de fonction 𝚪)

On sait (voir l’exercice n° 3 de cette fiche) que pour tout $k\in\mathbb{N}$ :

$\int_{0}^{+\infty}u^{k}e^{-u}\thinspace du=k!$

et donc, après le changement de variable $u=nt$ :

$\int_{0}^{+\infty}\,t^{k}\,e^{-nt}\,dt=\frac{k!}{n^{k+1}}$

Il en résulte que :

$x_{n}=\int_{0}^{+\infty}\,\left(\sum_{k=1}^{n}\,k\,\binom{n}{k}\,t^{k}\right)\,e^{-nt}\,dt=\int_{0}^{+\infty}\,nt\left(1+t\right)^{n-1}\,e^{-nt}\,dt$

c’est-à-dire :

$x_{n}=A_{n}-n\,\int_{0}^{+\infty}\,\left(1+t\right)^{n-1}\,e^{-nt}\,dt$

où l’on a posé :

$A_{n}=n\,\int_{0}^{+\infty}\,\left(1+t\right)^{n}\,e^{-nt}\,dt$

Intégrons par parties en posant :

$\left.\begin{array}{c}u=\left(1+t\right)^{n}\\v'=n\,e^{-nt}\end{array}\right\} \;\text{et}\;\left\{ \begin{array}{c}u'=n\left(1+t\right)^{n-1}\\v=-e^{-nt}\end{array}\right.$

On obtient :

$A_{n}=\underbrace{\left[-\left(1+t\right)^{n}\,e^{-nt}\right]_{t=0}^{+\infty}}_{=1}+n\,\int_{0}^{+\infty}\,\left(1+t\right)^{n-1}\,e^{-nt}\,dt$

et donc $x_{n}=1,$ comme souhaité.

Méthode 4 (une formule plus générale)

On commence par établir un petit …

Lemme

Etant donné un entier $n\geqslant1$ et des réels $a_1,\ldots,a_n$ :

$\sum_{k=1}^na_k\prod_{i=1}^{k-1}\left(1-a_i\right)=1-\prod_{i=1}^n\left(1-a_i\right)$

Note : on utilise la convention usuelle selon laquelle un produit indexé par l’ensemble vide est égal à 1.

Cette formule se prouve aisément par récurrence, ou bien en observant que la sommation peut être rendue télescopique. En effet, pour tout $k\in\llbracket1,n\rrbracket$ :

$\begin{eqnarray*}a_k\prod_{i=1}^{k-1}\left(1-a_i\right) & = & \left(1-(1-a_k)\right)\prod_{i=1}^{k-1}\left(1-a_i\right)\\& = & \prod_{i=1}^{k-1}\left(1-a_i\right)-\prod_{i=1}^{k}\left(1-a_i\right)\end{eqnarray*}$