n! en termes d’une série finie alternée
dans Arithmétique
salut,
je demande si vous pouvez m'aider à démontrer la formule suivante:
cordialement
Méhdi Pascal
Mehdi-Pascal@hotmail.fr
je demande si vous pouvez m'aider à démontrer la formule suivante:
cordialement
Méhdi Pascal
Mehdi-Pascal@hotmail.fr
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je sais que vous ne donnez que des indications, mais s'il vous plait expliquez moi encore plus,
cordialement
Je voulais démontrer cette égalité par récurrence.
On part de:
$\displaystyle \sum_{j=0}^{n+1} (-1)^j\binom{n+1}{j} (n+2-j)^{n+1}$
et on essaie de le relier à:
$\displaystyle \sum_{j=0}^{n} (-1)^j\binom{n}{j} (n+1-j)^{n}$
NB:
$n+2-j=(n+1-j)+1$
(je ne sais pas si cette remarque est pertinente)
$S(n+1)=\displaystyle \sum_{j=0}^{n+1} (-1)^j\binom{n+1}{j} (n+2-j)^{n+1}=(n+1) \sum_{j=0}^{n+1}\binom{n}{j} \dfrac{(n+2-j)^{n+1}}{n+1-j} $
On a aussi:
$S(n+1)=\displaystyle \sum_{j=0}^{n+1} (-1)^j\binom{n+1}{j} (n+2-j)^{n+1}=(n+1) \sum_{j=0}^{n+1}\binom{n}{j}\left(\dfrac{1}{n+1-j}+\sum_{k=1}^{n+1}\binom{n+1}{k}(n+1-j)^{k-1}\right)$
$S(n+1)=\displaystyle \sum_{j=0}^{n+1} (-1)^j\binom{n+1}{j} (n+2-j)^{n+1}=(n+2)^{n+1}+\sum_{j=0}^{n}(-1)^{j+1}\binom{n+1}{j+1}(n+1-j)^{n+1}=(n+2)^{n+1}+\\\displaystyle\sum_{j=0}^{n}(-1)^{j+1}\binom{n}{j}(n+1-j)^{n+1}+\sum_{j=0}^{n-1}(-1)^{j+1}\binom{n}{j+1}(n+1-j)^{n+1}$
Cela devrait mieux fonctionner. :-D
PS:
Bof.
$\displaystyle \binom{n}{j+1}=\dfrac{n!}{(j+1)!(n-j-1)!}=\dfrac{n-j}{j+1}\times \dfrac{n!}{j!(n-j)!}=\dfrac{n-j}{j+1}\binom{n}{j}$
$\displaystyle\sum_{j=0}^{n}(-1)^{j+1}\binom{n}{j}(n+1-j)^{n+1}=-(n+1)\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}(n+1-j)^{n}+\sum_{j=0}^{n}(-1)^{j}j\binom{n}{j}(n+1-j)^{n}$
Pour une identité combinatoire, un raisonnement combinatoire est plus reposant. Et quand on voit une somme alternée comme ici, on a de bonnes chances de rencontrer le principe d'inclusion-exclusion.
Soyons ambitieux : on va montrer que pour tout entier naturel $k$ et tout entier naturel $n$,
$$ n! = \sum_{j=0}^n (-1)^j \pmatrix{n\\ j}(n-j+k)^n\;.$$
Analysons les quantités qui apparaissent : $n!$, c'est le cardinal de l'ensemble $\mathfrak{S}(A)$ de l'ensemble des permutations de $A=\{1,\ldots,n\}$. Et dans la somme le premier terme est $(n+k)^n$, qui est le cardinal de l'ensemble $B^A$ des applications de $A$ dans $B=\{1,\ldots,n,\ldots,n+k\}$. Quel rapport entre les deux ? Bah, une permutation de $A$ n'est autre qu'une application de $A$ dans $B$ dont l'image contient $A$ (et est donc forcément égale à $A$). Autrement dit, en notant $F_i$ l'ensemble des applications de $A$ dans $B$ dont l'image ne contient pas $i$, on a
$$\mathfrak{S}(A)= B^A-\bigcup_{i=1}^n F_i\;.$$
Voila, yapuka compter en utilisant le principe d'inclusion-exclusion.
$\displaystyle S_n:=\sum_{j=0}^n (-1)^j\binom{n}{j} (n+1-j)^n$
On a:
$\displaystyle \sum_{j=0}^{n-1}(-1)^{j+1}\binom{n}{j+1}(n+1-j)^{n+1}=2(n+1)S_n-(n+2)\sum_{j=0}^n (-1)^j\binom{n+1}{j+1} (n+1-j)^n-\sum_{j=0}^n(-1)^j\binom{n}{j}j (n+1-j)^n$
Car:
1) $\displaystyle \binom{n}{j+1}=\dfrac{n-j}{j+1}\binom{n}{j}$
2) $\displaystyle \binom{n+1}{j+1}=\dfrac{n+1}{j+1}\binom{n}{j}$
et:
3)
$\begin{align}
\dfrac{(n+1-j)(n-j)}{j+1}\binom{n}{j}&=\binom{n}{j}\Big(n+2-(j+1)\Big)\left(\dfrac{n+1-(j+1)}{j+1}\right)\\
&=\binom{n}{j}\left(\dfrac{(n+1)(n+2)}{j+1}-2(n+1)+j\right)
\end{align}$
Par ailleurs, on a vu plus haut que:
$\displaystyle S_{n+1}=(n+2)^{n+1}+\sum_{j=0}^{n}(-1)^{j+1}\binom{n}{j}(n+1-j)^{n+1}+\sum_{j=0}^{n-1}(-1)^{j+1}\binom{n}{j+1}(n+1-j)^{n+1}$
et:
$\displaystyle\sum_{j=0}^{n}(-1)^{j+1}\binom{n}{j}(n+1-j)^{n+1}=-(n+1)S_n+\sum_{j=0}^{n}(-1)^{j}j\binom{n}{j}(n+1-j)^{n}$
Donc:
$\boxed{\displaystyle S_{n+1}=(n+1)S_n+(n+2)\left((n+2)^{n}-\sum_{j=0}^n (-1)^j\binom{n+1}{j+1} (n+1-j)^n\right)}$
Pour terminer cette démonstration par récurrence il faudrait montrer que:
$\displaystyle (n+2)^n=\sum_{j=0}^n (-1)^j\binom{n+1}{j+1} (n+1-j)^n$
Je ne produis pas des démonstrations à la minute. B-)-
Il se pourrait aussi que je perde tout intérêt à cette question. :-D
J'essaie de comprendre où plus loin, parce que j'ai du mal à extraire cette information de tes messages.
$\displaystyle (n+2)^n=\sum_{j=0}^n (-1)^j\binom{n+1}{j+1} (n+1-j)^n$
Numériquement cette égalité semble vraie.
Et cette égalité, si elle est vraie, n'est pas une évidence.
Je n'ai pas d'obligation de résultat, ni de rendement. Ce n'est pas un concours, ni un examen.
Un problème est pour moi un voyage. J'admire le paysage qui se dévoile au fur et à mesure du voyage.
Si je ne parviens pas à la fin du voyage, ou si je prends des chemins de traverse pour y parvenir, cela me convient parfaitement. L'important n'est pas le but mais le chemin. Je suis un flâneur. B-)
Voyons : à gauche le cardinal de l'ensemble des applications de $A=\{1,\ldots,n\}$ dans $C=\{1,\ldots,n+2\}$. A droite une somme dont le premier terme est $(n+1) (n+1)^n$. Bon, $(n+1)^n$ c'est le cardinal de l'ensemble $G_i$ des applications de $A$ dans $C$ dont l'image ne contient pas $i$ (pour $i=1,\ldots,n+1$). On a bien sûr
$$ C^A= \bigcup_{i=1}^{n+1} G_i\;.$$
Et yapuka compter avec le principe d'inclusion-exclusion.
Soit $K$ un corps commutatif , soit $I$ l'application identique de $K[X]$, et soit $T$ l'application de $K[X]$ dans $K[X]$ définie par : $TP(X)=P(X+1)$. Soit $\Delta=T-I$, qui est l'opérateur « différence finie », défini par : $\Delta P(X)=P(X+1)-P(X)$.
Ces « opérateurs » $T$, $I$, $\Delta$ sont des endomorphismes du $K$-espace vectoriel $K[X]$.
Traditionnellement, on écrit $TP$ pour $T(P)$ et idem pour $\Delta$ ou autre opérateur.
Si $\displaystyle P(X)=\overset{n}{\underset{k=0}{\sum }}a_{k}X^{k}$, $ n \in \mathbb N^* $, $a_{n}\neq 0$, alors le terme dominant de $\Delta P$ est $na_{n}X^{n-1}$.
Et ainsi de suite pour $\Delta^2 P$, etc.
Il en résulte que le polynôme $\Delta ^nP$ est constant et que cette constante est égale à $n!a_n$.
Or on a : $\displaystyle \Delta ^{n}=(T-I)^{n}=\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})(-1)^{n-k}T^{k}=\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})(-1)^{k}T^{n-k}$.
D'ordinaire c'est la première égalité qu'on utilise mais il semble qu'ici la seconde soit plus appropriée.
Elle signifie que tout polynôme $\displaystyle P(X)=\overset{n}{\underset{k=0}{\sum }}a_{k}X^{k}$ vérifie : $\displaystyle \overset{n}{\underset{k=0}{\sum }}(_{k}^{n})(-1)^{k}P(X+n-k)=a_{n}n!$.
Ce qui comprend et généralise l'égalité proposée.
Bonne soirée.
F. Ch.
23/10/2016
................................
\displaystyle
« Â À Ç É Ê È Î »
.
Un souvenir est, par définition, toujours achevé. B-)-
On peut réécrire l'égalité (à démontrer) sous la forme, plus agréable:
$\boxed{\displaystyle n!=(-1)^n\sum_{j=0}^{n}\binom{n}{j}(-1)^j(j+1)^n}$
Obtenue en faisant le changement de variable $j\leftarrow n-j$ et puisque $\binom{n}{j}=\binom{n}{n-j}$.
PS:
Soit,
$\displaystyle P_n(x)=(-1)^n\sum_{j=0}^{n}\binom{n}{j}(-1)^j(j+x)^n$
Numériquement, il me semble constater que pour tout $x$ entier relatif, on a:
$\displaystyle n!=P_n(x)$.
On pose pour tout $n$ entier naturel et pour tout $x$ réel,
$\displaystyle S_n(x)=\sum_{j=0}^n \binom{n}{j} (-1)^j(x-j)^n$
On a pour pour tout $n$ entier naturel et pour tout $x$ réel,
(1) $\boxed{S_{n+1}(x+1)=(x+1)S_{n}(x+1)+(n-x)S_n(x)}$
Pour le moment admettons cette identité.
On veut démontrer pour tout $n$ entier naturel, par récurrence, la propriété,
$\boxed{\mathcal{P}_n: \text{Pour tout } x\text{ réel, }S_n(x)=n!}$
Pour tout $x$, $S_0(x)=1=0!$
On suppose $\mathcal{P}_n$ vraie et on utilise l'identité (1) en remplaçant $x$ par $x-1$,
$S_{n+1}(x)=xS_n(x)+(n-x+1)S_n(-x)=xn!+(n-x+1)n!=n!(x+n-x+1)=(n+1)!$
Donc $\mathcal{P}_{n+1}$ est vraie et par récurrence $\mathcal{P}_n$ est vraie pour tout $n$ entier naturel.
Preuve de l'identité (1),
$\begin{align}
S_{n+1}(x+1)&=(-1)^{n+1}(x-n)^{n+1}+\sum_{j=0}^{n}\binom{n+1}{j}(-1)^j(x+1-j)^{n+1}\\
&=(-1)^{n+1}(x-n)^{n+1}+(x+1)\sum_{j=0}^{n} \binom{n+1}{j}(-1)^j(x+1-j)^n-\sum_{j=0}^{n} \binom{n+1}{j}(-1)^j j(x+1-j)^n\\
&=(-1)^{n+1}(x-n)^{n+1}+(x+1)\sum_{j=0}^{n} \binom{n}{j}\left(1+\dfrac{j}{n+1-j}\right)(-1)^j(x+1-j)^n-\\
&\qquad\qquad\sum_{j=0}^{n} \binom{n}{j}\left(\dfrac{nj}{n+1-j}+\dfrac{j}{n+1-j}\right)(-1)^j(x+1-j)^n\\
&=(x+1)S_n(x+1)+(-1)^{n+1}(x-n)^{n+1}+(x-n)\sum_{j=0}^{n} \binom{n}{j}\dfrac{j}{n+1-j}(-1)^j(x+1-j)^n\\
&=(x+1)S_n(x+1)+(-1)^{n+1}(x-n)^{n+1}-(x-n)\sum_{j=0}^{n-1} \binom{n}{j+1}\dfrac{j+1}{n-j}(-1)^j(x-j)^n\\
&=(x+1)S_n(x+1)-(x-n)\left(\sum_{j=0}^{n-1} \binom{n}{j}(-1)^j(x-j)^n+(-1)^n(x-n)^n\right)\\
&=(x+1)S_n(x+1)+(n-x)S_n(x)\\
\end{align}$
PS : J'essayais désespérément de trouver une relation entre $S_{n+1}(x)$ et des $S_k(x)$ avec $0<k\leq n$.
Je ne voyais pas, et pourtant c'était sous mes yeux, que $x$ devait varier.
Heureusement, j'ai eu de l'aide : https://www.math.upenn.edu/~wilf/Downld.html page 192.
Cela va tout de suite mieux quand tu sais que ce que tu recherches existe et qu'on te donne la formule. :-)
PS2 : Il se peut qu'on puisse obtenir cette relation de récurrence avec Sage avec les fonctions qui tournent autour de l'algorithme WZ et affiliés.
Une page que je trouve intéressante sur ces questions : http://arminstraub.com/teaching/specialfunctions-summer16
En sortant un $x-j$ de la puissance et en séparant en deux sommes on obtient avec $\displaystyle\binom{n}{j}=\dfrac n j \binom{n-1}{j-1}$ la relation: $u_{n,p}(x)=x u_{n,p-1}(x)+n u_{n-1,p-1}(x-1)$.
Puisque $u_{n,0}(x)$ est égal à 1 si $n=0$ et à $0$ si $n>0$ on montre rapidement, par récurrence sur $p$, que $u_{n,p}(x)$ est nul si $p<n$ et est égal à $n!$ si $p=n$.
On peut aussi montrer que $u_{n,n+1}(x)=(n+1)!\left(x-\dfrac n2\right)$.
La relation,
$\boxed{u_{n,n+1}(x)=(n+1)!\left(x-\dfrac n2\right)}$
N'est pas facile à deviner.
Dans la question initiale il n'y avait aucun paramètre.
Dans le message
http://www.les-mathematiques.net/phorum/read.php?5,1346454,1347376#msg-1347376
Je n'avais pas encore trouvé dans un livre la relation de récurrence, que je pressentais exister, indiquée plus haut.
Quand j'ai écrit:
$\boxed{\displaystyle n!=(-1)^n\sum_{j=0}^{n}\binom{n}{j}(-1)^j(j+1)^n}$
Je me suis douté que le $1$ de $(1+j)^n$ était la valeur d'un paramètre (habitude apprise en calculant des intégrales définies :-) )
J'ai vérifié avec PARI sur quelques exemples qui m'ont confirmé numériquement cette intuition.
Bien que, à cause des problèmes d'arrondis, je pensais que le paramètre devait être un entier.
La démonstration de la relation de récurrence que j'ai indiquée plus haut n'utilise pas, à mon grand étonnement, la formule utilisée pour construire le triangle de Pascal.
Sage a des fonctions pour trouver ce genre de relations mais je ne sais pas, du fait qu'il faut introduire obligatoirement un paramètre, si Sage peut donner les relations de récurrences trouvées (Sage ne tourne pas facilement sous Windows)
Maxima a des fonctions pour faire ce type de calculs mais elles sont très limitées, tu ne peux que calculer des sommes indéfinies, quand le programme y parvient.
Je ne sais pas si des fonctions existent pour GP PARI. Je n'ai pas été capable de trouver
Dans cette histoire, j'ai appris que:
$\sum_{k=0}^n \binom{n}{k}^2$ avait une forme close tandis que $\sum_{k=0}^n \binom{n}{k}^3$ n'en avait pas d'"élémentaire" semble-t-il (il y a une relation de récurrence que chacune de ces sommes vérifie cependant).
Et que Mary Celine Fasenmyer a ouvert la voie.
https://fr.wikipedia.org/wiki/Mary_Celine_Fasenmyer
Pour tout $n\geq 0$ entier et pour tout $x$ réel,
$\displaystyle \sum_{i=0}^{n} (-1)^i\binom{n}{i}(x-i)^n=n!$
La preuve utilise un raisonnement par récurrence.
On considère, pour tout $x$ réel et $n$ entier naturel la fonction $f_n$ définie sur $\mathbb{R}$,
$\displaystyle f_n(x)=\sum_{i=0}^{n} (-1)^i\binom{n}{i}(x-i)^n$
Pour tout $x$ réel, $f_0(x)=1$.
On suppose que pour tout $x$ réel, $f_k(x)=k!$.
$\displaystyle f_{k+1}^{\prime}(x)=(k+1)\sum_{i=0}^{k+1} (-1)^i\dfrac{(k+1)!}{i!(k+1-i)!}(x-i)^k$
On sort le terme $i=k+1$ de la somme et on utilise le fait que:
$\displaystyle\dfrac{(k+1)!}{i!(k+1-i)!}=\binom{k}{i}\left(1+\dfrac{i}{k+1-i}\right)$
Il vient,
$\begin{align}
\displaystyle f_{k+1}^{\prime}(x)&=(k+1)\left[\sum_{i=0} (-1)^i\binom{k}{i}(x-i)^k+(-1)^{k+1}(x-(k+1))^k+\sum_{i=1}^{k}(-1)^i\dfrac{k!(x-i)^k}{(i-1)!(k+1-i)!}\right]\\
&=(k+1)\left[f_k(x)+\sum_{i=0}^k(-1)^{i+1}\binom{k}{i}(x-1-i)^k\right]\\
&=(k+1)\left[f_k(x)-f_k(x-1)\right]\\
&=(k+1)\left(k!-k!\right)\\
&=0
\end{align}$
Ainsi, la fonction $f_{k+1}$ définie sur $\mathbb{R}$ est constante.
En particulier, on a, pour tout $x$ réel,
$f_{k+1}(x)=f_{k+1}(k+1)=(k+1)f_{k}(k+1)=(k+1)k!=(k+1)!$
Donc, par récurrence on a bien,
Pour tout $n$ entier et pour tout $x$ réel, $f_n(x)=n!$
Source:
An Algebraic Identity Leading to Wilson's Theorem , Sebastián Martín Ruiz,
https://arxiv.org/ftp/math/papers/0406/0406086.pdf
Pour tout entier $n \geq 1$, $\displaystyle n!=\sum_{k=1}^{n} (-1)^{n-k} \binom {n}{k}k^n$
Pour tout $x$ réel on a:
$e^x=1+x+x^2g(x)$
avec $g$ une fonction de $\text{C}^{\infty}\left(\mathbb{R}\right)$.
Pour tout $n$ entier naturel positif,
$(e^x-1)^n=(x+x^2g(x))^n$
On a:
$\displaystyle (e^x-1)^n=\sum_{k=0}^n \binom{n}{k}e^{kx}(-1)^{n-k}\tag1$
et:
$\begin{align}
\displaystyle (x+x^2g(x))^n&=\sum_{k=0}^n \binom{n}{k}x^{k}x^{2n-2k}g(x)^{n-k}\\
&=\sum_{k=0}^n \binom{n}{k}x^{2n-k}g(x)^{n-k}\\
&=x^n+x^{n+1}\sum_{k=0}^{n-1} \binom{n}{k}x^{n-k-1}g(x)^{n-k}\\
&=x^n+x^{n+1}h(x) \tag2
\end{align}$
avec pour tout $x$ réel,
$\displaystyle h(x)=\sum_{k=0}^{n-1} \binom{n}{k}x^{n-k-1}g(x)^{n-k}$
$h$ est une fonction de $\text{C}^{\infty}\left(\mathbb{R}\right)$.
Si on dérive $n$ fois la fonction définie par (1) et qu'on évalue la fonction obtenue en $x=0$, on a:
$\displaystyle \sum_{k=1}^n \binom{n}{k}k^n(-1)^{n-k}$
(il n'y a pas d'indice $k=0$ puisque pour tout $x$ réel et $k=0$, $e^{kx}=1$ )
D'autre part, si on dérive $n$ fois la fonction définie pour tout $x$ réel par $u(x)=x^n$ et qu'on évalue en $x=0$ la fonction obtenue on a:
$n!$
Par ailleurs, si on dérive $n$ fois la fonction définie pour tout $x$ réel par $v(x)=x^n+x^{n+1}h(x)$, d'après la formule de Leibniz on a:
$\begin{align}\left(x^{n+1}h(x)\right) ^{(n)}&=\sum_{j=0}^{n} (n+1)\times ....\times (n+1-j+1)\binom{n}{j}x^{n+1-j}h^{(j)}(x)\\
&=x\sum_{j=0}^{n} (n+1)\times ....\times (n+1-j+1)\binom{n}{j}x^{n-j}h^{(j)}(x)\\
&=xk(x)
\end{align}$
avec pour tout $x$ réel, $\displaystyle k(x)=\sum_{j=0}^{n} (n+1)\times ....\times (n+1-j+1)\binom{n}{j}x^{n-j}h^{(j)}(x)$
Ainsi, la dérivée $n$-ème de la fonction définie par $(2)$, évaluée en $x=0$ vaut $n!$.
Et puisque les fonctions définies par $(1)$ et $(2)$ sont égales on a:
Pour tout entier $n \geq 1$, $\displaystyle n!=\sum_{k=1}^{n} (-1)^{n-k} \binom {n}{k}k^n$
(preuve trouvée dans l'article: https://www.emis.de/journals/INTEGERS/papers/f18/f18.pdf
il y a une autre preuve, combinatoire, de ce résultat dans le même papier. J'ai pris connaissance de cet article en parcourant: https://arxiv.org/pdf/1703.06401.pdf )