Dénombrement

On note $\displaystyle K$ le corps $\displaystyle \mathbb{Z}/2\mathbb{Z}$, muni des lois d’addition et de multiplication usuelles. On considère le $\displaystyle K$-espace vectoriel $\displaystyle V=K^n$. La dimension de $\displaystyle V$ sur $\displaystyle K$ est $\displaystyle n$.
Il y a une bijection naturelle, notée $\displaystyle \mathcal{E}$, entre $\displaystyle V$ et l’ensemble $\displaystyle P=\mathcal{P}\{1,\ldots,n\}$ : à tout $\displaystyle x \in V$, on associe la partie $\displaystyle E=\mathcal{E}(x) \in P$ telle que, pour tout $\displaystyle l\in\{1,\ldots n\}$, on a $\displaystyle l \in E \Leftrightarrow x_l=1$.
On consière également la forme bilinéaire $\displaystyle b : V \times V \rightarrow K$ définie par :
$$\forall (x,y) \in V \times V \ , \ b(x,y)=\sum_{j=1}^n x_j y_j.$$ En plus de la bilinéarité, on utilise la propriété suivante : $\displaystyle b(x,y)$ vaut $\displaystyle 0$, resp. $\displaystyle 1$, si et seulement si le cardinal de $\displaystyle \mathcal{E}(x) \cap \mathcal{E}(y)$ est pair, resp. impair. En effet, le produit $\displaystyle x_j y_j$ vaut $\displaystyle 1$ si et seulement si $\displaystyle x_j=y_j=1$, c’est à dire si et seulement si $\displaystyle j$ appartient à $\displaystyle \mathcal{E}(x)$ et à $\displaystyle \mathcal{E}(y)$.

On considère maintenant une famille $\displaystyle E_1,\ldots,E_k$ vérifiant les hypothèses de l’énoncé. On pose $\displaystyle x^{(i)}=\mathcal{E}^{-1}(E_i) \in V$. On va montrer que la famille $\displaystyle (x^{(1),\ldots,x^{(k)}})$ est libre dans $\displaystyle V$, ce qui implique que $\displaystyle k \leq {\rm dim }(V) = n$.

Soient $\displaystyle \lambda_1,\ldots,\lambda_k \in K$ tels que $\displaystyle \sum_{i=1}^k \lambda_i x^{(i)} = 0$. On fixe un indice $\displaystyle 1 \leq i_0 \leq k$. On a alors :
$$0 = b(0,x^{(i_0)}) = \sum_{i=1}^k \lambda_i b(x^{(i)},x^{(i_0)}).$$
Or si $\displaystyle i \neq i_0$, alors $\displaystyle \phi(x^{(i)}) \cap \phi(x^{(i_0)}) = E_i \cap E_{i_0}$ est de cardinal pair, par la deuxième hypothèse, on a donc $\displaystyle b(x^{(i)},x^{(i_0)})=0$. De la même façon, la première hypothèse implique que $\displaystyle b(x^{(i_0)},x^{(i_0)})=1$. On a donc $\displaystyle 0=\lambda_{i_0}$. Comme $\displaystyle i_0$ a été choisi arbitrairement dans $\displaystyle \{1,\ldots,k\}$, on a montré que $\displaystyle \lambda_i = 0$ pour tout indice $\displaystyle i$, ce qui prouve que la famille $\displaystyle (x^{(1)}),\ldots,x^{(k)})$ est libre dans $\displaystyle V$. On a donc nécessairement $\displaystyle k \leq n$.
On remarque pour finir qu’on peut avoir $\displaystyle k=n$ : il suffit de choisir $\displaystyle E_{i}$
= {i} pour tout $\displaystyle i \in \{1,\ldots, n\}$.

Autre méthode
Peut-on se passer des méthodes d’algèbre linéaire, qui paraissent assez artificielles au vu de l’énoncé ? Réponse : oui, bien sûr, mais au prix d’un travail titanesque, au bout duquel on est convaincu de la puissance du théorème de la base incomplète, et également convaincu que l’utilisation de l’algèbre linéaire est finalement assez naturelle.

