icone-math-OS-Exos
exercice 1 facile

Le calcul des premiers termes de cette suite donne, successivement :

    \begin{eqnarray*}u_{0} & = & 1\\ u_{1} & = & 1\\ u_{2} & = & u_{1}+u_{0}=2\\ u_{3} & = & 2\left(u_{2}+u_{1}\right)=2\times3=6\\ u_{4} & = & 3\left(u_{3}+u_{2}\right)=3\times8=24\\ u_{5} & = & 4\left(u_{4}+u_{3}\right)=4\times30=120\end{eqnarray*}


ce qui nous amène naturellement à conjecturer que :

    \[\boxed{\forall n\in\mathbb{N},\:u_{n}=n!}\]

Prouvons ceci par récurrence.

Vue la manière dont cette suite \left(u_{n}\right)_{n\geqslant0} a été définie, il s’agira d’une récurrence d’ordre 2.

Et comme l’initialisation est faite (largement), on peut passer à l’hérédité.

Supposons donc qu’on ait u_{n-1}=\left(n-1\right)! et u_{n}=n! pour un certain n\in\mathbb{N}^{\star}.

Alors :

    \begin{eqnarray*}u_{n+1} & = & n\left(u_{n}+u_{n-1}\right)\\ & = & n\left(n!+\left(n-1\right)!\right)\\ & = & n\left(n-1\right)!\left(n+1\right)\\ & = & \left(n+1\right)! \end{eqnarray*}

comme souhaité.

exercice 2 facile

On calcule facilement :

    \[B_{1}=1\]

    \[B_{2}=9\]

    \[B_{3}=63\]

    \[B_{4}=447\]

Manifestement, 9 ne divise ni B_{1} ni B_{4} (puisque 447\equiv6\pmod{9}) mais 9 divise B_{2} et B_{3}.

On calcule ensuite :

    \begin{eqnarray*} B_{5} & = & B_{4}+25\times120\\ & = & 3447\\ & = & 9\times383 \end{eqnarray*}

ce qui prouve que 9\mid B_{5}.

Une récurrence vient d’être initialisée. Supposons que, pour un certain n\geqslant5, on ait : 9\mid B_{n}.

Comme \left(n+1\right)! est multiple de 6!=720=9\times80, alors 9\mid\left(n+1\right)\left(n+1\right)! et donc 9\mid B_{n+1}, puisque

    \[B_{n+1}=B_{n}+\left(n+1\right)\left(n+1\right)!\]

En conclusion :

    \[\boxed{\left\{ n\in\mathbb{N}^{\star};\thinspace9\mid B_{n}\right\} =\mathbb{N^{\star}}-\left\{ 1,4\right\} }\]

exercice 3 facile

On va utiliser la :

Proposition

Soit \left(x_{n}\right)_{n\geqslant0} une suite de réels strictement positifs.

Si \displaystyle{\lim_{n\to\infty}\frac{x_{n+1}}{x_n}=L>0}, alors :

    \[ \lim_{n\rightarrow+\infty}\left(x_n\right)^{1/n}=L\]

Ce résultat est une conséquence immédiate du lemme de Cesàro, appliqué à la suite \left(\ln\left(x_{n}\right)\right)_{n\geqslant0}.

Cela dit, posons pour tout n\geqslant1 :

    \[x_{n}=\frac{n!}{n^{n}}\]

Comme :

    \[\frac{x_{n+1}}{x_{n}}=\frac{\left(n+1\right)!}{\left(n+1\right)^{n+1}}\:\frac{n^{n}}{n!}=\left(\frac{n}{n+1}\right)^{n}=\left(1+\frac{1}{n}\right)^{-n}\]

on voit que :

    \[\lim_{n\rightarrow\infty}\frac{x_{n+1}}{x_{n}}=\frac{1}{e}\]

et donc :

    \[\boxed{\lim_{n\rightarrow\infty}\frac{\left(n!\right)^{1/n}}{n}=\frac{1}{e}}\]

