7.2 Quelques outils

Comme nous venons de le mentionner, les récurrences jouent un rôle très important en combinatoire, et nous avons déjà eu l’occasion d’en rencontrer plusieurs depuis le début de la session. Bien qu’occasionnellement nous avons été en mesure de les transformer sous forme explicite, la plupart du temps nous avons dû nous contenter de la récurrence, faute d’avoir les outils nécessaire pour trouver cette forme explicite. Dans ce chapitre nous sommes intéressé à remédier à ce problème, et développer des méthodes systématiques de résolution des récurrences.

Les deux méthodes les plus importantes pour résoudre les récurrences sont les fonctions génératrices et la méthode du polynôme caractéristique. La méthode des fonctions génératrices, bien que difficile, est la méthode la plus générale à notre disposition. D’un autre côté, la méthode du polynôme caractéristique est beaucoup plus simple, mais s’applique seulement dans quelque cas particulier. Des méthodes, tel que la dérivation symbolique, peut cependant nous permettre de réécrire certaine récurrence sous une forme différente pour ensuite pouvoir appliquer la méthode du polynôme caractéristique.

Avant de ce lancer dans l’étude des fonctions génératrices, il nous est cependant nécessaire de faire un détour, et d’étudier certain outils qui nous serons essentielles pour appliquer correctement cette méthode.

La factorisation des polynômes

Autant dans la méthode des fonctions génératrices que dans celle du polynôme caractéristique, il nous est souvent nécessaire de factoriser un polynôme sous forme de facteur irréductible qui peuvent être soit de degré 1\displaystyle 1 ou 2\displaystyle 2. Le théorème fondamental de l’algèbre nous affirme que cela est toujours possible, bien qu’il nous donne aucune information sur comment obtenir une telle factorisation.

Le cas des polynômes de degré 2\displaystyle 2 est facile. On peut utiliser la technique du produit-somme, ou la formule quadratique.

Exemple 7.2.1.

On veut factoriser le polynôme x2−5⁢x+6\displaystyle x^{2}-5x+6. Pour ce faire, nous avons deux méthodes:

  • —
    ​

    Méthode du produit-somme: On cherche des entiers x1,x2\displaystyle x_{1},x_{2} pour lesquels la somme est −5\displaystyle-5 et le produit est 6\displaystyle 6. Par essaie et erreur, on détermine facilement que x1=−2\displaystyle x_{1}=-2 et x2=−3\displaystyle x_{2}=-3. On obtient donc:

    x2−5⁢x+6=(x+x1)⁢(x+x2)=(x−2)⁢(x−3)\displaystyle x^{2}-5x+6=(x+x_{1})(x+x_{2})=(x-2)(x-3)
  • —
    ​

    Méthode de la formule quadratique: On commence par calculer x1\displaystyle x_{1} et x2\displaystyle x_{2} à l’aide de la formule quadratique, ce qui nous donne:

    −b±b2−4⁢a⁢c2⁢a=5±(−5)2−4⁢(1)⁢(6)2⁢(1)=5±12=5±12=2⁢ et ⁢3\displaystyle\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}=\frac{5\pm\sqrt{(-5)^{2}-4(1)(6)% }}{2(1)}=\frac{5\pm\sqrt{1}}{2}=\frac{5\pm 1}{2}=2\textrm{ et }3

    On a donc x1=2\displaystyle x_{1}=2 et x2=6\displaystyle x_{2}=6, ce qui nous donne la factorisation suivante:

    x2−5⁢x+6=(x−x1)⁢(x−x2)=(x−2)⁢(x−3)\displaystyle x^{2}-5x+6=(x-x_{1})(x-x_{2})=(x-2)(x-3)
  • —
    ​

    Remarque importante: Remarquez que les signes sont traité différemment dans les deux méthodes, ce qui est souvent source d’erreur.

Exemple 7.2.2.

On veut factoriser le polynôme 3⁢x2+5⁢x+9\displaystyle 3x^{2}+5x+9. Pour ce faire, nous allons utiliser à nouveau la formule quadratique:

−5±52−4⁢(3)⁢(9)2⁢(3)\displaystyle\frac{-5\pm\sqrt{5^{2}-4(3)(9)}}{2(3)}

On remarque immédiatement que 52−4⁢(3)⁢(9)=−83<0\displaystyle 5^{2}-4(3)(9)=-83<0. Le polynôme ne possède donc aucune racine dans les nombres réels. On peut donc affirmer qu’il est irréductible dans ℝ\displaystyle\mathbb{R}.

Exemple 7.2.3.

On veut factoriser le polynôme 15⁢x2−2⁢x−8\displaystyle 15x^{2}-2x-8. Pour ce faire, appliquons la formule quadratique:

2±(−2)2−4⁢(15)⁢(−8)2⁢(15)=2±48430=2±2230=2430⁢ et ⁢−2030\displaystyle\frac{2\pm\sqrt{(-2)^{2}-4(15)(-8)}}{2(15)}=\frac{2\pm\sqrt{484}}% {30}=\frac{2\pm 22}{30}=\frac{24}{30}\textrm{ et }\frac{-20}{30}

On obtient donc la factorisation suivante:

15⁢x2−2⁢x−8=15⁢(x−2430)⁢(x+2030)=15⁢(x−45)⁢(x+23)=(5⁢x−4)⁢(3⁢x+2)\displaystyle 15x^{2}-2x-8=15\left(x-\frac{24}{30}\right)\left(x+\frac{20}{30}% \right)=15\left(x-\frac{4}{5}\right)\left(x+\frac{2}{3}\right)=(5x-4)(3x+2)

Attention: lorsque l’on a un polynôme de la forme a⁢x2+b⁢x+c\displaystyle ax^{2}+bx+c avec des racines x1\displaystyle x_{1} et x2\displaystyle x_{2}, la factorisation peut s’écrire sous la forme a⁢(x−x1)⁢(x−x2)\displaystyle a(x-x_{1})(x-x_{2}). Une erreur très courante est d’oublier le facteur a\displaystyle a dans la factorisation.

Comme nous venons de le voir, les polynômes réductibles de degrés 2\displaystyle 2 sont faciles à factoriser. Des formules similaires, bien que plus compliqué, existe aussi pour les polynômes de degré 3\displaystyle 3 et 4\displaystyle 4. Par contre, le théorème d’Abel-Galois nous affirme qu’aucune telle formule n’existe pour les polynômes généraux de degré 5\displaystyle 5 ou plus. Étant donné donné ces limitations, nous allons ici présenter une méthode différente pour trouver les racines (et donc factoriser) des polynômes de degrés quelconques. La méthode s’applique cependant uniquement pour les racines rationnelles d’un polynôme à coefficients entiers, ce qui est suffisant pour la grande majorité des problèmes d’énumération en combinatoire. La méthode consiste essentiellement à trouver une liste de candidat potentiel pour les racines du polynôme, puis de les tester un par un. Une fois qu’une racine est trouvé, on effectue alors la division euclidienne pour trouver un nouveau polynôme de degré plus petit. C’est le théorème des racines rationnelles qui nous permet dans un premier temps d’établir une liste de candidat.

Théorème 7.2.1:

Théorème des racines rationnelles. Si p⁢(x)\displaystyle p(x) est un polynôme à coefficient entier tel que:

p⁢(x)=an⁢xn+an−1⁢xn−1+…+a1⁢x+a0\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}

où an\displaystyle a_{n} et a0\displaystyle a_{0} sont différent de zéro, alors toutes les racines rationnelles x=pq\displaystyle x=\frac{p}{q} écrite en fraction réduite satisfont les deux propriétés suivantes:

  1. 1.
    ​

    p\displaystyle p est un diviseur entier du terme a0\displaystyle a_{0}

  2. 2.
    ​

    q\displaystyle q est un diviseur entier du terme an\displaystyle a_{n}

Il faut noter que le théorème des racines rationnelles nous donne une liste de candidat qui peuvent être soit positif ou négatif. Question de réduire la liste des possibilités, nous pouvons ensuite utiliser la règle des signes de Descartes pour déterminer le nombre de racines positives et le nombre de racines négatives.

Théorème 7.2.2:

Règle des signes de Descartes. Lorsque les termes d’un polynôme sont ordonné en ordre décroissant de degré, alors le nombre de racines positives est soit égal au nombre de changement de signe entre les termes non nul consécutif, ou bien moins par un multiple de 2\displaystyle 2. Les racines multiples sont compté séparément.

Le nombre de racine négative d’un polynôme p⁢(x)\displaystyle p(x) est obtenu en appliquant la même règle que précedement au polynôme p⁢(−x)\displaystyle p(-x).

Nous allons maintenant illustrer ces théorèmes à l’aide de quelques exemples, en commençant par un exemple à l’aide d’un polynôme du second degré pour lequel nous savons déjà trouver les racines à l’aide de la formule quadratique.

Exemple 7.2.4.

On veut utiliser le théorème des racines rationnelles pour trouver les racines du polynôme p⁢(x)=3⁢x2−22⁢x+7\displaystyle p(x)=3x^{2}-22x+7. Comme 3\displaystyle 3 et 7\displaystyle 7 sont des nombres premiers, on obtient que les seules possibilités pour des racines rationnelles sont:

{±1,±7,±13,±73}\displaystyle\left\{\pm 1,\pm 7,\pm\frac{1}{3},\pm\frac{7}{3}\right\}

Maintenant, comme il n’y a deux changements de signes, la règle des signes de Descartes nous affirme qu’il y a 0\displaystyle 0 ou 2\displaystyle 2 racines positives. En applicant le corollaire, nous avons p⁢(−x)=3⁢x2+22⁢x+7\displaystyle p(-x)=3x^{2}+22x+7, ce qui signifie qu’il n’y a aucune racine négative. Nous avons donc seulement 4\displaystyle 4 candidats à tester. En testant les possibilités une par une, on a donc:

x\displaystyle x 1/3\displaystyle\nicefrac{{1}}{{3}} 1\displaystyle 1 7/3\displaystyle\nicefrac{{7}}{{3}} 7\displaystyle 7
p⁢(x)\displaystyle p(x) 0\displaystyle 0 −12\displaystyle-12 −28\displaystyle-28 0\displaystyle 0

On obtient donc que les racines du polynôme sont 7\displaystyle 7 et 1/3\displaystyle\nicefrac{{1}}{{3}}. Remarquez que par le théorème fondamental de l’algèbre, nous savons qu’il ne peut pas y avoir d’autre racine. De plus, après avoir trouvé que 1/3\displaystyle\nicefrac{{1}}{{3}} est une racine, nous aurions donc pu arrêter notre recherche et faire la division euclidienne pour trouver l’autre racine:

\polylongdiv⁢3⁢x2−22⁢x+73⁢x−1\displaystyle\polylongdiv{3x^{2}-22x+7}{3x-1}

Ce qui nous donne x−7=0\displaystyle x-7=0 et donc x=7\displaystyle x=7 est l’autre racine.

Bien sur, l’intérêt du théorème des racines rationnelles n’est pas de trouver les racines d’un polynôme du second degré, mais bien de trouver les racines de polynôme de degré plus élevé. La technique reste cependant la même.

Exemple 7.2.5.

Nous voulons factoriser le polynôme p⁢(x)=x3−23⁢x2+170⁢x−400\displaystyle p(x)=x^{3}-23x^{2}+170x-400. Par le théorème des racines rationnelles, nous savons que toutes les racines rationnelles de p⁢(x)\displaystyle p(x) doivent être un diviseur entier (positif ou négatif) de 400\displaystyle 400. Par la règle des signes de Descartes, nous savons qu’il y a 1\displaystyle 1 ou 3\displaystyle 3 racines positives. Comme p⁢(−x)=−x3−23⁢x2−170⁢x−400\displaystyle p(-x)=-x^{3}-23x^{2}-170x-400, nous savons par le corollaire qu’il n’y a aucune racine négative. De plus, comme 400=24⋅52\displaystyle 400=2^{4}\cdot 5^{2}, nous savons que 400\displaystyle 400 possède 5⋅3=15\displaystyle 5\cdot 3=15 diviseurs, ce qui signifie qu’il nous faut tester au plus 15\displaystyle 15 possibilités pour trouver toutes les racines rationnelles du polynôme. On doit donc compléter le tableau ci-dessous:

x\displaystyle x 1\displaystyle 1 2\displaystyle 2 4\displaystyle 4 5\displaystyle 5 8\displaystyle 8 10\displaystyle 10 16\displaystyle 16 20\displaystyle 20 25\displaystyle 25 40\displaystyle 40 50\displaystyle 50 80\displaystyle 80 100\displaystyle 100 200\displaystyle 200 400\displaystyle 400
p⁢(x)\displaystyle p(x) −252\displaystyle-252 −144\displaystyle-144 −24\displaystyle-24 0\displaystyle 0

Remarquez que nous avons arrêter de compléter notre tableau du moment que nous avons trouvé que 5\displaystyle 5 est une racine, et nous allons effectuer la division euclidienne pour trouver les autres racines.

\polylongdiv

x^3-23x^2+170x-400x-5

On obtient donc x3−23⁢x2+170⁢x−400=(x−5)⁢(x2−18⁢x+80)=(x−5)⁢(x−8)⁢(x−10)\displaystyle x^{3}-23x^{2}+170x-400=(x-5)(x^{2}-18x+80)=(x-5)(x-8)(x-10).

Décomposition en fractions partielles

La décomposition en fractions partielles est une technique permettant une fonction rationnelle sous la forme d’une somme de fonctions rationnelles plus simple, et donc plus facilement utilisable dans le contexte des fonctions génératrices. La décomposition en fractions partielles se fait en plusieurs étapes:

  1. 1.
    ​

    On commence par réécrire notre fonction rationnelle f⁢(x)=p⁢(x)q⁢(x)\displaystyle f(x)=\frac{p(x)}{q(x)} sous la forme f⁢(x)=s⁢(x)+r⁢(x)q⁢(z)\displaystyle f(x)=s(x)+\frac{r(x)}{q(z)} avec deg⁡(r⁢(x))<deg⁡(q⁢(x))\displaystyle\deg(r(x))<\deg(q(x)). Ceci peut être accompli à l’aide de la division euclidienne des polynômes.

  2. 2.
    ​

    On factorise le dénominateur q⁢(x)\displaystyle q(x) sous la forme q1α1⁢(x)⁢q2α2⁢(x)⁢q3α3⁢(x)⁢…⁢qkαk⁢(x)\displaystyle q_{1}^{\alpha_{1}}(x)q_{2}^{\alpha_{2}}(x)q_{3}^{\alpha_{3}}(x).% ..q_{k}^{\alpha_{k}}(x) avec chacun des qiαi⁢(x)\displaystyle q_{i}^{\alpha_{i}}(x) un polynôme de degré 1 ou 2 irréductible différent. Ceci est possible grâce au théorème fondamental de l’algèbre. Remarquez que le théorème fondamental de l’algèbre est uniquement un théorème d’existence, et ne nous donne aucune information sur la façon de factoriser notre polynôme. La formule quadratique, le théorème des racines rationnelles et la règle des signes de Descartes peuvent s’avérer particulièrement utile pour la factorisation.

  3. 3.
    ​

    Une fois les deux étapes précédentes complété, chaque facteur de la forme (a⁢x+b)n\displaystyle(ax+b)^{n} au dénominateur peut être décomposé sous la forme

    A1a⁢x+b+A2(a⁢x+b)2+A3(a⁢x+b)3+…+An(a⁢x+b)n\displaystyle\frac{A_{1}}{ax+b}+\frac{A_{2}}{(ax+b)^{2}}+\frac{A_{3}}{(ax+b)^{% 3}}+...+\frac{A_{n}}{(ax+b)^{n}}

    de plus, chaque facteur irréductible de la forme (a⁢x2+b⁢x+c)n\displaystyle(ax^{2}+bx+c)^{n} au dénominateur peut être décomposé sous la forme

    A1⁢x+B1a⁢x2+b⁢x+c+A2⁢x+B2(a⁢x2+b⁢x+c)2+A3⁢x+B3(a⁢x2+b⁢x+c)3+…+An⁢x+Bn(a⁢x2+b⁢x+c)n\displaystyle\frac{A_{1}x+B_{1}}{ax^{2}+bx+c}+\frac{A_{2}x+B_{2}}{(ax^{2}+bx+c% )^{2}}+\frac{A_{3}x+B_{3}}{(ax^{2}+bx+c)^{3}}+...+\frac{A_{n}x+B_{n}}{(ax^{2}+% bx+c)^{n}}

    Il faut ensuite résoudre le système d’équations linéaires pour obtenir la valeur des constantes.