Soient $\displaystyle E_1,\ldots,E_k$ vérifiant les hypothèses de l’énoncé. Pour toute partie $\displaystyle I$ de $\displaystyle \{1,\ldots,k\}$et tout élément $\displaystyle l \in \{1,\ldots,n\}$on pose $$m(l,I) = {\rm Card}\{i \in I : l \in E_i\}.$$On remarque que si $\displaystyle I \cap J = \emptyset$ alors $\displaystyle m(l,I\cup J) = m(l,I)+m(l,J)$.
On introduit l’application $\displaystyle \Phi : \mathcal{P(\{1,\ldots,k\})} \rightarrow \mathcal{P}(\{1,\ldots,n\})$définie de la façon suivante : $\displaystyle l \in \Phi(I)$ si et seulement si $\displaystyle m(I,l)$ est impair. On va montrer que l’application $\displaystyle \Phi$ est injective, ce qui implique que $\displaystyle 2^k \leq 2^n$, donc que $\displaystyle k \leq n$.

On montre d’abord que $\displaystyle \Phi(I \Delta J) = \Phi(I) \Delta \Phi(J)$, où $\displaystyle \Delta$ représente la différence symétrique. Par définition, $\displaystyle I \Delta J$ est l’union disjointe de $\displaystyle I \backslash J = I \cap J^c$ et $\displaystyle J \backslash I = J \cap I^c$. On a donc :
$$m(l, I \Delta J) = m(l,I \backslash J)+m(l,J \backslash I) = m(l,I)+m(l,J)-2m(l,I\cap J).$$En particulier, $\displaystyle m(l,I \Delta J)$ est impair si et seulement si exactement une des deux quantités $\displaystyle m(l,I)$, $\displaystyle m(l,J)$ est paire, ce qui est équivalent à dire que $\displaystyle l$ appartient à un et un seul des deux ensembles$\displaystyle \Phi(I)$, $\displaystyle \Phi(J)$, autrement dit si et seulement si $\displaystyle l \in \Phi(I) \Delta \Phi(J)$.
Soient $\displaystyle I$ et $\displaystyle J$ telles que $\displaystyle \Phi(I) = \Phi(J)$. On a $\displaystyle \Phi(I) \Delta \Phi(J) = \emptyset$, donc $\displaystyle \Phi(K) = \emptyset$, où $\displaystyle K= I \Delta J$. Il reste à montrer que nécessairement $\displaystyle K= \emptyset$. Supposons par l’absurde que’il existe un certain $\displaystyle i \in K$. Comme on a $\displaystyle \Phi(K) = \emptyset$, chacun des $\displaystyle m(l,K)$ est pair. En particulier, $\displaystyle \sum_{l \in E_i} m(l,K)$ est pair. Mais on a aussi : $$\sum_{l \in E_i} m(l,K) = \sum_{l \in E_i} \sum_{k \in K} 1_{l \in E_k} = \sum_{k \in K} \sum_{l\in E_i} 1_{l\in E_k} = \sum_{k \in K} {\rm card}(E_i \cap E_k).$$
Or les quantités $\displaystyle {\rm card}(E_i \cap E_k)$ sont toutes paires, sauf $\displaystyle {\rm card}(E_i \cap E_i) = {\rm card}(E_i )$, qui est impair. Ainsi on a prouvé que $\displaystyle \sum_{l \in E_i}m(l,K)$ est impair, ce qui est une contradiction. Ainsi $\displaystyle K = \emptyset$, donc $\displaystyle \Phi$ est injective et $\displaystyle k \le n$.

1. L’idée est d’écrire $\displaystyle {n \choose k}$ sous la forme explicite $\displaystyle \frac{n!}{k!(n-k)!}$, ce qui est possible dès que $\displaystyle 0 \le k \le n$. On a alors : $$\sum_{k=1}^n k {n \choose k} = \sum_{k=1}^n k \frac{(n-1)! n}{ (k-1)!k ((n-1)-(k-1))!}$$$$= n \sum_{k=1}^n {n-1 \choose k-1} = n \sum_{l=0}^{n-1} {n-1 \choose l} = n 2^{n-1}.$$
   Pour le second calcul, c’est la même idée :
   $$\sum_{k=0}^n \frac{1}{k+1} {n \choose k} = \sum_{k=0}^n \frac{\frac{(n+1)!}{n+1}}{(k+1)k ! ((n+1)-(k+1))!}$$ $$= \frac{1}{n+1}\sum_{k=0}^n {n+1 \choose k+1} = \frac{1}{n+1} \sum_{l=1}^{n+1} {n+1 \choose l} = \frac{2^{n+1}-1}{n+1}.$$

