Fonction génératrice/Exercices/Série génératrice d'une suite

Exercice 1-1

Calculer le carré de la série formelle ${\frac {1}{1-X}}=\sum _{k\in \mathbb {N} }X^{k}$, puis vérifier que son produit par $(1-X)^{2}$ est bien égal à $1$.

Solution

$\sum _{k\in \mathbb {N} }1.X^{k}\sum _{j\in \mathbb {N} }1.X^{j}=\sum _{n\in \mathbb {N} }\left(\sum _{0\leq k\leq n}1.1\right)X^{n}=\sum _{n\in \mathbb {N} }\left(n+1\right)X^{n}$.

$\left(1-2X+X^{2}\right)\sum _{k\in \mathbb {N} }\left(k+1\right)X^{k}=1.\left(0+1\right)X^{0}+\left[1.\left(1+1\right)-2.\left(0+1\right)\right]X^{1}+\sum _{n\geq 2}\left[\left(n+1\right)-2n+\left(n-1\right)\right]X^{n}=1$.

 

Retrouver ce résultat par dérivation formelle.

Solution

${\frac {1}{(1-X)^{2}}}=\left({\frac {1}{1-X}}\right)'=\left(\sum _{k\in \mathbb {N} }X^{k}\right)'=\sum _{k\geq 1}kX^{k-1}=\sum _{n\in \mathbb {N} }\left(n+1\right)X^{n}$.

 

Exercice 1-2

Soit la suite $(a_{n})_{n\geq 0}$ définie par $a_{0}=a_{1}=1$ et $\forall n\geq 2,a_{n}=2a_{n-1}-a_{n-2}+2^{n-2}$.

1. On pose $A(X)=\sum _{n\geq 0}a_{n}X^{n}$. Montrer que $A(X)=1-X+(2X-X^{2})A(X)+{\frac {X^{2}}{1-2X}}$.
2. Montrer que $A(X)={\frac {1}{1-2X}}+{\frac {1}{1-X}}-{\frac {1}{(1-X)^{2}}}$.
3. En utilisant l'exercice précédent, en déduire une expression explicite de $a_{n}$.
4. La vérifier par récurrence.

Solution

1. $\sum _{n\geq 2}a_{n}X^{n}=2\sum _{n\geq 2}a_{n-1}X^{n}-\sum _{n\geq 2}a_{n-2}X^{n}+\sum _{n\geq 2}2^{n-2}X^{n}$ se réécrit $A(X)-1-X=2X(A(X)-1)-X^{2}A(X)+{\frac {X^{2}}{1-2X}}$, d'où le résultat.
2. D'après la question précédente, $(1-X)^{2}A(X)=1-X+{\frac {X^{2}}{1-2X}}$ donc $A(X)={\frac {1}{1-X}}+{\frac {X^{2}}{(1-2X)(1-X)^{2}}}$. On vérifie que ${\frac {X^{2}}{(1-2X)(1-X)^{2}}}={\frac {1}{1-X}}-{\frac {1}{(1-X)^{2}}}$, d'où le résultat.
3. D'après la question précédente, $\sum _{k\geq 0}a_{k}X^{k}=\sum _{k\geq 0}(2X)^{k}+\sum _{k\geq 0}X^{k}-\sum _{k\geq 0}(k+1)X^{k}$ donc $a_{k}=2^{k}-k$.
4. Cette égalité est bien vérifiée pour $k=0$ et pour $k=1$ et si, pour un certain $n\geq 2$, elle l'est pour $k=n-2$ et $k=n-1$, alors elle l'est pour $k=n$ car $2a_{n-1}-a_{n-2}+2^{n-2}=2(2^{n-1}-(n-{\cancel {1}}))-{\cancel {2^{n-2}}}+(n-{\cancel {2}})+{\cancel {2^{n-2}}}=2^{n}-n$.

 

Exercice 1-3

Reprendre la méthode précédente pour déterminer l’expression explicite du terme général de la suite $(g_{n})_{n\geq 0}$ définie par $g_{0}=g_{1}=1$ et $\forall n\geq 2\quad g_{n}=g_{n-1}+2g_{n-2}+(-1)^{n}$.

