Transformation binomiale

En mathématiques, dans le domaine de l'analyse combinatoire, une suite est la transformation binomiale d'une autre si elle calcule les différences d'ordre successif entre les termes consécutifs.

Cette transformation est en rapport avec la transformation d'Euler, qui est le lien entre les séries génératrices ordinaires de deux suites qui sont la transformée binomiale l'une de l'autre. Un cas particulier de la transformation d'Euler est parfois utilisé pour accélérer la convergence de séries alternées (voir l'accélération des séries). Un autre cas particulier apparaît dans une application aux séries hypergéométriques.

Définition

La transformée binomiale $T$ d'une suite $(a n)$ est la suite $(s n)$ définie par $s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{k},$ où les ${n \choose k}=C_{n}^{k}$ désignent les coefficients binomiaux.

La transformée binomiale s'avère être la suite des $n$ -ièmes différences de la suite originelle, avec signe négatif pour les différences impaires :

s_{0}=a_{0}

s_{1}=-(\triangle a)_{0}=-(a_{1}-a_{0})

s_{2}=(\triangle ^{2}a)_{0}=(a_{2}-a_{1})-(a_{1}-a_{0})=a_{2}-2a_{1}+a_{0}

. . .

s_{n}=(-1)^{n}(\triangle ^{n}a)_{0}

où $Δ$ est l'opérateur de différence.

Étant un opérateur linéaire, la transformation peut s'écrire comme

$s_{n}=(Ta)_{n}=\sum _{k=0}^{\infty }T_{nk}a_{k}$

où $T$ est une matrice de dimension infinie de coefficients $T_{nk}=(-1)^{k}{n \choose k}$ .

La suite de départ peut être retrouvée par $a_{n}=(Ts)_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}s_{k}.$ (Il existe de nombreuses démonstrations de cette propriété : voir par exemple le § « Formulation alternative » ci-dessous, ou l'article « Formule d'inversion de Pascal ».)

Cette transformation est donc une involution, c'est-à-dire $T\circ T={\rm {Id}}$ ou, en utilisant des notations indicielles :

$\sum _{k=0}^{\infty }T_{nk}T_{km}=\delta _{nm}$ où $δ$ est le symbole de Kronecker.

Formulation alternative

Une autre définition de la transformation binomiale change le signe ( $t_{n}=(-1)^{n}s_{n}$ ), en considérant la suite des différences finies en 0 de la suite $a$ (vue comme une fonction sur $\mathbb {N} \subset \mathbb {R}$ ) :

$t_{n}=\Delta ^{n}[a](0)=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}a_{k}.$

Avec ces notations, l'involutivité de la transformation $T$ ci-dessus équivaut à :

$a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}.$

On peut donc la déduire du fait que le polynôme d'interpolation de Lagrange $L$ des $n+1$ points $(0,a_{0}),\dots ,(n,a_{n})$ est égal à sa série de Newton en $0$ :

L(x)=\sum _{k=0}^{n}{x \choose k}\Delta ^{k}[L](0)=\sum _{k=0}^{n}{x \choose k}t_{k}

,

en particulier

a_{n}=L(n)=\sum _{k=0}^{n}{n \choose k}t_{k}

.

Cette transformée binomiale se trouve par la table des différences. Chaque ligne reprend les différences de la ligne précédente.

La suite $(t n) = (0, 2, 12, 48, 160, 480, \dots) = (n (n + 1)2 n -1)$ (ligne supérieure) est la transformée binomiale de la diagonale $(a n) = (0, 2, 8, 18, 32, 50, \dots) = (2 n 2)$ .

0		2		12		48		160		480
	2		10		36		112		320
		8		26		76		208
			18		50		132
				32		82
					50

Transformation d'Euler

Fonctions génératrices ordinaires

La transformation binomiale établit un lien entre les séries génératrices associées aux suites.

Soient les séries génératrices ordinaires

$f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}$ et $g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}.$

On tire

$g(x)=(Tf)(x)={\frac {1}{1-x}}\,f\left({\frac {-x}{1-x}}\right).$

Cette relation entre les séries génératrices ordinaires est appelée transformation d'Euler.

Elle permet par exemple de démontrer que la transformée binomiale d'une suite récurrente linéaire est une suite récurrente linéaire de même ordre.

Accélération de séries

En posant $x = -1$ dans la relation précédente, la transformation d'Euler est utilisée pour accélérer la convergence des séries alternées. En effet :

$\sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\Delta ^{n}a_{0}}{2^{n+1}}}.$

Les termes du membre de droite diminuent généralement beaucoup plus vite, permettant ainsi un calcul numérique rapide de la somme.

Fonction hypergéométrique

L'application de la transformation d'Euler à la fonction hypergéométrique $\,_{2}F_{1}$ donne la relation

$\,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(c-a,b;c;{\frac {z}{z-1}}\right).$

Fractions continues

La transformation binomiale, et ses variantes comme la transformation d'Euler, sont connues pour leur lien avec la représentation des réels par des fractions continues. Soit $x$ un réel représenté par la fraction continue (éventuellement généralisée) suivante : $x=[0;a_{1},a_{2},a_{3},\ldots ].$ Alors ${\frac {x}{\lambda x+1}}={\frac {1}{\lambda +{\tfrac {1}{x}}}}={\frac {1}{\lambda +[a_{1};a_{2},a_{3},\ldots ]}}={\frac {1}{[\lambda +a_{1};a_{2},a_{3},\ldots ]}}=[0;\lambda +a_{1},a_{2},a_{3},\ldots ].$

Fonction génératrice exponentielle

Considérons des séries génératrices exponentielles,

${\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}$

et

${\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}.$

Alors

${\overline {g}}(x)=(T{\overline {f}})(x)=e^{x}{\overline {f}}(-x).$

La sommation de Borel convertit les séries génératrices ordinaires en séries génératrices exponentielles.

Représentation intégrale

Lorsque la suite peut être interpolée par une fonction analytique complexe, alors la transformée binomiale de la suite peut être représentée par la moyenne d'une intégrale de Nörlund-Rice sur la fonction d'interpolation.

Généralisations

Prodinger^[1] a donné une transformation de type modulaire : $u_{n}=\sum _{k=0}^{n}{n \choose k}a^{k}(-c)^{n-k}b_{k}.$ Elle donne $U(x)={\frac {1}{cx+1}}B\left({\frac {ax}{cx+1}}\right)$ où $U$ et $B$ sont les séries génératrices ordinaires associées aux suites $(u n)$ et $(b n)$ .
Spivey et Steil^[2] ont défini la transformation montante k-binomiale par $\sum _{j=0}^{n}{n \choose j}j^{k}a_{j}$ et la transformation descendante k-binomiale par $\sum _{j=0}^{n}{n \choose j}j^{n-k}a_{j}.$ Ces deux transformations sont des endomorphismes du noyau de la transformation de Hankel d'une suite.

Opérateur de décalage

La transformation binomiale correspond à l'opérateur de décalage pour la suite des nombres de Bell, c'est-à-dire :

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$

où les $B n$ représentent les nombres de Bell.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Binomial transform » (voir la liste des auteurs).

↑ (en) Helmut Prodinger, Some information about the Binomial transform, 1992 [PDF].
↑ (en) Michael Z. Spivey et Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, 2006.

Voir aussi

Bibliographie

(en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition]

Articles connexes

[1] (en) Helmut Prodinger, Some information about the Binomial transform, 1992 [PDF].

[2] (en) Michael Z. Spivey et Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, 2006.

[1]

[2]