2. La même idée d’expliciter les coefficients binomiaux est encore valable ici, car on a les inégalités $\displaystyle 0 \le k \le n$ et $\displaystyle 0 \le p-k \le n-k$. On peut donc écrire : $$\sum_{k=1}^p (-1)^k {n\choose k} {n-k \choose p-k} = \sum_{k=1}^p (-1)^k \frac{n!}{k!(n-k)!} \frac{(n-k)!}{(p-k)! ((n-k)-(p-k))!}$$ $$= \frac{n!}{(n-p)!} \sum_{k=1}^p (-1)^k \frac{1}{k! (p-k)!} = {n \choose p} \sum_{k=1}^p (-1)^k {p \choose k}$$ $$={n \choose p} ((1-1)^p-1) = - {n \choose p}.$$

Au vu de l’égalité sur les $\displaystyle C_n$ 👉 Produit de Cauchy.

1. Tout produit des $\displaystyle a_j$ s’écrit d’une unique façon $\displaystyle (a_1\cdots a_k)(a_{k+1}\cdots a_n)$. La parenthèse de “coupure” représente un $\displaystyle k$ qui va varier entre $\displaystyle 1$ et $\displaystyle n-1$. Il y a $\displaystyle C_k$ parenthésages possibles pour $\displaystyle (a_1\cdots a_k)$ et $\displaystyle C_{n-k}$ pour $\displaystyle (a_{k+1}\cdots a_n)$. D’où l’égalité voulue pour $\displaystyle n\ge2$. On a aussi $\displaystyle C_1=1$.
2. On calcule $\displaystyle g(x)^2=\sum_{n\ge2}\left(\sum_{k=1}^{n-1} C_k C_{n-k}\right)x^n=\sum_{n\ge2}C_n x^n =g(x)-x$. Pour l’instant c’est un calcul formel car on ne sait pas si le rayon de convergence est $\displaystyle R>0$. Supposons que ce soit le cas dans notre phase d’analyse.
3. On peut résoudre l’équation $\displaystyle g^2-g+x=0$, ce qui donne après une petite étude $\displaystyle g(x)=\frac{1-\sqrt{1-4x}}{2}$.
   Pour la synthèse, il faut développer en série entière $\displaystyle g(x)$ et vérifier qu’on a bien la relation de récurrence de la question 1). On a $\displaystyle g'(x)=\frac{1}{\sqrt{1-4x}}$ et on peut développer assez facilement $\displaystyle g'$ pour $\displaystyle 0 < x < 1/4$, et on trouve $\displaystyle g'(x)=\sum_{n\ge0}{2n \choose n}x^n$. En intégrant et avec $\displaystyle g(0)=0$, il vient $\displaystyle C_n=\frac{{2n-2 \choose n-1}}{n}$, $\displaystyle n\ge1$.

Ceux sont les nombres de Catalan qui constituent un sujet passionnant de combinatoire.

