Factorielles

Solution —

Borne supérieure : chaque facteur de \(n! = 1 \cdot 2 \cdots n\) est \(\leq n\), donc :

\[n! = \prod_{k=1}^{n} k \leq \prod_{k=1}^{n} n = n^n\]

Borne inférieure : on utilise que \(\ln\) est croissante et compare la somme à une intégrale :

\[\ln(n!) = \sum_{k=1}^{n} \ln k \geq \int_1^{n} \ln x\, dx = \bigl[x\ln x - x\bigr]_1^n = n\ln n - n + 1\]

En exponentiant :

\[n! \geq e^{n\ln n - n + 1} = e \cdot \left(\frac{n}{e}\right)^n \geq \left(\frac{n}{e}\right)^n\]

Solution —

On note \(v_p(n!)\) cet exposant. La formule de Legendre donne :

\[v_p(n!) = \sum_{j \geq 1} \left\lfloor \frac{n}{p^j} \right\rfloor\]

Idée : parmi \(1, 2, \ldots, n\), il y a \(\lfloor n/p \rfloor\) multiples de \(p\), puis \(\lfloor n/p^2 \rfloor\) multiples de \(p^2\) (qui contribuent un facteur \(p\) supplémentaire), etc.

Solution —

On développe \(e = \displaystyle\sum_{m \geq 0} \frac{1}{m!}\), donc :

\[e \cdot n! = \sum_{m=0}^{n} \frac{n!}{m!} + R_n \quad \text{où} \quad R_n = \sum_{m \geq n+1} \frac{n!}{m!}\]

Estimée du reste :

\[R_n = \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} + \cdots < \frac{1}{n+1}\sum_{j \geq 0}\frac{1}{(n+1)^j} = \frac{1}{n} < 1\]

Et \(R_n > 0\), donc \(0 < R_n < 1\).

Identification de la somme finie : on pose \(k = n - m\) dans \(\displaystyle\sum_{m=0}^{n} \frac{n!}{m!}\) :

\[\sum_{m=0}^{n} \frac{n!}{m!} = \sum_{k=0}^{n} \frac{n!}{(n-k)!} = \sum_{k=0}^{n} \binom{n}{k} k! = S_n\]

Donc \(e \cdot n! = S_n + R_n\) avec \(0 < R_n < 1\) et \(S_n \in \mathbb{N}\). On conclut :

\[S_n = \lfloor e \cdot n! \rfloor \quad \blacksquare\]

Solution —

1. Limite : on calcule le rapport \(u_{n+1}/u_n\) :

\[\frac{u_{n+1}}{u_n} = \frac{(n+1)!}{(n+1)^{n+1}} \cdot \frac{n^n}{n!} = \frac{n^n}{(n+1)^n} = \left(\frac{n}{n+1}\right)^n = \frac{1}{\left(1+\frac{1}{n}\right)^n} \xrightarrow[n\to+\infty]{} \frac{1}{e}\]

Puisque \(\dfrac{u_{n+1}}{u_n} \to \dfrac{1}{e} < 1\), on a \(u_n \to 0\).

2. Convergence de la série : par le critère de d'Alembert, puisque \(\dfrac{u_{n+1}}{u_n} \to \dfrac{1}{e} < 1\), la série \(\displaystyle\sum u_n\) converge.

Solution —

Tests pour les petites valeurs :

\(n\)	\(n!\)	\(n!+1\)	Carré parfait ?
0	1	2	Non
1	1	2	Non
2	2	3	Non
3	6	7	Non
4	24	25 = 5²	Oui ✓
5	120	121 = 11²	Oui ✓

Pour \(n \geq 6\) : \(n!\) est divisible par \(9\) (car \(6! = 720\)), donc \(n! + 1 \equiv 1 \pmod{9}\). Or les carrés modulo 9 sont \(\{0,1,4,7\}\) — la condition \(m^2 \equiv 1 \pmod{9}\) est possible, donc ce critère seul ne suffit pas.

Pour \(n \geq 6\), on utilise \(n! \equiv 0 \pmod{8}\) (car \(6!\) contient \(2^4\)), donc \(m^2 \equiv 1 \pmod{8}\), ce qui est toujours vrai pour \(m\) impair. Des arguments plus fins (mod 5, mod 7) éliminent les cas restants.

Solution —

Les zéros finaux de \(n!\) proviennent des facteurs \(10 = 2 \times 5\). Il y en a \(v_5(n!)\) (voir exercice 2). On définit :

\[a(n) = \frac{n!}{2^{v_2(n!)} \cdot 5^{v_5(n!)}}\]

Méthode :

1. Calculer \(v_2(n!)\) et \(v_5(n!)\) par la formule de Legendre.
2. La différence \(v_2(n!) - v_5(n!)\) donne le nombre de facteurs 2 résiduels.
3. Réduire \(a(n)\) modulo 10 en exploitant les cycles multiplicatifs.
4. Multiplier par \(2^{v_2(n!)-v_5(n!)} \pmod{10}\).

Solution —

On compare \(\ln(n!) = \displaystyle\sum_{k=1}^{n} \ln k\) à l'intégrale \(\displaystyle\int_1^n \ln x\,dx = n\ln n - n + 1\).

Par la méthode des rectangles (la fonction \(\ln\) est croissante) :

\[n\ln n - n + 1 = \int_1^n \ln x\,dx \leq \sum_{k=1}^{n} \ln k \leq \int_1^{n+1} \ln x\,dx = (n+1)\ln(n+1) - n\]

On obtient donc :

\[n\ln n - n + 1 \leq \ln(n!) \leq n\ln n - n + \ln n + 1\]

Ce qui donne bien \(\ln(n!) = n\ln n - n + O(\ln n)\). En exponentiant :

\[n! \approx \left(\frac{n}{e}\right)^n \cdot K(n) \quad \text{avec } K(n) \in [e,\, e\cdot n]\]

Solution —

1. Formule par inclusion-exclusion :

Notons \(A_i\) l'ensemble des permutations de \(\{1,\ldots,n\}\) qui fixent \(i\). On veut \(|A_1^c \cap \cdots \cap A_n^c|\). Par inclusion-exclusion :

\[D_n = \sum_{k=0}^{n}(-1)^k \sum_{|I|=k}\left|\bigcap_{i\in I} A_i\right| = \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)!\]

car \(\left|\bigcap_{i\in I} A_i\right| = (n-k)!\) pour tout \(I\) de taille \(k\).

2. Lien avec \(e\) : on réécrit :

\[D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}\]

Or \(\displaystyle\frac{1}{e} = \sum_{k=0}^{+\infty}\frac{(-1)^k}{k!}\), donc :

\[\left|\frac{D_n}{n!} - \frac{1}{e}\right| = \left|\sum_{k=n+1}^{+\infty}\frac{(-1)^k}{k!}\right| < \frac{1}{(n+1)!}\]

D'où \(\left|D_n - \dfrac{n!}{e}\right| < \dfrac{1}{n+1} \leq \dfrac{1}{2}\) pour \(n \geq 1\). Donc \(D_n\) est l'entier le plus proche de \(\dfrac{n!}{e}\).