Récurrence et coefficients binomiaux en L1 de maths : cours et méthodes

Propriété du bon ordre. Toute partie non vide de \(\mathbb{N}\) possède un plus petit élément. Toute partie non vide et majorée de \(\mathbb{N}\) possède un plus grand élément.

Considérons l’ensemble \(A=\left\{\frac{1}{n} : n\in\mathbb{N}^{*}\right\}\). Il est non vide et minoré par \(0\). Pourtant, aucun de ses éléments n’est le plus petit, car \(\frac{1}{n+1}<\frac{1}{n}\). Le bon ordre est donc une propriété propre aux entiers, et non à toute partie minorée de \(\mathbb{R}\).

Soit \(n_0\in\mathbb{N}\). On suppose que \(\mathcal{P}(n_0)\) est vraie et que, pour tout \(n\geq n_0\), \(\mathcal{P}(n)\) implique \(\mathcal{P}(n+1)\). Alors \(\mathcal{P}(n)\) est vraie pour tout entier \(n\geq n_0\).

Raisonnons par l’absurde. Supposons que l’ensemble \(F\) des entiers \(n\geq n_0\) pour lesquels \(\mathcal{P}(n)\) est fausse soit non vide. Par le bon ordre, \(F\) admet un plus petit élément \(m\). D’abord, \(m\neq n_0\) puisque \(\mathcal{P}(n_0)\) est vraie. Ainsi \(m-1\geq n_0\), et \(m-1\notin F\) par minimalité de \(m\). Autrement dit, \(\mathcal{P}(m-1)\) est vraie. L’hérédité donne alors \(\mathcal{P}(m)\), ce qui contredit \(m\in F\). Par conséquent \(F\) est vide.

1. Énoncer clairement la propriété \(\mathcal{P}(n)\) et le rang de départ \(n_0\).
2. Initialisation : vérifier \(\mathcal{P}(n_0)\) par un calcul explicite.
3. Hérédité : fixer un entier \(n\geq n_0\), supposer \(\mathcal{P}(n)\) et en déduire \(\mathcal{P}(n+1)\).
4. Conclure en citant le principe de récurrence.

Montrons que, pour tout \(n\in\mathbb{N}\), l’entier \(11^{n}-4^{n}\) est divisible par \(7\). Notons \(\mathcal{P}(n)\) cette propriété.

Pour \(n=0\), on obtient \(1-1=0\), qui est divisible par \(7\). Fixons ensuite \(n\in\mathbb{N}\) et supposons \(11^{n}-4^{n}=7q\) avec \(q\in\mathbb{Z}\). Alors

\[11^{n+1}-4^{n+1}=11\left(11^{n}-4^{n}\right)+11\cdot 4^{n}-4\cdot 4^{n}=77q+7\cdot 4^{n}.\]

Le membre de droite vaut \(7\left(11q+4^{n}\right)\). Ainsi \(\mathcal{P}(n+1)\) est vraie. Par récurrence, la propriété est établie pour tout \(n\).

Le rang de départ n’est pas toujours \(0\). Montrons que \(2^{n}\geq n^{2}\) pour tout entier \(n\geq 4\). D’abord, pour \(n=4\), on a \(16\geq 16\). Notons que la propriété est fausse pour \(n=3\), puisque \(8<9\) : le choix \(n_0=4\) est donc imposé.

Ensuite, fixons \(n\geq 4\) et supposons \(2^{n}\geq n^{2}\). Alors \(2^{n+1}\geq 2n^{2}\). Il reste à comparer \(2n^{2}\) et \((n+1)^{2}\). Leur différence vaut \(n^{2}-2n-1=(n-1)^{2}-2\), qui est positive dès que \(n\geq 3\). Ainsi \(2^{n+1}\geq(n+1)^{2}\), et la récurrence est établie à partir du rang \(4\).

Si \(\mathcal{P}(n_0)\) et \(\mathcal{P}(n_0+1)\) sont vraies, et si pour tout \(n\geq n_0\) la conjonction de \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) implique \(\mathcal{P}(n+2)\), alors \(\mathcal{P}(n)\) est vraie pour tout \(n\geq n_0\).