Exemple 7.2.6.

On veut décomposer la fonction rationnelle suivante sous forme de fractions partielles:

5⁢x2−94⁢x+390x3−23∗x2+170∗x−400\displaystyle\frac{5x^{2}-94x+390}{x^{3}-23*x^{2}+170*x-400}

Pour ce faire, remarquons premièrement que x3−23⁢x2+170⁢x−400=(x−5)⁢(x−8)⁢(x−10)\displaystyle x^{3}-23x^{2}+170x-400=(x-5)(x-8)(x-10). On doit donc trouver des constantes A\displaystyle A, B\displaystyle B et C\displaystyle C telle que:

5⁢x2−94⁢x+390x3−23⁢x2+170⁢x−400\displaystyle\displaystyle\frac{5x^{2}-94x+390}{x^{3}-23x^{2}+170x-400} =\displaystyle\displaystyle= Ax−5+Bx−8+Cx−10\displaystyle\displaystyle\frac{A}{x-5}+\frac{B}{x-8}+\frac{C}{x-10}
=\displaystyle\displaystyle= A⁢(x−8)⁢(x−10)+B⁢(x−5)⁢(x−10)+C⁢(x−5)⁢(x−8)x3−23⁢x2+170⁢x−400\displaystyle\displaystyle\frac{A(x-8)(x-10)+B(x-5)(x-10)+C(x-5)(x-8)}{x^{3}-2% 3x^{2}+170x-400}
=\displaystyle\displaystyle= (A+B+C)⁢x2+(−18⁢A−15⁢B−13⁢C)⁢x+(80⁢A+50⁢B+40⁢C)x3−23⁢x2+170⁢x−400\displaystyle\displaystyle\frac{(A+B+C)x^{2}+(-18A-15B-13C)x+(80A+50B+40C)}{x^% {3}-23x^{2}+170x-400}

On doit donc résoudre le système d’équations linéaires suivants:

{A+B+C=5−18⁢A−15⁢B−13⁢C=−9480⁢A+50⁢B+40⁢C=390\displaystyle\left\{\begin{array}[]{l}A+B+C=5\\ -18A-15B-13C=-94\\ 80A+50B+40C=390\end{array}\right.

En applicant la méthode de Gauss, nous obtenons donc:

(1115−18−15−13−94805040390)∼80⁢L1−L3→L318⁢L1+L2→L2(1115035−40304010)∼10⁢L2−L3→L3(1115035−40010−50)\displaystyle\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&1&1&5\\ -18&-15&-13&-94\\ 80&50&40&390\end{array}\right)\sim^{18L_{1}+L_{2}\rightarrow L_{2}}_{80L_{1}-L% _{3}\rightarrow L_{3}}\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&1&1&5\\ 0&3&5&-4\\ 0&30&40&10\end{array}\right)\sim^{10L_{2}-L_{3}\rightarrow L_{3}}\left(\begin{% array}[]{@{}*{3}{c}|c@{}}1&1&1&5\\ 0&3&5&-4\\ 0&0&10&-50\end{array}\right)

On a donc 10⁢C=−50\displaystyle 10C=-50, ce qui nous donne C=−5\displaystyle C=-5. En remplaçant dans la seconde ligne, on a donc 3⁢B+5⁢(−5)=−4\displaystyle 3B+5(-5)=-4, ce qui nous donne 3⁢B=21\displaystyle 3B=21 et donc B=7\displaystyle B=7. Finalement, en remplaçant dans la première équation on a A+7−5=5\displaystyle A+7-5=5, ce qui nous donne A=3\displaystyle A=3. La décomposition en fractions partielles est donc:

5⁢x2−94⁢x+390x3−23⁢x2+170⁢x−400=3x−5+7x−8+−5x−10\displaystyle\frac{5x^{2}-94x+390}{x^{3}-23x^{2}+170x-400}=\frac{3}{x-5}+\frac% {7}{x-8}+\frac{-5}{x-10}
Exemple 7.2.7.

Décomposer en fractions partielles la fonction rationnelle suivante:

−9⁢x2+13⁢x−114x3−6⁢x2+4⁢x−24\displaystyle\frac{-9x^{2}+13x-114}{x^{3}-6x^{2}+4x-24}