On observe que :

    \begin{eqnarray*}\frac{\left(a_{1}+\cdots+a_{r}\right)!}{a_{1}!\cdots a_{r}!} & = & \frac{\left(a_{1}+\cdots+a_{r}\right)!}{a_{1}!\left(a_{2}+\cdots+a_{r}\right)!}\thinspace\frac{\left(a_{2}+\cdots+a_{r}\right)!}{a_{2}!\left(a_{3}+\cdots+a_{r}\right)!}\cdots\frac{\left(a_{r-1}+a_{r}\right)!}{a_{r-1}!a_{r}!}\\ & = & \prod_{i=1}^{r-1}\binom{a_{i}+\cdots+a_{r}}{a_{i}} \end{eqnarray*}

qui est entier, vu qu’il s’agit d’un produit d’entiers. Ceci règle la question.

Remarque

Posons n=a_{1}+\cdots+a_{r}. Le nombre entier :

    \[\frac{n!}{a_{1}!\cdots a_{r}!}\]

est ce qu’on appelle un coefficient multinomial . Il est parfois noté :

    \[\binom{n}{a_{1},\cdots,a_{r}}\]

et admet l’interprétation combinatoire suivante.

Etant donnés n objets et r cases numérotées de 1 à r, cet entier indique le nombre de façons de placer :

  • a_{1} objets dans la case 1,
  • a_{2} objets dans la case 2,
  • etc …,
  • les n-\left(a_{1}+\cdots+a_{r-1}\right)=a_{r} objets restants dans la case r.

Lorsque r=2 (et donc n=a_{1}+a_{2}), on retrouve le coefficient binomial ordinaire :

    \[\binom{n}{a_{1}}=\frac{\left(a_{1}+a_{2}\right)!}{a_{1}!\thinspace a_{2}!}\]

Si l’un des deux entiers a ou b vaut 0 ou 1, le résultat est évidemment vrai.

Supposons maintenant que a,b\geqslant2.

Alors a+b\leqslant ab, car \left(a-1\right)\left(b-1\right)\geqslant1. Il s’ensuit que \left(a+b\right)!\mid\left(ab\right)!

Par ailleurs a!\thinspace b!\mid\left(a+b\right)! puisque :

    \[\frac{\left(a+b\right)!}{a!\:b!}=\binom{a+b}{a}\in\mathbb{N}\]

Finalement, par transitivité :

    \[\boxed{a!\thinspace b!\mid\left(ab\right)!}\]

Selon la formule du pion :

    \[k\binom{nk}{k}=nk\binom{nk-1}{k-1}\]

d’où, en simplifiant par k :

    \[\binom{nk}{k}=n\binom{nk-1}{k-1}\]

et donc :

(\diamondsuit)   \[\boxed{n\mid\binom{nk}{k}}\]

Montrons à présent, par récurrence sur a (l’entier b est fixé) que :

    \[a!\,\left(b!\right)^{a}\,\vert\,\left(ab\right)!\]

Pour a=1, c’est évident. Supposons que, pour un certain entier a\geqslant1, il existe Q\in\mathbb{N}^{\star} tel que \left(ab\right)!=Q\,a!\,\left(b!\right)^{a}. Alors :

    \begin{eqnarray*}\left(\left(a+1\right)b\right)! & = & \left(ab+b\right)!\\ & = & \left(ab\right)!\,\left(ab+1\right)\cdots\left(ab+b\right)\\ & = & Q\,a!\,\left(b!\right)^{a}\,b!\,\binom{\left(a+1\right)b}{b}\end{eqnarray*}

Or d’après \left(\diamondsuit\right) :

    \[\exists R\in\mathbb{N}^{\star};\,\binom{\left(a+1\right)b}{b}=\left(a+1\right)R\]

Ainsi :

    \[\left(\left(a+1\right)b\right)!=QR\,\left(a+1\right)!\,\left(b!\right)^{a+1}\]

ce qui montre que :

    \[\left(a+1\right)!\thinspace\left(b!\right)^{a+1}\mid\left(\left(a+1\right)b\right)!\]

comme souhaité. En conclusion :

    \[\boxed{\forall\left(a,b\right)\in\mathbb{N}^{2},\thinspace a!\,\left(b!\right)^{a}\,\vert\,\left(ab\right)!}\]