1. On a $\displaystyle a_n=\frac{n}{n+1}\frac{2n(2n-1)}{n^2}=\frac{4-2/n}{1+1/n}\xrightarrow[n\to\infty]{}4$. On en déduit, par le critère de d’Alembert, que le rayon de convergence de $\displaystyle \sum_{n\ge1} C_n x^n$ est $\displaystyle R=\frac14$.
2. On a $$f'(x)=\sum_{n\ge1} nC_n x^{n-1}=1+4xf'(x)-2f(x).$$ On en déduit que $\displaystyle f$ satisfait l’équation différentielle $\displaystyle (1-4x)y'+2y=1$. On la résout avec la méthode de variation de la constante, et on trouve pour tout $\displaystyle x\in]-1/4,1/4[$, $\displaystyle f(x)=\frac12(1-\sqrt{1-4x})$.
3. La fonction $\displaystyle f$ vérifie l’équation fonctionnelle $\displaystyle f(x)^2=f(x)-x$ sur $\displaystyle ]-1/4,1/4[$.
4. On a $\displaystyle f(x)^2=\sum_{n\ge1} d_n x^n$ avec $\displaystyle d_n=\sum_{k=1}^{n-1}C_kC_{n-k}$. En identifiant les coefficients avec l’équation fonctionnelle, on obtient pour tout $\displaystyle n\ge2$, $\displaystyle d_n=C_n$, d’où $\displaystyle C_n=\sum_{k=1}^{n-1}C_kC_{n-k}$.

• Somme, combinaison 👉 Formule du binôme ;
• Polynômes interpolateurs $\displaystyle L_k$ de Lagrange 👉 écriture de $\displaystyle P$ comme somme des $\displaystyle L_k$.

1. La formule du binôme de Newton permet d’écrire : $$\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^k P_0(k) = \sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^k = (1-1)^{n+1} = 0$$ comme souhaité. Soit maintenant $\displaystyle 1 \le l \le n$ fixé. On va montrer que l’identité voulue est bien vérifiée pour le polynôme $\displaystyle P_l$. On constate que $\displaystyle P_l(k) = 0$ pour tout $\displaystyle 0 \le k \le l-1$ et que $$\forall k \in \{l,\ldots,n\} \ , \ P_l(k) = \frac{k!}{(k-l)!}.$$ Ainsi, $$\begin{aligned} \sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^k P_l(k)\ & =\ \sum_{k=l}^{n+1} \frac{(n+1)!}{k!(n+1-k)!} \frac{k!}{(k-l)!} (-1)^k\\ & =\ \sum_{k=l}^{n+1} \frac{(n+1)!}{(k-l)!(n+1-k)!}(-1)^k. \end{aligned}$$ Le changement d’indices $\displaystyle p=k-l$ montre que cette somme vaut $$\frac{(n+1)!}{(n+1-l)!} \sum_{p=0}^{n+1-l} \binom{n+1-l}{p}(-1)^{l+p} = \frac{(n+1)!}{(n+1-l)!} (-1)^l (1-1)^{n+1-l} = 0.$$ Pour démontrer l’identité pour un polynôme quelconque $\displaystyle P \in \R_n[X]$, on commence par remarquer que $\displaystyle (P_l)_{0 \le l \le n}$ forme une base de $\displaystyle \R_n[X]$. En effet c’est une famille étagée car $\displaystyle {\rm deg}(P_l) =l$. Il existe donc des coefficients $\displaystyle a_0,\ldots,a_n$ tels que $\displaystyle P(X) = \sum_{l=0}^n a_l P_l(X)$ et on a : $$\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^k P(k) = \sum_{l=0}^n a_l \left(\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^k P_l(k) \right) = 0.$$

2. On pose $\displaystyle \alpha_k = P(k)$ pour tout $\displaystyle k \in \{0,\ldots, n\}$. On sait, par la théorie des polynômes d’interpolation de Lagrange, que $\displaystyle P$ est l’unique polynôme de $\displaystyle \R_n[X]$ tel que $\displaystyle P(k) = \alpha_k$ pour tout $\displaystyle 0 \le k \le n$. De plus, on a $\displaystyle P(X) = \sum_{k=0}^n \alpha_k L_k(X)$, avec $$L_k(X) = \frac{\prod_{0 \le i \le n , i \neq k} X-i}{\prod_{0 \le i \le n , i \neq k} k-i}.$$ Le dénominateur se simplifie : on a $$\prod_{0 \le i \le n , i \neq k} k-i = \left(\prod_{i=0}^{k-1} k-i \right) \left(\prod_{i=k+1}^n k-i\right) = k ! (-1)^{n-k} (n-k)!$$ De plus on a : $$\prod_{0 \le i \le n , i \neq k} n+1-i = \frac{\prod_{i=0}^n n+1-i}{n+1-k} = \frac{(n+1)!}{n+1-k}.$$ Ainsi $$L_k(n+1) = \frac{(n+1)!}{k!(n-k)!(n+1-k) (-1)^{n-k}} = \binom{n+1}{k} (-1)^{n-k}.$$ On en déduit que $$P(n+1) = \sum_{k=0}^n \binom{n+1}{k} (-1)^{n-k} P(k),$$ donc (en écrivant $\displaystyle (-1)^{n-k} = (-1)^{n+k}$) : $$\sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{k} P(k) = (-1)^{n+1} P(n+1) + (-1)^n P(n+1) = 0.$$

BONUS !!! Une troisième méthode : on considère l’application linéaire $\displaystyle D : \R[X] \rightarrow \R[X]$ qui à tout polynôme $\displaystyle P$ associe le polynôme $\displaystyle Q=D(P)$ tel que $\displaystyle Q(X)=P(X+1)-P(X)$. On peut voir l’application $\displaystyle D$ comme une dérivation discrète (d’où la lettre $\displaystyle D$, malin, non ?). On va se raccrocher à cette intuition en vérifiant si certaines propriétés de l’opération de dérivation sont aussi vraies pour $\displaystyle D$. Tout d’abord, on remaque que si $\displaystyle P(X)=X^p$, alors $\displaystyle D(P)(X)=(X+1)^p-X^p = \sum_{k=0}^{p-1} \binom{p}{k} X^{k-1}$. Ainsi $\displaystyle D$ envoie tout polynôme de degré (exactement) $\displaystyle d \ge 1$ sur un polynôme de degré (exactement) $\displaystyle d-1$. En particulier le noyau de $\displaystyle D$ est l’ensemble des polynômes constants.

On va maintenant itérer l’opération $\displaystyle D$. On remarque que $$(D^2P)(X) = (DP)(X+1)-(DP)(X) = P(X+2)-2P(X+1)+P(X).$$ On peut alors montrer par récurrence sur $\displaystyle n \ge 1$ que $$(D^nP)(X) = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} P(X+k).$$ En effet si cette formule est vraie pour un certain rang $\displaystyle n$ on a alors $$(D^{n+1}P)(X) = \sum_{k} \binom{n}{k} (-1)^{n-k} (P(X+k+1)-P(X+k)) = \sum_{k} P(X+k) (-1)^{n+1-k}\left(\binom{n}{k}+\binom{n}{k-1}\right),$$ et on conclut par la formule de Pascal.