Solution

On pose $G(X)=\sum _{n\in \mathbb {N} }g_{n}X^{n}$.

$\sum _{n\geq 2}g_{n}X^{n}=\sum _{n\geq 2}g_{n-1}X^{n}+2\sum _{n\geq 2}g_{n-2}X^{n}+\sum _{n\geq 2}(-X)^{n}$ se réécrit

$G(X)-1-X=X(G(X)-1)+2X^{2}G(X)+{\frac {X^{2}}{1+X}}$, soit

$1+{\frac {X^{2}}{1+X}}=\left(1-X-2X^{2}\right)G(X)=\left(1+X\right)\left(1-2X\right)G(X)$, donc

$G(X)={\frac {1+X+X^{2}}{\left(1+X\right)^{2}\left(1-2X\right)}}={\frac {-1/9}{1+X}}+{\frac {1/3}{\left(1+X\right)^{2}}}+{\frac {7/9}{1-2X}}$ et

$g_{n}=(-1/9)(-1)^{n}+(1/3)(n+1)(-1)^{n}+(7/9)2^{n}={\frac {(3n+2)(-1)^{n}+7.2^{n}}{9}}$ (que l'on peut vérifier par récurrence).

 

Exercice 1-4

I) Pour tout entier $n>0$, on pose :

$S_{n}(X):=\sum _{j\geq 0}{\binom {n+j-1}{j}}X^{j}$.

Démontrer par récurrence, de deux façons, que $\forall n\in \mathbb {N} ^{*}\quad {\frac {1}{(1-X)^{n}}}=S_{n}(X)$ :

1. en utilisant que ${\frac {1}{(1-X)^{n}}}+{\frac {X}{(1-X)^{n+1}}}={\frac {1}{(1-X)^{n+1}}}$ ;
2. en utilisant que $\left({\frac {1}{(1-X)^{n}}}\right)'={\frac {n}{(1-X)^{n+1}}}$.

Retrouver ce résultat directement, en utilisant que la dérivée $m$-ième de ${\frac {1}{1-X}}$ est ${\frac {m!}{(1-X)^{m+1}}}$.

II) On considère la suite des polynômes de Tchebychev de seconde espèce,

$U_{n}(X)=\sum _{0\leq k\leq n/2}(-1)^{k}{\binom {n-k}{k}}(2X)^{n-2k}$

(cf. Sommation/Exercices/Formule du binôme#Exercice 5-11). À l'aide de la question I, montrer que sa série génératrice,

$\sum _{n\geq 0}T^{n}U_{n}(X)$, est égale à ${\frac {1}{1-2TX+T^{2}}}$.

III) Pour tous entiers naturels m, n, en développant de deux façons $S_{n+1}(X)S_{m+1}(X)$, déduire de la question I que pour tout entier r ≥ m + n,

$\sum _{j=n}^{r-m}{\binom {j}{n}}{\binom {r-j}{m}}={\binom {r+1}{m+n+1}}$.

Solution de la question I

1. La formule est déjà vraie pour $n=0$, avec par convention ${\binom {-1}{0}}=1$. Elle est héréditaire car

   ${\begin{aligned}S_{n}(X)+XS_{n+1}(X)&=\sum _{j\geq 0}{\binom {n+j-1}{j}}X^{j}+\sum _{i\geq 0}{\binom {n+i-1}{i}}X^{i+1}\\&=1+\sum _{j\geq 1}\left[{\binom {n+j-1}{j}}+{\binom {n+j-1}{j-1}}\right]X^{j}\\&=\sum _{j\geq 0}{\binom {n+j}{j}}X^{j}=S_{n+1}(X)\end{aligned}}$

   (on a utilisé la formule de Pascal).

   Remarque

   En initialisant la récurrence à $n=0$, on vient de redémontrer le cas particulier bien connu $n=1$. Inversement, on peut s'appuyer sur ce cas pour n'initialiser la récurrence qu'à $n=1$.