L’inégalité \left(2n\right)!\leqslant2\:n^{2n} est vraie pour n=1 (c’est une égalité).

Supposons-la vraie pour un certain n\geqslant1. Alors :

    \begin{eqnarray*} \left(2n+2\right)! & = & \left(2n+2\right)\left(2n+1\right)\left(2n\right)!\\ & \leqslant & \left(2n+2\right)\left(2n+1\right)2\thinspace n^{2n} \end{eqnarray*}

Pour conclure, il suffit de voir que :

    \[\left(2n+2\right)\left(2n+1\right)n^{2n}\leqslant\left(n+1\right)^{2n+2}\]

c’est-à-dire :

(\spadesuit)   \[2\left(2n+1\right)n^{2n}\leqslant\left(n+1\right)^{2n+1}\]


Or, la suite de terme général \left(1+\frac{1}{n}\right)^{n} est croissante et de premier terme 2, donc :

    \[2\leqslant\left(1+\frac{1}{n}\right)^{n}\]

et donc :

    \[4\thinspace n^{2n}\leqslant\left(n+1\right)^{2n}\]

d’où \left(\spadesuit\right) puisque 2\left(2n+1\right)\leqslant4\left(n+1\right).

On a prouvé par récurrence que :

    \[\boxed{\forall n\in\mathbb{N}^\star,\,\left(2n\right)!\leqslant2\:n^{2n}}\]

Voici maintenant une autre preuve, plus élégante.

On observe que :

    \[\left(2n\right)!=2n^{2}\prod_{k=1}^{n-1}k\left(2n-k\right)\]

Or, pour tout k\in\left\llbracket 1,n-1\right\rrbracket :

    \[k\left(2n-k\right)\leqslant n^{2}\]

puisque :

    \[n^{2}-k\left(2n-k\right)=n^{2}-2kn+k^{2}=\left(n-k\right)^{2}\geqslant0\]

Il en résulte que :

    \[\left(2n\right)!\leqslant2n^{2}\left(n^{2}\right)^{n-1}=2\thinspace n^{2n}\]

Commençons par établir le corollaire suivant de la formule de Legendre :

Corollaire

Etant donnés n\in\mathbb{N} et p\in\mathbb{P}, on note S_{p}\left(n\right) la somme des chiffres en base p de n. Alors :

    \[v_{p}\left(n!\right)=\frac{n-S_{p}\left(n\right)}{p-1}\]

Preuve (cliquer pour déplier / replier)

Décomposons n en base p :

    \[n=\sum_{k=0}^{d}\,a_{k}p^{k}\]

avec :

    \[\begin{array}{cc}\forall k\in\left\llbracket 0,d\right\rrbracket , & a_{k}\in\left\llbracket 0,p-1\right\rrbracket \\a_{p}\neq0\end{array}\]

Pour tout i\in\left\llbracket 1,d\right\rrbracket :

(\star)   \[\left\lfloor \frac{n}{p^{i}}\right\rfloor =\left\lfloor \sum_{k=i}^{d}\,a_{k}p^{k-i}+\sum_{k=0}^{i-1}\,a_{k}p^{k-i}\right\rfloor =\sum_{k=i}^{d}\,a_{k}p^{k-i}\]

car :

    \[\sum_{k=i}^{d}\,a_{k}p^{k-i}\in\mathbb{N}\]

et

    \[0\leqslant\sum_{k=0}^{i-1}\,a_{k}p^{k-i}\leqslant\left(p-1\right)\sum_{k=0}^{i-1}p^{k-i}<\left(p-1\right)\sum_{j=1}^{\infty}\frac{1}{p^{j}}=1\]

Donc, d’après la formule de Legendre et la relation \left(\star\right) :

    \begin{eqnarray*}v_{p}\left(n!\right) & = & \sum_{i=1}^{d}\left\lfloor \frac{n}{p^{i}}\right\rfloor \\ & = & \sum_{i=1}^{d}\left(\sum_{k=i}^{d}\,a_{k}p^{k-i}\right)\\ & = & \sum_{k=1}^{d}\left(a_{k}\sum_{i=1}^{k}p^{k-i}\right)\\ & = & \sum_{k=1}^{d}a_{k}\frac{p^{k}-1}{p-1}\end{eqnarray*}