Soit \((u_n)\) définie par \(u_0=2\), \(u_1=5\) et \(u_{n+2}=5u_{n+1}-6u_n\). Montrons que \(u_n=2^{n}+3^{n}\) pour tout \(n\).

D’abord, \(2^{0}+3^{0}=2=u_0\) et \(2+3=5=u_1\) : les deux premiers rangs sont vérifiés. Ensuite, supposons la formule vraie aux rangs \(n\) et \(n+1\). On calcule

\[u_{n+2}=5\left(2^{n+1}+3^{n+1}\right)-6\left(2^{n}+3^{n}\right)=2^{n}(10-6)+3^{n}(15-6).\]

On trouve \(4\cdot 2^{n}+9\cdot 3^{n}=2^{n+2}+3^{n+2}\). Par récurrence double, la formule est vraie pour tout \(n\in\mathbb{N}\).

Supposons \(\mathcal{P}(n_0)\) vraie et, pour tout \(n\geq n_0\), que la validité de \(\mathcal{P}(n_0),\mathcal{P}(n_0+1),\dots,\mathcal{P}(n)\) entraîne celle de \(\mathcal{P}(n+1)\). Alors \(\mathcal{P}(n)\) est vraie pour tout \(n\geq n_0\).

On applique la récurrence simple à \(\mathcal{R}(n)\) : « pour tout \(k\) entre \(n_0\) et \(n\), \(\mathcal{P}(k)\) est vraie ». D’abord, \(\mathcal{R}(n_0)\) coïncide avec \(\mathcal{P}(n_0)\). Ensuite, si \(\mathcal{R}(n)\) est vraie, l’hypothèse fournit \(\mathcal{P}(n+1)\), donc \(\mathcal{R}(n+1)\). Ainsi \(\mathcal{R}(n)\) est vraie pour tout \(n\geq n_0\), et a fortiori \(\mathcal{P}(n)\).

1. Écrire l’hypothèse sous la forme : « supposons \(\mathcal{P}(k)\) vraie pour tout \(k\) tel que \(n_0\leq k\leq n\) ».
2. Ramener le rang \(n+1\) à un ou plusieurs rangs plus petits, sans savoir à l’avance lesquels.
3. Vérifier que ces rangs sont bien supérieurs ou égaux à \(n_0\) ; sinon, traiter les petits cas à part dans l’initialisation.

Montrons que tout entier \(n\geq 1\) s’écrit comme une somme de puissances de \(2\) deux à deux distinctes. Pour \(n=1\), on a \(1=2^{0}\).

Soit \(n\geq 1\) et supposons la propriété vraie pour tous les entiers de \(1\) à \(n\). Notons \(2^{p}\) la plus grande puissance de \(2\) inférieure ou égale à \(n+1\). Si \(n+1=2^{p}\), c’est terminé. Sinon, posons \(r=n+1-2^{p}\). Alors \(1\leq r\leq n\), et de plus \(r<2^{p}\) car \(n+1<2^{p+1}\). L’hypothèse de récurrence écrit \(r\) comme somme de puissances distinctes, toutes strictement inférieures à \(2^{p}\). En ajoutant \(2^{p}\), on obtient une écriture de \(n+1\) sans répétition.

C’est l’existence de l’écriture en base \(2\). Le rang utilisé, \(r\), n’est pas \(n\) : une récurrence simple ne suffirait donc pas.

Pour des nombres \(a_p,a_{p+1},\dots,a_q\) avec \(p\leq q\), on note

\[\sum_{k=p}^{q}a_k=a_p+a_{p+1}+\cdots+a_q\quad\text{et}\quad\prod_{k=p}^{q}a_k=a_p\,a_{p+1}\cdots a_q.\]

Si \(q<p\), on convient que la somme vaut \(0\) et que le produit vaut \(1\). La lettre \(k\) est muette : on peut la remplacer par \(i\) ou \(j\) sans rien changer.

Pour tous réels \(\lambda,\mu\) et toutes familles \((a_k)\), \((b_k)\) :

\[\sum_{k=p}^{q}\left(\lambda a_k+\mu b_k\right)=\lambda\sum_{k=p}^{q}a_k+\mu\sum_{k=p}^{q}b_k,\qquad \prod_{k=p}^{q}\left(a_kb_k\right)=\prod_{k=p}^{q}a_k\prod_{k=p}^{q}b_k.\]