Vu le résultat à prouver à la question 1, il faut faire apparaître une famille sommable !

1. On sait que pour tout $\displaystyle z \in \R$ on a $\displaystyle \exp(z) = \sum_{k=0}^\infty \frac{z^k}{k!}$ donc $$f(x) = \sum_{k=0}^\infty \frac{\exp(kx)}{k!} = \sum_{k=0}^\infty \sum_{n=0}^\infty \frac{k^n x^n}{k! n!}.$$ Or on sait que $$\sum_{k=0}^\infty \sum_{n=0}^\infty \frac{k^n |x|^n}{k! n!} = \exp(\exp(|x|)) < \infty,$$ on peut donc écrire, par sommabilité de la famille : $$f(x) = \sum_{n=0}^\infty \sum_{k=0}^\infty \frac{k^n x^n}{k! n!} = \sum_{n=0}^\infty \frac{A_n}{n!} x^n.$$ Cette formule a été établie pour tout $\displaystyle x\in \R$, ce qui prouve que la fonction $\displaystyle f$ est développable en série entière autour de $\displaystyle 0$, avec un rayon infini.
2. Pour $\displaystyle n=0$, on remarque qu’on a bien $\displaystyle f'(x) = \exp(x) f(x).$ Si $\displaystyle n> 0$, on écrit que $$f^{(n+1)}(x) = \frac{\partial^n }{\partial x^n} f'(x) =\frac{\partial^n }{\partial x^n} (\exp(x) f(x)),$$ et par la formule de Leibniz (et en remarquant que $\displaystyle \exp^{(k)} = \exp$) on obtient : $$f^{(n+1)}(x) = \sum_{k=0}^n \binom{n}{k} \exp(x) f^{(k)}(x).$$ De plus, la fonction $\displaystyle f$ est de classe $\displaystyle \mathcal{C}^\infty$ en $\displaystyle 0$ et on a, d’après la première question, $\displaystyle f^{(n)}(0) = A_n$. En prenant la valeur particulière $\displaystyle x=0$ dans la formule de récurrence sur les $\displaystyle f^{(n)}$, on obtient alors : $$A_{n+1} = \sum_{k=0}^n \binom{n}{k} A_k.$$
3. On montre par récurrence sur $\displaystyle n \ge 0$ que $\displaystyle B_n$ est entier. Si $\displaystyle n=0$, on a $\displaystyle A_0=e$ donc $\displaystyle B_0=1$. Pour montrer l’hérédité, on remarque que, d’après la question 2, on a $\displaystyle B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k$, si $\displaystyle B_0,\ldots,B_n$ sont entiers alors $\displaystyle B_{n+1}$ l’est aussi.

La quantité $\displaystyle k! (2n-k)!$ est-elle monotone en $\displaystyle k$ ? Comme c’est des produits, on regarde des quotients et pas des différences !