Or {\displaystyle S_{p}\left(n\right)=\sum_{k=0}^{d}\,a_{k}} et la relation annoncée en résulte.

Venons-en maintenant à l’exercice. La condition 2^{n-1}\mid n! équivaut à v_{2}\left(n!\right)\geqslant n-1.

Or, en remplaçant p par 2 dans le corollaire ci-dessus :

    \[v_{2}\left(n!\right)=n-s\left(n\right)\]

où s\left(n\right) désigne la somme des chiffres binaires de n ou, ce qui revient au même, le nombre 1 dans l’écriture binaire de n.

Ainsi, pour tout n\in\mathbb{N}^{\star} :

    \[2^{n-1}\mid n!\Leftrightarrow s\left(n\right)\leqslant1\]

Cette dernière condition signifie bien sûr que s\left(n\right)=1, c’est-à-dire que n est une puissance de 2. En conclusion :

    \[\boxed{\forall n\in\mathbb{N}^\star,\,2^{n-1}\mid n!\Leftrightarrow\exists q\in\mathbb{N},\,n=2^q}\]

exercice 9 difficile

La formule de Legendre donne :

    \[v_{p}\left(\frac{\left(30n\right)!\thinspace n!}{\left(15n\right)!\thinspace\left(10n\right)!\thinspace\left(6n\right)!}\right)=\sum_{k=1}^{\infty}\left(\left\lfloor \frac{30n}{p^{k}}\right\rfloor +\left\lfloor \frac{n}{p^{k}}\right\rfloor -\left\lfloor \frac{15n}{p^{k}}\right\rfloor -\left\lfloor \frac{10n}{p^{k}}\right\rfloor -\left\lfloor \frac{6n}{p^{k}}\right\rfloor \right)\]

Or, il se trouve que, pour tout x\in\mathbb{R} :

    \[\left\lfloor 30x\right\rfloor +\left\lfloor x\right\rfloor -\left\lfloor 15x\right\rfloor -\left\lfloor 10x\right\rfloor -\left\lfloor 6x\right\rfloor \geqslant0\]

On peut établir ceci en se limitant au cas où x\in\left[0,1\right[, car d’une part \forall\left(t,n\right)\in\mathbb{R}\times\mathbb{Z},\thinspace\left\lfloor t+n\right\rfloor =\left\lfloor t\right\rfloor +n et d’autre part 30+1-15-10-6=0.

Soit donc x\in\left[0,1\right[ et soit k=\left\lfloor 30x\right\rfloor . Alors :

    \[x\in\left[\frac{k}{30},\frac{k+1}{30}\right[,\quad\mbox{avec }0\leqslant k<30\]

Le tableau ci-dessous répertorie, pour chaque k, les valeurs de \left\lfloor 6x\right\rfloor , \left\lfloor 10x\right\rfloor , \left\lfloor 15x\right\rfloor et \left\lfloor 30x\right\rfloor .

On constate, à chaque fois, la positivité de \Phi\left(x\right)=\left\lfloor 30x\right\rfloor +\left\lfloor x\right\rfloor -\left\lfloor 15x\right\rfloor -\left\lfloor 10x\right\rfloor -\left\lfloor 6x\right\rfloor :

On notera que la fonction \Phi est à valeurs dans \{0,1\}.

Cette fonction a été utilisée par le mathématicien russe P. Tchebytchev pour établir le théorème selon lequel, pour tout x>1 :

    \[\frac{\lambda x}{\ln(x)}\leqslant\pi(x)\leqslant\frac{\mu x}{\ln(x)}\]

où \pi(x) désigne le nombre de nombres premiers inférieurs à x et \lambda,\mu sont des constantes telles que 0<\lambda<1<\mu.

Si un point n’est pas clair ou vous paraît insuffisamment détaillé, n’hésitez pas à poster un commentaire ou à me joindre via le formulaire de contact.

Partager cet article
    

Laisser un commentaire