De plus, \(\prod_{k=p}^{q}\lambda a_k=\lambda^{q-p+1}\prod_{k=p}^{q}a_k\). Enfin, la relation de Chasles permet de couper une somme : pour \(p\leq r<q\), \(\sum_{k=p}^{q}a_k=\sum_{k=p}^{r}a_k+\sum_{k=r+1}^{q}a_k\).

Translation. Pour tout entier \(r\), en posant \(j=k+r\) :

\[\sum_{k=p}^{q}a_{k+r}=\sum_{j=p+r}^{q+r}a_j.\]

Renversement. En posant \(j=n-k\) :

\[\sum_{k=0}^{n}a_k=\sum_{j=0}^{n}a_{n-j}.\]

Calculons \(S_n=\sum_{k=0}^{n}(3k+2)\) par renversement. En posant \(j=n-k\), on obtient \(S_n=\sum_{j=0}^{n}(3n-3j+2)\). Renommons \(j\) en \(k\), puis additionnons les deux écritures terme à terme :

\[2S_n=\sum_{k=0}^{n}\left[(3k+2)+(3n-3k+2)\right]=\sum_{k=0}^{n}(3n+4)=(n+1)(3n+4).\]

Ainsi \(S_n=\frac{(n+1)(3n+4)}{2}\). On contrôle avec \(n=1\) : \(2+5=7\) et \(\frac{2\cdot 7}{2}=7\).

Pour toute suite \((b_k)\) et tous entiers \(p\leq q\) :

\[\sum_{k=p}^{q}\left(b_{k+1}-b_k\right)=b_{q+1}-b_p.\]

De même, si les \(b_k\) sont non nuls, \(\prod_{k=p}^{q}\frac{b_{k+1}}{b_k}=\frac{b_{q+1}}{b_p}\).

Par linéarité, la somme vaut \(\sum_{k=p}^{q}b_{k+1}-\sum_{k=p}^{q}b_k\). Dans la première, on pose \(j=k+1\) : elle devient \(\sum_{j=p+1}^{q+1}b_j\). Les termes d’indice compris entre \(p+1\) et \(q\) apparaissent dans les deux sommes et s’annulent. Il reste donc \(b_{q+1}-b_p\). Le cas du produit se traite de la même manière.

1. Chercher une suite \((b_k)\) telle que le terme général soit \(b_{k+1}-b_k\), au signe près.
2. Pour une fraction rationnelle, décomposer en éléments simples, puis regrouper les fractions qui se décalent d’un rang.
3. Écrire le résultat, puis le contrôler sur le premier rang.

Calculons \(T_n=\sum_{k=1}^{n}k\cdot k!\). L’idée consiste à écrire \(k=(k+1)-1\). On obtient alors \(k\cdot k!=(k+1)!-k!\). C’est une différence de deux termes consécutifs de la suite \(b_k=k!\). Par conséquent

\[T_n=\sum_{k=1}^{n}\left((k+1)!-k!\right)=(n+1)!-1.\]

Vérification pour \(n=2\) : \(1+4=5\) et \(3!-1=5\).

Calculons \(U_n=\sum_{k=1}^{n}\frac{1}{k(k+1)(k+2)}\). On remarque d’abord que

\[\frac{1}{k(k+1)}-\frac{1}{(k+1)(k+2)}=\frac{(k+2)-k}{k(k+1)(k+2)}=\frac{2}{k(k+1)(k+2)}.\]

Ainsi, avec \(b_k=\frac{1}{k(k+1)}\), le terme général vaut \(\frac{1}{2}\left(b_k-b_{k+1}\right)\). Le télescopage donne alors

\[U_n=\frac{1}{2}\left(\frac{1}{2}-\frac{1}{(n+1)(n+2)}\right).\]

En particulier, \(U_n\) croît et tend vers \(\frac{1}{4}\), comme le montre la figure.

Le télescopage fonctionne aussi pour les produits. Calculons \(W_n=\prod_{k=1}^{n}\frac{2k+1}{2k-1}\). Posons \(b_k=2k-1\). Alors \(b_{k+1}=2k+1\), et chaque facteur s’écrit \(\frac{b_{k+1}}{b_k}\). Par conséquent