Pour ce faire, nous devons premièrement factoriser le dénominateur p⁢(x)=x3−6⁢x2+4⁢x−24\displaystyle p(x)=x^{3}-6x^{2}+4x-24. Comme il s’agit d’un polynôme de degré 3\displaystyle 3, il doit posséder au minimum 1\displaystyle 1 racines réelles par le théorème fondamental de l’algèbre, ce qui signifie qu’il est réductible. De plus, le théorème des racines rationnelles nous affirme que toutes les racines rationnelles de p⁢(x)\displaystyle p(x) doivent être un diviseur entier de 24\displaystyle 24 (positif ou négatif). On obtient donc les possibilités suivantes:

{±1,±2,±3,±4,±6,±8,±12,±24}\displaystyle\left\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 8,\pm 12,\pm 24\right\}

De plus, comme p⁢(−x)=−x3−6⁢x2−4⁢x−24\displaystyle p(-x)=-x^{3}-6x^{2}-4x-24, nous savons par le corollaire de la règle des signes de Descartes que le polynôme p⁢(x)\displaystyle p(x) ne possède aucune racine négative. Nous somme donc ramené à tester un maximum de 8\displaystyle 8 possibilités.

x\displaystyle x 1\displaystyle 1 2\displaystyle 2 3\displaystyle 3 4\displaystyle 4 6\displaystyle 6 8\displaystyle 8 12\displaystyle 12 24\displaystyle 24
p⁢(x)\displaystyle p(x) −25\displaystyle-25 −32\displaystyle-32 −39\displaystyle-39 −40\displaystyle-40 0\displaystyle 0

On remarque donc que 6\displaystyle 6 est une racine du polynôme. Nous allons donc effectuer la division euclidienne:

\polylongdiv

x^3-6x^2+4x-24x-6

Il nous reste donc à factoriser le polynôme x2+4\displaystyle x^{2}+4. Il est facile de voir que ce polynôme est en fait irréductible dans les nombres réels, et donc la factorisation de p⁢(x)\displaystyle p(x) est:

x3−6⁢x2+4⁢x−24=(x−6)⁢(x2+4)\displaystyle x^{3}-6x^{2}+4x-24=(x-6)(x^{2}+4)

La décomposition en fractions partielles doit donc avoir la forme suivante:

−9⁢x2+13⁢x−114x3−6⁢x2+4⁢x−24=Ax−6+B⁢x+Cx2+4=A⁢(x2+4)+(B⁢x+C)⁢(x−6)x3−6⁢x2+4⁢x−24=(A+B)⁢x2+(−6⁢B+C)⁢x+(4⁢A−6⁢C)x3−6⁢x2+4⁢x−24\displaystyle\frac{-9x^{2}+13x-114}{x^{3}-6x^{2}+4x-24}=\frac{A}{x-6}+\frac{Bx% +C}{x^{2}+4}=\frac{A(x^{2}+4)+(Bx+C)(x-6)}{x^{3}-6x^{2}+4x-24}=\frac{(A+B)x^{2% }+(-6B+C)x+(4A-6C)}{x^{3}-6x^{2}+4x-24}

Ce qui nous donne le système d’équations linéaires suivants:

