27 décembre 2017

9 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • Démarrage trompeur

    le 3 janvier 2018 à 17:27, par François Sauvageot

    Oui, merci Patrick pour l’article. C’est un chouette sujet, mais il reste assez difficile. Cette combinatoire n’est plus trop à la mode et donnera donc du fil à retordre à des élèves de secondaire ... et même à des étudiant.e.s du supérieur !

    Que ce soit les coefficients binomiaux (dont l’interprétation n’est pas vraiment donnée dans le secondaire) ou la dérivation discrète (qui est absente des considérations du secondaire), les bases sont fragiles. C’est d’ailleurs pourquoi, en MP*, je passe pas mal de temps sur l’opérateur $\Delta$ de Newton, ou dérivée discrète : $\Delta=\tau-Id$ : $P\mapsto P(X+1)-P$.

    La base adaptée aux calculs avec $\Delta$ est celle des polynômes de Newton \[\Gamma_n={X\choose n}=\frac{X(X-1)\cdots(X-n+1)}{n!}\]
    puisque $\Delta(\Gamma_{n+1})=\Gamma_n$, en parfaite analogie avec la base de Taylor $\frac{X^n}{n!}$ adaptée aux calculs avec la dérivée et donc le développement en série de Taylor.

    On obtient rapidement le fait suivant pour un polynôme $P$ de degré $n$ :
    \[P=\sum_{k=0}^na_k\Gamma_k\Longleftrightarrow\forall k\in[0;n]\,a_k=\Delta^k(P)(0)\]
    puisque tous les $\Gamma_k$ sont nuls en 0, sauf $\Gamma_0$ qui y vaut 1.

    Comme
    \[\Delta^k=(\tau-I)^k=\sum_{i=0}^k(-1)^{k-i}{k\choose i}\tau^i\]
    on en déduit que les coefficients de $P$ dans le développement en série de Newton est obtenu à partir des premières valeurs de $P$ sur les entiers de la façon suivante :
    \[a_k=(-1)^k\sum_{i=0}^k(-1)^i{k\choose i}P(i).\]
    Ce qui est remarquable est que cette construction est stable par élévation du degré ! Donc on peut faire de l’inter(extra)polation itérative à peu de frais : on cherche un polynôme de degré $n$ qui fait le job en s’adaptant aux $n+1$ premières valeurs constatées et ensuite, si on n’est pas satisfait, on augmente le degré en ne calculant qu’un coefficient de plus à chaque fois.

    Ainsi, quand on cherche à deviner une formule que l’on espère polynomiale, on devrait enseigner qu’il faut chercher la décomposition dans la base des polynômes de Newton. C’est d’ailleurs comme ça qu’on peut trouver facilement des erreurs dans des reports dans des listes obtenues avec des formules polynomiales : apparait par linéarité une erreur qui, par itération de $\Delta$, fournit des coefficients binomiaux (correspondant au dévelopement de $X^n$ dans la base de Newton). Il faut aussi faire concorder les observations avec des valeurs de 0 à $n$. Ici on part de $n=2$ et on peut soit décaler de 2, soit commencer à $n=1$ en prenant la valeur 1 (c’est plus dur d’imaginer une valeur avec $n=0$).

    Si $P(k)=b^k$, on trouve $a_k=(b-1)^k$. Il y a d’ailleurs un sujet sympa de l’X à ce propos (X 2011, filière MP, composition B) : accélération de convergence via la transformation d’Euler. Ici $b=2$ et donc les coefficients sont l’unité !
    L’écart entre $P_4=\sum_{k=0}^4\Gamma_k$ et $2^X$ est donc donné par les termes manquants : $2^n-P_4(n)=\sum_{k=5}^n\Gamma_k(n)$. Pour $n=5$, on trouve $\Gamma_5(5)={5\choose 5}=1$. En fait on se balade sur la $n$-ème ligne du triangle de Pascal et on somme les cinq premiers termes, donc sur la cinquième ligne on ne néglige qu’un terme qui vaut 1.

    Autrement dit quand on dit : $1$, $2$, $4$ ... on devrait penser directement $\Gamma_0$, $\Gamma_0+\Gamma_1$, $\Gamma_0+\Gamma_1+\Gamma_2$, etc. i.e. $1$, $n$, $\frac{n^2-n+2}2$, etc. tout en ayant en tête que la somme de la série $\sum\Gamma_k$ est $2^X$ !

    Si $P(k)=k^{n+1}$, on peut en effet penser aux polynômes de Bernoulli puisque, par définition (ou presque) de ces polynômes, on a $\Delta(B_{n+1})=(X^{n+1})'=(n+1)X^n$, i.e. ce sont eux qui permettent de sommer des puissances $n$-èmes. Toutefois aucune formule simple ne m’est apparue en rédigeant ces lignes ...

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.