\[W_n=\frac{3}{1}\cdot\frac{5}{3}\cdots\frac{2n+1}{2n-1}=\frac{b_{n+1}}{b_1}=2n+1.\]

Chaque numérateur se simplifie avec le dénominateur suivant. Pour \(n=2\), on vérifie que \(3\cdot\frac{5}{3}=5\).

Pour tout \(n\in\mathbb{N}\) et tout complexe \(q\neq 1\) :

\[\sum_{k=1}^{n}k=\frac{n(n+1)}{2},\qquad \sum_{k=1}^{n}k^{2}=\frac{n(n+1)(2n+1)}{6},\qquad \sum_{k=1}^{n}k^{3}=\frac{n^{2}(n+1)^{2}}{4},\]
\[\sum_{k=0}^{n}q^{k}=\frac{1-q^{n+1}}{1-q}.\]

Prouvons la formule des carrés par télescopage. Pour tout \(k\), \((k+1)^{3}-k^{3}=3k^{2}+3k+1\). Sommons de \(k=0\) à \(n\) : le membre de gauche télescope en \((n+1)^{3}\). Ainsi

\[(n+1)^{3}=3\sum_{k=0}^{n}k^{2}+\frac{3n(n+1)}{2}+(n+1).\]

On isole la somme des carrés, puis on factorise par \(n+1\) :

\[3\sum_{k=0}^{n}k^{2}=(n+1)\left[(n+1)^{2}-1-\frac{3n}{2}\right]=\frac{(n+1)\left(2n^{2}+n\right)}{2}.\]

On divise par \(3\) et on obtient la formule annoncée. Pour la somme géométrique, on multiplie par \(1-q\) : la somme \(\sum_{k=0}^{n}\left(q^{k}-q^{k+1}\right)\) télescope en \(1-q^{n+1}\).

On pose \(0!=1\) et \((n+1)!=(n+1)\,n!\) pour tout \(n\in\mathbb{N}\). Autrement dit, \(n!=\prod_{k=1}^{n}k\). Pour des entiers \(0\leq k\leq n\), le coefficient binomial « \(k\) parmi \(n\) » est

\[\binom{n}{k}=\frac{n!}{k!\,(n-k)!}.\]

Si \(k<0\) ou \(k>n\), on convient que \(\binom{n}{k}=0\).

Pour écrire toute une ligne sans factorielle, on passe d’un coefficient au suivant par la relation

\[\binom{n}{k+1}=\binom{n}{k}\cdot\frac{n-k}{k+1}.\]

Pour \(n=7\), on part de \(1\), puis on multiplie successivement par \(\frac{7}{1}\), \(\frac{6}{2}\) et \(\frac{5}{3}\). On obtient ainsi \(1\), \(7\), \(21\) et \(35\). La symétrie fournit ensuite le reste de la ligne : \(35\), \(21\), \(7\), \(1\).

Pour tous entiers \(0\leq k\leq n\) :

• symétrie : \(\binom{n}{n-k}=\binom{n}{k}\) ;
• valeurs extrêmes : \(\binom{n}{0}=\binom{n}{n}=1\) et \(\binom{n}{1}=n\) ;
• formule du pion : si \(1\leq k\leq n\), alors \(k\binom{n}{k}=n\binom{n-1}{k-1}\).

La symétrie se lit sur la définition : échanger \(k\) et \(n-k\) ne modifie pas le dénominateur. Pour la formule du pion, on écrit \(k\cdot\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}\). Ensuite, on sort le facteur \(n\) de \(n!\). Comme \(n-k=(n-1)-(k-1)\), on reconnaît \(n\binom{n-1}{k-1}\).

Pour tous entiers \(n\geq 0\) et \(k\geq 1\) :

\[\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}.\]

Si \(k>n+1\), les trois termes sont nuls. Si \(k=n+1\), l’égalité s’écrit \(1+0=1\). Supposons donc \(1\leq k\leq n\). On met les deux fractions au dénominateur commun \(k!\,(n+1-k)!\) :

\[\binom{n}{k-1}+\binom{n}{k}=\frac{n!\,k+n!\,(n+1-k)}{k!\,(n+1-k)!}=\frac{(n+1)!}{k!\,(n+1-k)!}.\]

On reconnaît bien \(\binom{n+1}{k}\).