2. On démarre la récurrence à $n=1$. L'initialisation est acquise (cf. ci-dessus) et pour l'hérédité, on utilise l'indication, jointe au fait que

   ${\begin{aligned}S'_{n}(X)&=\sum _{j\geq 1}{\binom {n+j-1}{j}}jX^{j-1}=\sum _{k\geq 0}{\binom {n+k}{k+1}}(k+1)X^{k}\\&=n\sum _{k\geq 0}{\binom {n+k}{k}}X^{k}=nS_{n+1}(X).\end{aligned}}$

Retrouvons le résultat directement, en posant $F(X)={\frac {1}{1-X}}$. Alors, $F^{(m)}=m!F^{m+1}$ donc

${\frac {1}{(1-X)^{n}}}=F^{n}={\frac {1}{(n-1)!}}F^{(n-1)}={\frac {1}{(n-1)!}}\left(\sum _{k\geq 0}X^{k}\right)^{(n-1)}={\frac {1}{(n-1)!}}\sum _{k\geq n-1}{\frac {k!}{(k-n+1)!}}X^{k-n+1}=S_{n}(X)$.

Remarque : on peut aussi démontrer le résultat par une récurrence tout bête, à condition de savoir — cf.Combinatoire/Exercices/Combinaisons#Exercice 4-1, question d) — que $\sum _{j=0}^{k}{\binom {n+j-1}{j}}={\binom {n+k}{k}}$.

 

Solution de la question II

${\begin{aligned}\sum _{n\geq 0}T^{n}U_{n}(X)&=\sum _{n\geq 0}T^{n}\sum _{0\leq k\leq n/2}(-1)^{k}{\binom {n-k}{k}}(2X)^{n-2k}\\&=\sum _{k\geq 0}(-1)^{k}\sum _{n\geq 2k}{\binom {n-k}{n-2k}}T^{n}(2X)^{n-2k}\\&=\sum _{k\geq 0}(-1)^{k}\sum _{j\geq 0}{\binom {k+j}{j}}T^{2k+j}(2X)^{j}\\&=\sum _{k\geq 0}(-T^{2})^{k}S_{k+1}(2TX)\\&={\frac {1}{1-2TX}}\sum _{k\geq 0}\left({\frac {-T^{2}}{1-2TX}}\right)^{k}\\&={\frac {1}{1-2TX}}{\frac {1}{1+{\frac {T^{2}}{1-2TX}}}}\\&={\frac {1}{1-2TX+T^{2}}}.\end{aligned}}$

 

Solution de la question III

D'après la question I,

$S_{n+1}(X)S_{m+1}(X)={\frac {1}{(1-X)^{n+1}}}{\frac {1}{(1-X)^{m+1}}}={\frac {1}{(1-X)^{m+n+2}}}=S_{m+n+2}(X)$

donc

$\sum _{k\geq 0}{\binom {m+n+k+1}{m+n+1}}X^{k}=\sum _{i\geq 0}{\binom {n+i}{n}}X^{i}\sum _{j\geq 0}{\binom {m+j}{m}}X^{j}$

c'est-à-dire

$\forall k\geq 0\quad {\binom {m+n+k+1}{m+n+1}}=\sum _{i=0}^{k}{\binom {n+i}{n}}{\binom {m+k-i}{m}}$

ou encore :

$\forall r\geq m+n\quad {\binom {r+1}{m+n+1}}=\sum _{i=0}^{r-m-n}{\binom {n+i}{n}}{\binom {r-n-i}{m}}=\sum _{j=n}^{r-m}{\binom {j}{n}}{\binom {r-j}{m}}$.

 

Pour une preuve combinatoire du III, voir la question II de Sommation/Exercices/Sommations plus compliquées#Exercice 7-1.

Exercice 1-5

Cet exercice constitue la démonstration par Euler (en 1773) de la formule du binôme généralisée, dans le cas d'un exposant rationnel.

On définit (pour tout $r\in \mathbb {R}$) les coefficients binomiaux généralisés :

$\forall n\in \mathbb {N} \quad {\binom {r}{n}}={\frac {r\left(r-1\right)\left(r-2\right)\dots \left(r-n+1\right)}{n!}}$,

puis la série formelle

$T_{r}(X):=\sum _{n\in \mathbb {N} }{\binom {r}{n}}X^{n}$.

Pour tous réels $r,s$ (et tout $n\in \mathbb {N}$), on note $P_{n}\left(r,s\right)$ le $n$-ième coefficient de la série formelle produit $T_{r}(X)T_{s}(X)$ :

$T_{r}(X)T_{s}(X)=\sum _{n\in \mathbb {N} }P_{n}\left(r,s\right)X^{n}$.

1. Vérifier que si $r,s\in \mathbb {N}$ alors $P_{n}\left(r,s\right)={\binom {r+s}{n}}$.
2. Démontrer que $P_{n}\left(r,s\right)$ est un polynôme en $r$ et $s$ (à coefficients rationnels).
3. Déduire des deux questions précédentes que $\forall r,s\in \mathbb {R} \quad P_{n}\left(r,s\right)={\binom {r+s}{n}}$ (pour tout $n\in \mathbb {N}$), donc $T_{r}(X)T_{s}(X)=T_{r+s}(X)$.
4. En déduire que $\forall p\in \mathbb {Z} \quad \forall q\in \mathbb {N} ^{*}\quad \left(T_{\frac {p}{q}}(X)\right)^{q}=\left(1+X\right)^{p}$, en commençant par traiter le cas $p\in \mathbb {N}$.

Solution

1. Si $r,s\in \mathbb {N}$ alors, d'après la formule du binôme usuelle, $T_{r}(X)T_{s}(X)=\left(1+X\right)^{r}\left(1+X\right)^{s}=\left(1+X\right)^{r+s}=T_{r+s}(X)$.
2. $P_{n}(r,s)=\sum _{i+j=n}{\binom {r}{i}}{\binom {s}{j}}$.
3. Le polynôme $Q_{n}(R,S):=P_{n}(R,S)-\sum _{i+j=n}{\binom {R}{i}}{\binom {S}{j}}\in \mathbb {Q} \left[R,S\right]$ s'annule sur $\mathbb {N} \times \mathbb {N}$ donc c'est le polynôme nul. On peut détailler : pour tout $r\in \mathbb {N}$, $Q_{n}(r,S)\in \mathbb {Q} [S]$ est nul car il a une infinité de racines $s$ (tous les entiers naturels) ; donc le polynôme $Q_{n}(R,S)$, vu comme polynôme en $R$ à coefficients dans $\mathbb {Q} [S]$, est nul car, de même, il a une infinité de racines $r$.
4. D'après la question précédente (et la question 1), $\forall p\in \mathbb {N} \quad \forall q\in \mathbb {N} ^{*}\quad \left(T_{\frac {p}{q}}(X)\right)^{q}=T_{p}(X)=\left(1+X\right)^{p}$ et $T_{-{\frac {p}{q}}}(X)\,T_{\frac {p}{q}}(X)=T_{0}(X)=1$, donc $\left(T_{-{\frac {p}{q}}}(X)\right)^{q}=\left(1+X\right)^{-p}$.

 

Remarque

Si $r\notin \mathbb {N}$, d'après le critère de D'Alembert, le rayon de convergence de la série entière associée à $T_{r}$ est égal à $1$.

Références

• Ranjan Roy, Sources in the Development of Mathematics: Series and Products from the Fifteenth to the Twenty-first Century, Cambridge University Press, 2011 [lire en ligne], chap.4.3 (« Euler's proof for rational indices »)  ;
• L. Euler, « Demonstratio theorematis Neutoniani de evolutione potestatum binomii pro casibus, quibus exponentes non sunt numeri integri », Novi Commentarii academiae scientiarum Petropolitanae, vol. 19, 1775, p. 103-111 [texte intégral] (E465, présenté à l'Académie de Saint-Pétersbourg le 1^er juillet 1773).

Cette preuve est moins bien expliquée sur xymaths.free.fr, et carrément comprise de travers par R. F. Muirhead, « Against Euler's proof of the binomial theorem for negative and fractional exponents », Proc. Edinburgh Math. Soc., vol. 17, 1898, p. 38-41 [lien DOI].