{A+B=−9−6⁢B+C=134⁢A−6⁢C=−114\displaystyle\left\{\begin{array}[]{l}A+B=-9\\ -6B+C=13\\ 4A-6C=-114\end{array}\right.

que l’on peut résoudre avec par exemple la méthode de Gauss. On obtient donc:

(110−90−611340−6−114)∼4⁢L1−L3→L3(110−90−611304678)∼2⁢L2+3⁢L3→L3(110−90−61130020260)\displaystyle\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&1&0&-9\\ 0&-6&1&13\\ 4&0&-6&-114\end{array}\right)\sim^{4L_{1}-L_{3}\rightarrow L_{3}}\left(\begin{% array}[]{@{}*{3}{c}|c@{}}1&1&0&-9\\ 0&-6&1&13\\ 0&4&6&78\end{array}\right)\sim^{2L_{2}+3L_{3}\rightarrow L_{3}}\left(\begin{% array}[]{@{}*{3}{c}|c@{}}1&1&0&-9\\ 0&-6&1&13\\ 0&0&20&260\end{array}\right)

Ce qui nous donne 20⁢C=260\displaystyle 20C=260, c’est à dire C=13\displaystyle C=13, en remplaçant dans la seconde équation on a ensuite −6⁢B+13=13\displaystyle-6B+13=13, ce qui signifie que B=0\displaystyle B=0, puis finalement en remplaçant dans la première équation on obtient A+0=−9\displaystyle A+0=-9, ce qui nous donne A=−9\displaystyle A=-9. La décomposition en fractions partielles est donc:

−9⁢x2+13⁢x−114x3−6⁢x2+4⁢x−24=−9x−6+13x2+4\displaystyle\frac{-9x^{2}+13x-114}{x^{3}-6x^{2}+4x-24}=\frac{-9}{x-6}+\frac{1% 3}{x^{2}+4}
Exemple 7.2.8.

On veut décomposer en fractions partielles la fonction rationnelle suivante:

−x2−2⁢x+18x3−15⁢x2+72⁢x−112\displaystyle\frac{-x^{2}-2x+18}{x^{3}-15x^{2}+72x-112}

En utilisant le théorème des racines rationnelles, on obtient la factorisation suivante pour le dénominateur: x3−15⁢x2+72⁢x−112=(x−4)2⁢(x−7)\displaystyle x^{3}-15x^{2}+72x-112=(x-4)^{2}(x-7), ce qui signifie que la décomposition en fractions partielles aura la forme suivante:

−x2−2⁢x+18x3−15⁢x2+72⁢x−112\displaystyle\displaystyle\frac{-x^{2}-2x+18}{x^{3}-15x^{2}+72x-112} =\displaystyle\displaystyle= Ax−4+B(x−4)2+Cx−7=A⁢(x−4)⁢(x−7)+B⁢(x−7)+C⁢(x−4)⁢(x−4)x3−15⁢x2+72⁢x−112\displaystyle\displaystyle\frac{A}{x-4}+\frac{B}{(x-4)^{2}}+\frac{C}{x-7}=% \frac{A(x-4)(x-7)+B(x-7)+C(x-4)(x-4)}{x^{3}-15x^{2}+72x-112}
=\displaystyle\displaystyle= (A+C)⁢x2+(−11⁢A+B−8⁢C)⁢x+(28⁢A−7⁢B+16⁢C)x3−15⁢x2+72⁢x−112\displaystyle\displaystyle\frac{(A+C)x^{2}+(-11A+B-8C)x+(28A-7B+16C)}{x^{3}-15% x^{2}+72x-112}

Ce qui nous donne le système d’équations linéaires suivants:

{A+C=−1−11⁢A+B−8⁢C=−228⁢A−7⁢B+16⁢C=18\displaystyle\left\{\begin{array}[]{l}A+C=-1\\ -11A+B-8C=-2\\ 28A-7B+16C=18\end{array}\right.

En résolvant ce système, on obtient donc: A=4,B=2\displaystyle A=4,B=2 et C=−5\displaystyle C=-5. La décomposition en fractions partielles est donc:

−x2−2⁢x+18x3−15⁢x2+72⁢x−112=4x−4+2(x−4)2+5x−7\displaystyle\frac{-x^{2}-2x+18}{x^{3}-15x^{2}+72x-112}=\frac{4}{x-4}+\frac{2}% {(x-4)^{2}}+\frac{5}{x-7}

Le théorème du binôme

Nous avons déjà eu l’occasion de rencontrer le théorème du binôme, mais nous ne l’avons toujours pas écrit formellement dans ces notes. Nous allons maintenant remédier à ce problème, et montrer quelques unes de ses applications en lien avec les fonctions génératrices.

Théorème 7.2.3:

Théorème du binome. Si a,b∈ℝ\displaystyle a,b\in\mathbb{R} et n∈ℕ\displaystyle n\in\mathbb{N}, alors:

(a+b)n=∑k=0n(nk)⁢ak⁢bn−k\displaystyle(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}
Démonstration.

Par définition, nous savons que:

(a+b)n=(a+b)⁢(a+b)⁢(a+b)⁢…⁢(a+b)⏟n⁢ fois\displaystyle(a+b)^{n}=\underbrace{(a+b)(a+b)(a+b)...(a+b)}_{n\textrm{% \leavevmode\nobreak\ fois}}

Il est facile de voir qu’une fois développer, chaque terme aura la forme Ck⁢ak⁢bn−k\displaystyle C_{k}a^{k}b^{n-k} avec Ck\displaystyle C_{k} une constante. Ceci est dû au fait que chaque terme sera formé du produit d’exactement n\displaystyle n facteurs, qui peuvent être soit des a\displaystyle a ou des b\displaystyle b. Pour trouver le coefficient Ck\displaystyle C_{k}, il s’agit de remarquer qu’il correspond au nombre de façon de choisir k\displaystyle k fois un a\displaystyle a parmi une possibilité de n\displaystyle n. Ceci nous est donné par le coefficient binomial (nk)\displaystyle\binom{n}{k}. On obtient donc:

(a+b)n=∑k=0n(nk)⁢ak⁢bn−k\displaystyle(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}

∎

Le cas particulier où a=x\displaystyle a=x et b=1\displaystyle b=1 est particulièrement intéressant, et comme nous l’avons déjà vu correspondant à la fonction génératrice du coefficient binomial. Nous avons donc

(x+1)n=∑k=0n(nk)⁢xk=∑k=0∞(nk)⁢xk\displaystyle(x+1)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}=\sum_{k=0}^{\infty}% \binom{n}{k}x^{k}

Remarquez qu’il nous est possible de remplacer le n\displaystyle n dans la somme par l’infinie, car le coefficient binomial (nk)\displaystyle\binom{n}{k} vaut 0\displaystyle 0 si k>n\displaystyle k>n. Cette forme du théorème du binôme est particulièrement intéressante, car la présence d’une seule variable x\displaystyle x nous permet d’utiliser les outils du calcul différentiel et intégral. C’est ce que Newton a fait, ce qui nous permet d’obtenir le théorème suivant:

Théorème 7.2.4:

Théorème du binôme généralisé de Newton. Si r\displaystyle r est un nombre réel, alors nous avons l’égalité suivante:

(x+1)r=∑k=0∞(rk)⁢xk,∀x,|x|<1\displaystyle(x+1)^{r}=\sum_{k=0}^{\infty}\binom{r}{k}x^{k},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \forall x,|x|<1

La démonstration de cette version du théorème ne sera pas faites ici, mais repose sur le calcul différentiel et intégral. Remarquez que dans cette version du théorème du binôme fonction pour n’importe quel exposant réel, contrairement à notre version original. Par contre, il devient nécessaire de limiter les valeurs de x\displaystyle x à des valeurs entre −1\displaystyle-1 et 1\displaystyle 1. Ceci n’aura cependant pas d’importance dans notre travail, car nous allons travailler avec des séries formelles et non des séries numériques.

Exemple 7.2.9.

On veut utiliser le théorème du binôme pour approximer la valeur de 2\displaystyle\sqrt{2}. Pour ce faire, nous avons:

2\displaystyle\displaystyle\sqrt{2} =\displaystyle\displaystyle= (1+1)1/2=∑k=0∞(1/2k)1k==∑k=0∞(1/2k)=∑k=0∞(1/2)k¯k!\displaystyle\displaystyle(1+1)^{\nicefrac{{1}}{{2}}}=\sum_{k=0}^{\infty}% \binom{\nicefrac{{1}}{{2}}}{k}1^{k}==\sum_{k=0}^{\infty}\binom{\nicefrac{{1}}{% {2}}}{k}=\sum_{k=0}^{\infty}\frac{(\nicefrac{{1}}{{2}})^{\underline{k}}}{k!}
=\displaystyle\displaystyle= (1/2)0¯0!+(1/2)1¯1!+(1/2)2¯2!+(1/2)3¯3!+(1/2)4¯4!+…\displaystyle\displaystyle\frac{(\nicefrac{{1}}{{2}})^{\underline{0}}}{0!}+% \frac{(\nicefrac{{1}}{{2}})^{\underline{1}}}{1!}+\frac{(\nicefrac{{1}}{{2}})^{% \underline{2}}}{2!}+\frac{(\nicefrac{{1}}{{2}})^{\underline{3}}}{3!}+\frac{(% \nicefrac{{1}}{{2}})^{\underline{4}}}{4!}+...
=\displaystyle\displaystyle= 10!+1/21!+(1/2)⁢(−1/2)2!+(1/2)⁢(−1/2)⁢(−3/2)3!+(1/2)⁢(−1/2)⁢(−3/2)⁢(−5/2)4!+…\displaystyle\displaystyle\frac{1}{0!}+\frac{\nicefrac{{1}}{{2}}}{1!}+\frac{(% \nicefrac{{1}}{{2}})(\nicefrac{{-1}}{{2}})}{2!}+\frac{(\nicefrac{{1}}{{2}})(% \nicefrac{{-1}}{{2}})(\nicefrac{{-3}}{{2}})}{3!}+\frac{(\nicefrac{{1}}{{2}})(% \nicefrac{{-1}}{{2}})(\nicefrac{{-3}}{{2}})(\nicefrac{{-5}}{{2}})}{4!}+...
≈\displaystyle\displaystyle\approx 1+0,5−0,125+0,0625−0,0390625=1,3984375\displaystyle\displaystyle 1+0,5-0,125+0,0625-0,0390625=1,3984375

La véritable valeur de 2\displaystyle\sqrt{2} est en fait approximativement 1,4142\displaystyle 1,4142, ce qui signifie que notre approximation est en loin d’être parfaite. En considérant plus de terme, il nous est cependant possible d’obtenir une bien meilleure approximation.

Dans notre cas, ce n’est pas vraiment les approximations qui rend le théorème du binôme intéressant, mais plutôt son lien avec les fonctions génératrices. Nous allons donc considérez quelques cas particulier.

Exemple 7.2.10.

Si on prend r=−1\displaystyle r=-1 dans le théorème du binôme, on obtient:

1x+1=∑k=0∞(−1k)⁢xk=∑k=0∞(−1)k¯k!⁢xk=∑k=0∞(−1)⁢(−2)⁢(−3)⁢(−4)⁢…⁢(−k)k!⁢xk=∑k=0∞(−1)k⁢k!k!⁢xk=∑k=0∞(−1)k⁢xk\displaystyle\frac{1}{x+1}=\sum_{k=0}^{\infty}\binom{-1}{k}x^{k}=\sum_{k=0}^{% \infty}\frac{(-1)^{\underline{k}}}{k!}x^{k}=\sum_{k=0}^{\infty}\frac{(-1)(-2)(% -3)(-4)...(-k)}{k!}x^{k}=\sum_{k=0}^{\infty}\frac{(-1)^{k}k!}{k!}x^{k}=\sum_{k% =0}^{\infty}(-1)^{k}x^{k}

En particulier, si on remplace x\displaystyle x par −x\displaystyle-x dans notre égalité, on obtient:

1−x+1=∑k=0∞(−1)k⁢(−x)k=∑k=0∞(−1)k⁢(−1)k⁢xk=∑k=0∞xk⇒11−x=∑k=0∞xk\displaystyle\frac{1}{-x+1}=\sum_{k=0}^{\infty}(-1)^{k}(-x)^{k}=\sum_{k=0}^{% \infty}(-1)^{k}(-1)^{k}x^{k}=\sum_{k=0}^{\infty}x^{k}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \frac{1}{1-x}=\sum_{k=0}^{\infty}x^{k}

qui n’est en fait rien d’autre que notre série géométrique.

Exemple 7.2.11.

Si on remplace r\displaystyle r par −n\displaystyle-n avec n\displaystyle n entier, et on remplace x\displaystyle x par −x\displaystyle-x, on obtient:

1(1−x)n\displaystyle\displaystyle\frac{1}{(1-x)^{n}} =\displaystyle\displaystyle= ∑k=0∞(−nk)⁢(−x)k=∑k=0∞(−n)k¯k!⁢(−1)k⁢xk=∑k=0∞(−n)⁢(−n−1)⁢(−n−2)⁢(−n−3)⁢…⁢(−n−k+1)k!⁢(−1)k⁢xk\displaystyle\displaystyle\sum_{k=0}^{\infty}\binom{-n}{k}(-x)^{k}=\sum_{k=0}^% {\infty}\frac{(-n)^{\underline{k}}}{k!}(-1)^{k}x^{k}=\sum_{k=0}^{\infty}\frac{% (-n)(-n-1)(-n-2)(-n-3)...(-n-k+1)}{k!}(-1)^{k}x^{k}
=\displaystyle\displaystyle= ∑k=0∞(−1)k⁢(n)⁢(n+1)⁢(n+2)⁢(n+3)⁢(n+4)⁢…⁢(n+k−1)k!⁢(−1)k⁢xk=∑k=0∞nk¯k!⁢xk=∑k=0∞⟨nk⟩⁢xk\displaystyle\displaystyle\sum_{k=0}^{\infty}\frac{(-1)^{k}(n)(n+1)(n+2)(n+3)(% n+4)...(n+k-1)}{k!}(-1)^{k}x^{k}=\sum_{k=0}^{\infty}\frac{n^{\overline{k}}}{k!% }x^{k}=\sum_{k=0}^{\infty}\left\langle n\atop k\right\rangle x^{k}
Exemple 7.2.12.

En reprenant la série géométrique de l’exemple 7.2.10 et en remplaçant le x\displaystyle x par xn\displaystyle x^{n} on obtient:

11−xn=∑k=0∞(xm)k=∑k=0∞xk⁢m\displaystyle\frac{1}{1-x^{n}}=\sum_{k=0}^{\infty}(x^{m})^{k}=\sum_{k=0}^{% \infty}x^{km}

La multiplication des séries

Dans la résolution des suites définies par récurrence, il est fréquent de devoir multiplier deux séries. Comme dernier outils avant d’entreprendre la résolution des récurrences, nous allons donc regarder comment ceci peut être accompli.

Théorème 7.2.5:

Multiplication des séries. Si ∑n=0∞an⁢xn\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} et ∑n=0∞bn⁢xn\displaystyle\sum_{n=0}^{\infty}b_{n}x^{n} sont des séries, alors leur produit est donné par la formule suivante:

(∑n=0∞an⁢xn)⁢(∑n=0∞bn⁢xn)=∑n=0∞(∑k=0nak⁢bn−k)⁢xn\displaystyle\left(\sum_{n=0}^{\infty}a_{n}x^{n}\right)\left(\sum_{n=0}^{% \infty}b_{n}x^{n}\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_{k}b_{n-k}% \right)x^{n}
Démonstration.

L’idée est tout simplement de remarquer que pour obtenir un xn\displaystyle x^{n}, il nous faut le produit d’une constante par un terme xn\displaystyle x^{n}, ou un terme de la forme x1\displaystyle x^{1} avec un terme de la forme xn−1\displaystyle x^{n-1}, ou un terme de la forme x2\displaystyle x^{2} avec un terme de la forme xn−2\displaystyle x^{n-2}, et ainsi de suite. En faisant la somme de tout ces termes, on peut alors obtenir le coefficient de xn\displaystyle x^{n}, et on fait ainsi de suite pour toute les valeurs de n\displaystyle n. ∎

Exemple 7.2.13.

On veut vérifier le théorème en calculant le produit e2⁢x⁢e3⁢x\displaystyle e^{2x}e^{3x} à l’aide des séries.

e2⁢x⁢e5⁢x\displaystyle\displaystyle e^{2x}e^{5x} =\displaystyle\displaystyle= (∑n=0∞2n⁢xnn!)⁢(∑n=0∞3n⁢xnn!)=∑n=0∞(∑k=0n2kk!⁢3n−k(n−k)!)⁢xn=∑n=0∞1n!⁢(∑k=0n(nk)⁢2k⁢3n−k)⁢xn\displaystyle\displaystyle\left(\sum_{n=0}^{\infty}\frac{2^{n}x^{n}}{n!}\right% )\left(\sum_{n=0}^{\infty}\frac{3^{n}x^{n}}{n!}\right)=\sum_{n=0}^{\infty}% \left(\sum_{k=0}^{n}\frac{2^{k}}{k!}\frac{3^{n-k}}{(n-k)!}\right)x^{n}=\sum_{n% =0}^{\infty}\frac{1}{n!}\left(\sum_{k=0}^{n}\binom{n}{k}2^{k}3^{n-k}\right)x^{n}
=\displaystyle\displaystyle= ∑n=0∞(2+3)n⁢xnn!=∑n=0∞5n⁢xnn!=e5⁢x\displaystyle\displaystyle\sum_{n=0}^{\infty}\frac{(2+3)^{n}x^{n}}{n!}=\sum_{n% =0}^{\infty}\frac{5^{n}x^{n}}{n!}=e^{5x}