Tous les coefficients binomiaux sont des entiers naturels.

Procédons par récurrence sur \(n\) avec la propriété : « pour tout \(k\in\mathbb{Z}\), \(\binom{n}{k}\in\mathbb{N}\) ». Pour \(n=0\), les seules valeurs sont \(1\) et \(0\). Supposons ensuite la propriété vraie au rang \(n\). Pour \(k\geq 1\), la formule de Pascal exprime \(\binom{n+1}{k}\) comme une somme de deux entiers naturels. Enfin, \(\binom{n+1}{0}=1\) et les coefficients d’indice négatif sont nuls. La propriété passe donc au rang \(n+1\).

Pour tous nombres complexes \(a\) et \(b\) et tout entier \(n\in\mathbb{N}\) :

\[(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}.\]

Raisonnons par récurrence sur \(n\). Pour \(n=0\), les deux membres valent \(1\). Supposons la formule vraie au rang \(n\) et multiplions par \(a+b\) :

\[(a+b)^{n+1}=\sum_{k=0}^{n}\binom{n}{k}a^{k+1}b^{n-k}+\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n+1-k}.\]

Dans la première somme, on pose \(j=k+1\) ; elle devient \(\sum_{j=1}^{n+1}\binom{n}{j-1}a^{j}b^{n+1-j}\). Grâce à la convention sur les coefficients nuls, les deux sommes peuvent ensuite courir de \(0\) à \(n+1\). On les regroupe alors terme à terme :

\[(a+b)^{n+1}=\sum_{j=0}^{n+1}\left[\binom{n}{j-1}+\binom{n}{j}\right]a^{j}b^{n+1-j}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{j}b^{n+1-j}.\]

La dernière égalité est la formule de Pascal, valable aussi pour \(j=0\) avec nos conventions. La formule est donc héréditaire.

1. Pour développer, écrire le terme général \(\binom{n}{k}a^{k}b^{n-k}\) en gardant les signes dans \(a\) et \(b\).
2. Pour isoler un coefficient, exprimer la puissance de \(x\) du terme général en fonction de \(k\), puis résoudre l’équation en \(k\).
3. Pour démontrer une identité, choisir des valeurs de \(a\) et \(b\) qui font apparaître la somme voulue, par exemple \(a=b=1\) ou \(a=-1\).

Cherchons le coefficient de \(x^{3}\) dans \((3-2x)^{6}\). Le terme général s’écrit \(\binom{6}{k}(-2x)^{k}3^{6-k}\). La puissance de \(x\) vaut \(3\) lorsque \(k=3\). Le coefficient cherché est donc

\[\binom{6}{3}(-2)^{3}3^{3}=20\times(-8)\times 27=-4320.\]

Notons que le signe vient de \((-2)^{3}\) : une puissance impaire d’un nombre négatif reste négative.

Pour tout \(n\in\mathbb{N}\), \(\sum_{k=0}^{n}\binom{n}{k}=2^{n}\). Pour tout \(n\geq 1\), \(\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=0\).

Montrons que \(\sum_{k=1}^{n}k\binom{n}{k}=n\,2^{n-1}\) pour \(n\geq 1\). D’abord, la formule du pion transforme chaque terme : \(k\binom{n}{k}=n\binom{n-1}{k-1}\). Ensuite, on pose \(j=k-1\) :

\[\sum_{k=1}^{n}k\binom{n}{k}=n\sum_{j=0}^{n-1}\binom{n-1}{j}=n\,2^{n-1}.\]

Contrôle avec \(n=3\) : \(3+2\cdot 3+3\cdot 1=12=3\cdot 4\).

• S’exercer : exercices corrigés de L1 de maths sur récurrence et coefficients binomiaux
• Bases utiles : Connecteurs, quantificateurs et types de démonstration
• Chapitre d’avant : Relations d'équivalence et relations d'ordre
• Chapitre d’après : Complexes : forme exponentielle, racines et géométrie
• Vérifier ses acquis : QCM de L1 de maths sur récurrence et coefficients binomiaux
• Contrôle corrigé en temps limité : Récurrence forte et identités binomiales : contrôle de maths en L1
• Tous les chapitres : le sommaire de la L1 de maths
• Après le bac : les maths post-bac, de la MPSI à la L3