Formule d'itération de Pascal

En mathématiques, plus précisément en combinatoire, la formule d'itération de Pascal, appelée aussi formule de la gouttière (ou formule de la crosse de hockey par traduction de l'anglais «Hockey-stick identity») est une formule exprimant la somme de termes consécutifs d'une colonne du triangle de Pascal. La formule donne le résultat d'une somme finie de termes consécutifs d'une colonne du triangle de Pascal, débutant au premier terme non nul, comme étant le coefficient binomial situé à droite et en-dessous du dernier terme. Pour les termes de la colonne p, allant de la ligne p jusqu'à la ligne n, la formule s'écrit : En utilisant la complétion du triangle de Pascal par des termes nuls, on peut aussi l'écrire : . Et en utilisant la symétrie des coefficients binomiaux, on obtient la somme d'une diagonale descendante : . vignette|Les cases rouges sont celles utilisées par la formule pour ; en bleu, cas d'une diagonale descendante pour les mêmes valeurs. L'expression « formule d'itération de Pascal » est une abréviation de « formule d'itération de la relation de Pascal » ; on trouve aussi la forme « formule de Pascal itérée » . Les expressions : formule « de la gouttière », ou « de la crosse de Hockey », viennent de l'analogie entre la situation des termes de la somme et de son résultat dans le triangle de Pascal et la forme des objets correspondants (voir figure ci-contre). La formule est appelée « sommation sur l'indice du haut » dans le livre Concrete Mathematics. Diverses démonstrations utilisent la relation de Pascal : On a . En faisant , on obtient , ce qui donne bien la formule. Cette démonstration nécessite de connaître la formule a priori. Initialisation ; pour la formule s'écrit . Hérédité ; hypothèse de récurrence : Alors ce qui achève la récurrence. D'après la formule des séries géométriques, on a : Or dans le premier membre, le coefficient de est égal à , et dans le second membre, il est égal à , d'où la formule.