Posons $\displaystyle v_k=k! (2n-k)!$. Alors $\displaystyle \frac{v_k}{v_{k+1}}=\frac{2n-k}{k+1}$. Or $\displaystyle 2n-k\ge k+1$ pour $\displaystyle k<n$. Donc $\displaystyle v_k\ge v_{k+1}$ pour tout entier $\displaystyle k\in[0,n-1]$. Donc pour tout entier $\displaystyle k\in[0,n]$, $\displaystyle v_k\ge v_n=(n!)^2$, ce qu’on voulait !
On multiplie cette inégalité par $\displaystyle (2n)!$ et on obtient $\displaystyle \frac{(2n)!}{k! (2n-k)!}\le\frac{(2n)!}{(n!)^2}$, qui est l’inégalité sur les combinaisons désirée.

Plein de compléments intéressants sur Math-OS !

1. Égalité combinatoire 👉 Trouver une interprétation en terme de dénombrement.
2. Produit de fonctions développables en série entière 👉 Produit de Cauchy.
3. Exprimer $\displaystyle d_n$ revient à exprimer $\displaystyle f(x)$.

1. Si $\displaystyle n=0$ l’égalité est vérifiée ($\displaystyle 1=1$). Supposons maintenant $\displaystyle n\in\N^*$.
   $\displaystyle \bullet$ Le nombre total de permutations de $\displaystyle [\![1,n]\!]$ vaut $\displaystyle n!$.
   $\displaystyle \bullet$ Pour $\displaystyle k\in[\![0,n]\!]$, le nombre de permutations de $\displaystyle [\![1,n]\!]$ ayant exactement $\displaystyle k$ points fixes vaut $\displaystyle \binom nk d_{n-k}$. En effet une telle permutation est déterminée par un ensemble $\displaystyle F$ de $\displaystyle k$ points fixes, et par un dérangement de $\displaystyle [\![1,n]\!]\setminus F$ (un ensemble de $\displaystyle n-k$ éléments).

Ainsi $\displaystyle n!=\sum_{k=0}^n\binom nk d_{n-k}$.
2. Comme $\displaystyle 0\leq d_n\leq n!$, le rayon de convergence de $\displaystyle \sum \frac{d_n}{n!}x^n$ est supérieur ou égal à celui de $\displaystyle \sum x^n$, qui vaut $\displaystyle 1$. Ainsi $\displaystyle f$ est définie (au moins) sur $\displaystyle ]-1;1[$.
Pour $\displaystyle x\in]-1;1[$ on peut faire le produit de Cauchy suivant (séries absolument convergentes) :
$$\begin{aligned} f(x)e^x & = \left(\sum_{n=0}^\infty \frac{d_n}{n!}x^n\right)\left(\sum_{n=0}^\infty \frac{1}{n!}x^n\right)\\ & =\sum_{n=0}^\infty\left(\sum_{k=0}^n\frac{d_{n-k}}{(n-k)! k!}\right)x^n\\ &=\sum_{n=0}^\infty \frac{1}{n!}\left(\sum_{k=0}^n\binom nk d_{n-k}\right)x^n\\ &=\sum_{n=0}^\infty x^n=\frac{1}{1-x}. \end{aligned}$$
3. L’égalité $\displaystyle f(x)=\frac{e^{-x}}{1-x}$, pour $\displaystyle x\in]-1;1[$, donne, à nouveau par produit de Cauchy :
$$\sum_{n=0}^\infty\frac{d_n}{n!}x^n = \left(\sum_{n=0}^\infty \frac{(-1)^n}{n!}x^n\right)\left(\sum_{n=0}^\infty x^n\right) = \sum_{n=0}^\infty\left(\sum_{k=0}^n\frac{(-1)^k}{k!}\right)x^n$$ Par unicité du développement en série entière, $\displaystyle \frac{d_n}{n!} = \sum_{k=0}^n\frac{(-1)^k}{k!}$.
$\displaystyle d_n$ est un entier par définition. Pour $\displaystyle n=1$, $\displaystyle d_1=0$ est bien l’entier le plus proche de $\displaystyle \frac 1e$. Prenons maintenant $\displaystyle n\geq 2$, et montrons que $\displaystyle \left|d_n-\frac{n!}{e}\right|<\frac 12$.
On a $\displaystyle d_n-\frac{n!}{e} = n! \sum_{k=0}^n\frac{(-1)^k}{k!}- n! \sum_{k=0}^\infty\frac{(-1)^k}{k!} = - n! \sum_{k=n+1}^\infty\frac{(-1)^k}{k!}$.
On reconnaît le reste d’une série alternée, et on peut donc majorer à l’aide du premier terme :
$$\left|d_n-\frac{n!}{e}\right|\leq \frac{n!}{(n+1)!}=\frac{1}{n+1}<\frac 12.$$