Le cours

Résumé en cinq points

Toute partie non vide de $\N$ a un plus petit élément. C'est ce qui fonde la récurrence et le raisonnement par le plus petit contre-exemple.
Une récurrence a trois étapes nommées, et il existe trois variantes : simple, double, forte.
Dans une somme, l'indice est muet. Les outils sont la linéarité, Chasles, le changement d'indice et le télescopage.
Trois sommes à connaître par cœur : $\frac{n(n+1)}{2}$ , $\frac{n(n+1)(2n+1)}{6}$ , et la géométrique $\frac{1 - x^{n+1}}{1 - x}$ pour $x \neq 1$ .
$\binom{n}{p} = \frac{n!}{p!(n-p)!}$ est symétrique en $p$ et $n - p$ , régi par Pascal, et la formule du binôme développe $(a+b)^n$ dès que $a$ et $b$ commutent.

Pourquoi ce chapitre

C'est le chapitre du calcul propre. Une copie de concours contient en permanence des sommes indexées, des changements d'indice, des récurrences. Les points perdus viennent presque toujours de la technique et non des idées :

indice muet mal géré ;
borne oubliée ;
hérédité mal rédigée.

On y installe aussi les coefficients binomiaux et la formule du binôme, qui reviennent partout, du calcul de $(1 + \ii)^n$ aux dérivées $n$ -ièmes d'un produit avec la formule de Leibniz, en passant par les probabilités. Enfin, la propriété du plus petit élément de $\N$ justifie le principe de récurrence et sert dans de nombreuses preuves d'arithmétique.

1L'ensemble des entiers naturels

1.1Ce qu'on admet

$\N$ est l'ensemble des entiers naturels, $\Z$ celui des entiers relatifs. Le programme admet leur existence et leurs propriétés algébriques usuelles. On retient trois propriétés d'ordre, qui suffisent à tout.

Propriété 1.1Propriété fondamentale

Toute partie non vide de $\N$ possède un plus petit élément.

Propriété 1.2Conséquences

Toute partie non vide et majorée de $\N$ possède un plus grand élément.
Toute partie non vide de $\Z$ minorée possède un plus petit élément.
Toute partie non vide de $\Z$ majorée possède un plus grand élément.
Il n'existe aucun entier strictement compris entre $n$ et $n + 1$ .

1.2Lien avec la récurrence

La propriété du plus petit élément justifie le principe de récurrence.

Théorème 1.3Principe de récurrence

Hypothèses

$P(n_0)$ est vraie ;
pour tout $n \geqslant n_0$ , $P(n)$ entraîne $P(n+1)$ .

Alors $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Démonstration

Supposons par l'absurde que l'ensemble $A$ des entiers $n \geqslant n_0$ tels que $P(n)$ est fausse soit non vide. $A$ possède un plus petit élément $m$ . Comme $P(n_0)$ est vraie, $m > n_0$ , donc $m - 1 \geqslant n_0$ et $P(m-1)$ est vraie par minimalité de $m$ . L'hérédité donne alors $P(m)$ , ce qui contredit $m \in A$ . Donc $A$ est vide.

Ce raisonnement, dit de la descente ou du plus petit contre-exemple, est aussi utile en lui-même.

2Les récurrences

2.1Récurrence simple

MéthodeRécurrence simple

Pour prouver $P(n)$ pour tout $n \geqslant n_0$ :

Initialisation : vérifier $P(n_0)$ .
Hérédité : soit $n \geqslant n_0$ tel que $P(n)$ est vraie, montrer $P(n + 1)$ .
Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Exemple 2.1Somme des entiers

Pour tout $n \geqslant 1$ , $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ .

Initialisation : la somme vaut 1 et la formule donne 1. Hérédité : si la formule vaut au rang $n$ , en ajoutant $n + 1$ on obtient $\begin{aligned} \frac{n(n+1)}{2} + (n+1)\\ = \frac{(n+1)(n+2)}{2}, \end{aligned}$ qui est la formule au rang $n + 1$ .

2.2Récurrence double

MéthodeRécurrence double

Initialiser en $n_0$ et $n_0 + 1$ .
Montrer que $P(n)$ et $P(n+1)$ entraînent $P(n+2)$ .

Elle sert pour les suites vérifiant une relation liant trois termes consécutifs, par exemple $u_{n+2} = a u_{n+1} + b u_n$ .

2.3Récurrence forte

MéthodeRécurrence forte

Prendre pour hypothèse que $P(k)$ est vraie pour tout $k$ entre $n_0$ et $n$ .
En déduire $P(n+1)$ .

Elle sert quand le passage au rang suivant utilise plusieurs rangs antérieurs, ou un rang inconnu à l'avance.

Exemple 2.2Diviseur premier

Tout entier $n \geqslant 2$ admet un diviseur premier. Si $n$ est premier, il se divise lui-même. Sinon $n = ab$ avec $2 \leqslant a \leqslant n - 1$ , et l'hypothèse forte appliquée à $a$ fournit un diviseur premier de $a$ , qui divise $n$ .

2.4Erreurs classiques

Attention

Oublier l'initialisation : la propriété « $n = n + 1$ » est héréditaire et pourtant fausse.
Écrire « supposons $P(n)$ vraie pour tout $n$ », qui est la conclusion et non l'hypothèse.
Faire porter la récurrence sur une propriété trop faible : il faut parfois renforcer l'énoncé pour que l'hérédité passe.
Dans une récurrence double, oublier la seconde initialisation.

3Sommes et produits

3.1Notation

Définition 3.1Somme et produit d'une famille finie

Pour une famille finie $(a_i)_{i \in I}$ de nombres complexes, on note $\sum_{i \in I} a_i$ sa somme et $\prod_{i \in I} a_i$ son produit. Quand $I$ est vide, la somme vaut 0 et le produit vaut 1, par convention. Quand $I = \intent{1}{n}$ , on écrit $\sum_{k=1}^{n} a_k$ .

L'indice est muet : $\sum_{k=1}^{n} a_k$ et $\sum_{i=1}^{n} a_i$ désignent le même nombre.

Attention

Un indice ne doit jamais apparaître hors de la somme qui le lie. Écrire $\sum_{k=1}^{n} a_k = n a_k$ est une faute grave.

3.2Règles de calcul

Propriété 3.2Linéarité

Pour tous complexes $\lambda$ , $\mu$ : $\sum (\lambda a_k + \mu b_k) = \lambda \sum a_k + \mu \sum b_k.$ Une constante multiplicative sort, une constante additive donne $\sum_{k=1}^{n} c = nc$ .

Propriété 3.3Relation de Chasles

Pour $1 \leqslant p < n$ : $\sum_{k=1}^{n} a_k = \sum_{k=1}^{p} a_k + \sum_{k=p+1}^{n} a_k.$

Propriété 3.4Changement d'indice affine

On pose $j = k + 1$ ou $j = n - k$ . On change l'indice partout, y compris dans les bornes. Par exemple : $\sum_{k=0}^{n} a_{n-k} = \sum_{j=0}^{n} a_j.$

Propriété 3.5Somme télescopique

$\sum_{k=1}^{n} (a_{k+1} - a_k) = a_{n+1} - a_1.$ Version produit : si aucun terme ne s'annule, $\prod_{k=1}^{n} \frac{a_{k+1}}{a_k} = \frac{a_{n+1}}{a_1}$ .

Le regroupement de termes est un autre outil : séparer les indices pairs et impairs, par exemple.

Attention

Il n'existe pas de formule pour la somme d'un produit. En général $\sum a_k b_k$ n'a rien à voir avec $\left(\sum a_k\right)\left(\sum b_k\right)$ .

3.3Sommes usuelles

Propriété 3.6Sommes à connaître

$\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ ;
$\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ ;
$\displaystyle\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}$ si $x \neq 1$ , et $n + 1$ si $x = 1$ .

Le cas $x = 1$ doit toujours être traité à part.

Propriété 3.7Factorisation de $a^n - b^n$

Pour $n \geqslant 1$ : $a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{n-1-k}.$ En particulier $a^2 - b^2 = (a-b)(a+b)$ et $a^3 - b^3 = (a-b)(a^2 + ab + b^2)$ . La somme géométrique est le cas $b = 1$ et $a = x$ , à un signe près.

On peut retrouver la somme des $k^2$ par télescopage, en développant $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ et en sommant.

3.4Sommes doubles

Une somme double est une somme indexée par un ensemble de couples. Deux configurations reviennent sans cesse.

Propriété 3.8Rectangle

Quand les indices varient indépendamment, on peut intervertir les deux signes somme, et le produit de deux sommes finies se développe : $\begin{aligned} &\Big(\sum_{i=1}^{n} a_i\Big)\Big(\sum_{j=1}^{p} b_j\Big)\\ &= \sum_{i=1}^{n} \sum_{j=1}^{p} a_i b_j. \end{aligned}$

Bien changer le nom de l'un des deux indices avant de développer.

Propriété 3.9Triangle

Quand la condition est $1 \leqslant i \leqslant j \leqslant n$ , on peut sommer d'abord sur $i$ puis sur $j$ , ou l'inverse : $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j} = \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}.$

Le passage d'une écriture à l'autre est un exigible. Un dessin du domaine d'indices dans un tableau carré évite les erreurs de bornes.

Attention

Ne pas confondre $i \leqslant j$ et $i < j$ : ils diffèrent de la diagonale.

4Coefficients binomiaux

4.1Factorielle

Définition 4.1Factorielle

Pour $n \geqslant 1$ , $n!$ est le produit des entiers de 1 à $n$ , et $0! = 1$ par convention.

La croissance est très rapide : $5! = 120$ , $10!$ vaut environ $3{,}6$ millions.

4.2Définition et symétrie

Définition 4.2Coefficient binomial

Pour $n \in \N$ et $p$ entier avec $0 \leqslant p \leqslant n$ , le coefficient binomial « $p$ parmi $n$ » vaut $\binom{n}{p} = \frac{n!}{p!\,(n-p)!}.$ On pose qu'il vaut 0 si $p < 0$ ou $p > n$ , ce qui évite les cas particuliers dans les formules.

Exemple 4.3Valeurs immédiates

$\begin{aligned} \binom{n}{0} &= \binom{n}{n} = 1,\\ \binom{n}{1} &= \binom{n}{n-1} = n,\\ \binom{n}{2} &= \frac{n(n-1)}{2}. \end{aligned}$

Propriété 4.4Symétrie

$\binom{n}{p} = \binom{n}{n-p}.$ Cela se lit sur la définition, les deux factorielles du dénominateur échangeant leurs rôles.

Remarque

$\binom{n}{p}$ est le nombre de parties à $p$ éléments d'un ensemble à $n$ éléments. Cette lecture aide à retenir les formules. Sa démonstration relève du chapitre de dénombrement.

4.3Formule de Pascal

Propriété 4.5Formule de Pascal

Pour $n \geqslant 1$ et $p$ entier : $\binom{n-1}{p-1} + \binom{n-1}{p} = \binom{n}{p}.$

Elle se vérifie par mise au même dénominateur. Elle donne le triangle de Pascal, où chaque coefficient est la somme des deux situés au-dessus de lui. Elle montre au passage, par récurrence sur $n$ , que les coefficients binomiaux sont des entiers.

4.4Formule du pion

Propriété 4.6Formule du pion

Pour $1 \leqslant p \leqslant n$ : $p\binom{n}{p} = n\binom{n-1}{p-1}.$

Elle sert à calculer des sommes du type $\sum k\binom{n}{k}$ , et se vérifie directement sur les factorielles.

5Formule du binôme

5.1Énoncé

Théorème 5.1Formule du binôme

Pour tous nombres complexes $a$ et $b$ et tout entier $n \geqslant 0$ : $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.$

La démonstration se fait par récurrence sur $n$ , en utilisant la formule de Pascal.

Attention

Quand on généralisera à des matrices ou à des endomorphismes, $a$ et $b$ devront commuter. Pour des nombres complexes c'est automatique.

5.2Conséquences classiques

Avec $a = b = 1$ : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ .
Avec $a = -1$ et $b = 1$ , pour $n \geqslant 1$ : la somme alternée des $\binom{n}{k}$ est nulle. Les coefficients de rang pair et de rang impair ont donc la même somme, égale à $2^{n-1}$ .
$(1 + x)^n$ se développe de la même façon, ce qui donne des identités utiles en dérivant ou en intégrant formellement.
Avec les complexes, $(1 + \ii)^n$ se calcule de deux façons, par le binôme et par la forme trigonométrique, ce qui fournit les sommes des $\binom{n}{k}$ pour $k$ multiple de 4 et leurs variantes. C'est un exercice classique de khôlle.

5.3Exemples de calcul

Exemple 5.2Calcul de $\sum k\binom{n}{k}$

On écarte $k = 0$ , puis la formule du pion donne $k\binom{n}{k} = n\binom{n-1}{k-1}$ . La somme vaut donc $n$ fois la somme des $\binom{n-1}{j}$ pour $j$ de 0 à $n - 1$ , soit $\sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}.$

Méthodes

MéthodeRéflexes du chapitre

Avant toute récurrence, écrire explicitement la propriété $P(n)$ que l'on veut démontrer, avec le quantificateur correct.
Devant une somme inconnue, chercher d'abord un télescopage, puis une somme géométrique, puis un changement d'indice.
Pour une somme dont le terme général change de nature selon la parité, séparer les indices pairs et impairs.
Pour une somme double, dessiner le domaine des indices, puis choisir l'ordre de sommation qui rend la somme intérieure calculable.
Pour une somme contenant des coefficients binomiaux, penser au binôme, à la symétrie, à Pascal et à la formule du pion, dans cet ordre.
Vérifier une formule sur $n = 0$ , $n = 1$ et $n = 2$ avant de se lancer dans une preuve : cela détecte la plupart des erreurs de bornes.
Pour une somme, contrôler le nombre de termes : de $p$ à $n$ il y a $n - p + 1$ termes, pas $n - p$ .

Ce qu'il faut savoir refaire en khôlle

Déduire le principe de récurrence de la propriété du plus petit élément de $\N$ .
Rédiger une récurrence simple, une récurrence double et une récurrence forte, en nommant les trois étapes.
Calculer la somme des $k$ , des $k^2$ et d'une somme géométrique, en traitant le cas $x = 1$ à part.
Démontrer la factorisation de $a^n - b^n$ et en déduire la somme géométrique.
Calculer une somme par télescopage, et retrouver ainsi la somme des carrés.
Intervertir les deux sommations dans une somme triangulaire, et développer un produit de deux sommes.
Démontrer la formule de Pascal et la formule du pion à partir des factorielles.
Démontrer la formule du binôme par récurrence, et calculer $\sum \binom{n}{k}$ , $\sum (-1)^k\binom{n}{k}$ et $\sum k\binom{n}{k}$ .

Méthodes et exercices

Les résultats à connaître

Toute partie non vide de N possède un plus petit élément. Admis, c'est le seul axiome du chapitre.
Toute partie non vide et majorée de N possède un plus grand élément. Exigible avec démonstration, par passage aux majorants.
Principe de récurrence simple, double et forte. Exigibles, et le programme demande de savoir relier la récurrence simple au plus petit élément.
Somme des k de 1 à n égale n(n + 1)/2, somme des k² égale n(n + 1)(2n + 1)/6. Exigibles avec démonstration, par récurrence ou par télescopage.
Somme géométrique : Σ de k = 0 à n de x^k vaut (1 − xⁿ⁺¹)/(1 − x) si x ≠ 1, et n + 1 si x = 1. Exigible avec démonstration.
Factorisation aⁿ − bⁿ = (a − b) Σ de k = 0 à n − 1 de a^k b^n−1−k, pour n ≥ 1. Exigible avec démonstration, par télescopage.
Sommes télescopiques, changements d'indice affines, regroupement de termes. Exigibles, ce sont des techniques.
Interversion des sommations dans une somme rectangulaire et dans une somme triangulaire, produit de deux sommes finies. Exigibles.
Formule de Pascal C(n − 1, p − 1) + C(n − 1, p) = C(n, p), symétrie C(n, p) = C(n, n − p), formule du pion p C(n, p) = n C(n − 1, p − 1). Exigibles avec démonstration sur les factorielles.
Formule du binôme dans R, et par extension dans C. Exigible avec démonstration par récurrence.
Σ C(n, k) = 2ⁿ, et somme alternée nulle pour n ≥ 1. Exigibles.
L'interprétation de C(n, p) comme nombre de parties à p éléments relève du chapitre de dénombrement et est admise ici.
Hors programme : toute construction de N, récurrence sur un ordre autre que celui de N.

Clés de démonstration

Plus grand élément d'une partie majorée. Soit A non vide et majorée. L'ensemble des majorants de A dans N est non vide, il a un plus petit élément M. Si M n'était pas dans A, alors M − 1 serait encore un majorant, ce qui contredit la minimalité, sauf si M = 0, auquel cas A = {0}. Astuce : appliquer le plus petit élément à l'ensemble des majorants.

Somme des carrés par télescopage. On développe (k + 1)³ − k³ = 3k² + 3k + 1 et on somme de k = 1 à n. À gauche le télescopage donne (n + 1)³ − 1. À droite on a 3 Σ k² + 3 n(n + 1)/2 + n. On isole Σ k². Astuce : pour la somme des puissances p-ièmes, télescoper les puissances (p + 1)-ièmes.

Somme géométrique. On note S la somme et on calcule S − xS : tous les termes se détruisent sauf 1 et − xⁿ⁺¹. Donc (1 − x) S = 1 − xⁿ⁺¹, et on divise si x ≠ 1. Astuce : le décalage d'indice qui suit une multiplication par x est un télescopage caché.

Factorisation de aⁿ − bⁿ. On développe (a − b) Σ a^k b^n−1−k en deux sommes, Σ a^k+1 b^n−1−k moins Σ a^k b^n−k. Dans la première on pose j = k + 1, elle devient Σ de j = 1 à n de a^j b^n−j. La différence avec la seconde, écrite avec le même indice, est télescopique et vaut aⁿ − bⁿ. Astuce : renommer l'indice pour aligner les deux sommes.

Formule de Pascal. On met au même dénominateur p!(n − p)!. Le premier terme se réécrit (n − 1)! p / (p!(n − p)!), le second (n − 1)!(n − p)/(p!(n − p)!). La somme des numérateurs vaut (n − 1)! n = n!. Astuce : multiplier haut et bas par p dans l'un, par n − p dans l'autre.

Formule du binôme. Hérédité : (a + b)ⁿ⁺¹ = (a + b)(a + b)ⁿ = Σ C(n, k) a^k+1 b^n−k + Σ C(n, k) a^k b^n+1−k. On décale l'indice de la première somme avec j = k + 1, on isole les termes extrêmes, et Pascal regroupe les termes en a^j b^n+1−j. Astuce : garder les bornes propres, ce sont les termes extrêmes qui donnent les coefficients 1.

Interversion triangulaire. L'ensemble des couples (i, j) avec 1 ≤ i ≤ j ≤ n se décrit soit en fixant j puis i de 1 à j, soit en fixant i puis j de i à n. Les deux sommes itérées énumèrent les mêmes termes. Astuce : dessiner le triangle et lire les bornes sur le dessin.

Exemples et contre-exemples à connaître

La propriété « n = n + 1 » est héréditaire et fausse pour tout n. L'initialisation n'est pas une formalité.
La somme géométrique de raison 1 vaut n + 1. La formule (1 − xⁿ⁺¹)/(1 − x) est un 0/0 sans signification en x = 1.
De p à n il y a n − p + 1 termes. La somme des constantes c de k = 3 à 10 vaut 8c, pas 7c.
Σ a_k b_k n'est pas (Σ a_k)(Σ b_k). Pour n = 2 et tous les termes égaux à 1, on obtient 2 d'un côté et 4 de l'autre.
0! = 1 et C(n, k) = 0 si k > n. Ces conventions rendent la formule de Pascal vraie pour tout entier p, sans cas particulier.
Somme vide nulle et produit vide égal à 1. C'est ce qui rend Chasles valable sans exception et donne x⁰ = 1.
L'existence d'un diviseur premier pour tout n ≥ 2 exige une récurrence forte : le diviseur a de n auquel on applique l'hypothèse n'est pas n − 1 mais un entier inconnu à l'avance.
Une suite définie par u_n+2 = u_n+1 + u_n demande une récurrence double, avec deux initialisations. Vérifier seulement u₀ ne prouve rien.

Techniques du chapitre

Technique 1 : chercher un télescopage. Mini-exercice : Σ de k = 1 à n de 1/(k(k + 1)). On écrit 1/(k(k + 1)) = 1/k − 1/(k + 1), et la somme vaut 1 − 1/(n + 1) = n/(n + 1).

Technique 2 : changement d'indice partout. Mini-exercice : Σ de k = 1 à n de (n − k + 1). On pose j = n − k + 1. Quand k va de 1 à n, j va de n à 1, et la somme vaut Σ de j = 1 à n de j = n(n + 1)/2.

Technique 3 : séparer pairs et impairs. Mini-exercice : Σ de k = 0 à 2n de (−1)^k k. Les termes pairs donnent Σ de j = 0 à n de 2j = n(n + 1), les impairs donnent − Σ de j = 0 à n − 1 de (2j + 1) = −n². Total : n. Vérification pour n = 1 : 0 − 1 + 2 = 1.

Technique 4 : somme double triangulaire. Mini-exercice : Σ des i pour 1 ≤ i ≤ j ≤ n. On fixe j : Σ de i = 1 à j de i = j(j + 1)/2. Puis Σ de j = 1 à n de (j² + j)/2 = n(n + 1)(2n + 1)/12 + n(n + 1)/4 = n(n + 1)(n + 2)/6. Pour n = 2, on trouve 4, comme le calcul direct 1 + 1 + 2.

Technique 5 : formule du pion pour les binomiaux. Mini-exercice : Σ de k = 0 à n de C(n, k)/(k + 1). On a (k + 1) C(n + 1, k + 1) = (n + 1) C(n, k), donc C(n, k)/(k + 1) = C(n + 1, k + 1)/(n + 1). La somme vaut (2ⁿ⁺¹ − 1)/(n + 1), le terme j = 0 de Σ C(n + 1, j) manquant.

Technique 6 : rédiger une récurrence forte. Mini-exercice : tout entier n ≥ 1 est somme de puissances de 2 deux à deux distinctes. Pour n ≥ 1, soit 2^p la plus grande puissance de 2 inférieure ou égale à n, qui existe par plus grand élément. Alors n − 2^p < 2^p. Si n − 2^p = 0 c'est fini, sinon l'hypothèse forte le décompose en puissances toutes strictement inférieures à 2^p, donc distinctes de 2^p.

Technique 7 : tester une formule sur les petits cas. Mini-exercice : avant de prouver Σ k² = n(n + 1)(2n + 1)/6, vérifier n = 1 (1 = 6/6) et n = 2 (5 = 2·3·5/6). Une borne fausse se voit immédiatement.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1. Somme des cubes

Classiques de khôlle et concours · Khôlle

Montrer que pour tout n ≥ 1, Σ de k = 1 à n de k³ = (n(n + 1)/2)².

Technique récurrence simple, factorisation soignée dans l'hérédité.

Voir le corrigé

P(n) : « Σ k³ = (n(n + 1)/2)² ». Initialisation : 1 = 1.
Hérédité : soit n ≥ 1 avec P(n). Alors Σ de k = 1 à n + 1 de k³ = (n(n + 1)/2)² + (n + 1)³ = (n + 1)² (n²/4 + n + 1) = (n + 1)² (n + 2)²/4.
C'est P(n + 1). Conclusion par récurrence.

piège : Développer entièrement au lieu de factoriser par (n + 1)². Le calcul devient illisible et la faute de signe arrive.

Exercice 2. Inégalité de Bernoulli

Classiques de khôlle et concours · Khôlle

Montrer que pour tout réel x ≥ −1 et tout entier n, (1 + x)ⁿ ≥ 1 + nx.

Technique récurrence, avec attention au signe quand on multiplie une inégalité.

Voir le corrigé

Initialisation n = 0 : 1 ≥ 1.
Hérédité : soit n avec (1 + x)ⁿ ≥ 1 + nx. Comme 1 + x ≥ 0, on peut multiplier : (1 + x)ⁿ⁺¹ ≥ (1 + x)(1 + nx) = 1 + (n + 1)x + nx².
Comme nx² ≥ 0, on obtient (1 + x)ⁿ⁺¹ ≥ 1 + (n + 1)x.

piège : Multiplier l'inégalité par 1 + x sans avoir dit que ce facteur est positif. C'est exactement là que sert l'hypothèse x ≥ −1.

Exercice 3. Télescopage avec des racines

Classiques de khôlle et concours · Khôlle

Montrer que Σ de k = 1 à n de (√(k + 1) − √k) = √(n + 1) − 1, puis que Σ de k = 1 à n de 1/√k ≥ 2(√(n + 1) − 1).

Technique quantité conjuguée puis comparaison terme à terme.

Voir le corrigé

La première somme est télescopique, elle vaut √(n + 1) − √1.
Pour k ≥ 1, √(k + 1) − √k = 1/(√(k + 1) + √k), par quantité conjuguée.
Comme √(k + 1) ≥ √k, on a √(k + 1) + √k ≥ 2√k, donc √(k + 1) − √k ≤ 1/(2√k), soit 1/√k ≥ 2(√(k + 1) − √k).
En sommant de 1 à n : Σ 1/√k ≥ 2(√(n + 1) − 1). Cette somme tend donc vers l'infini avec n.

piège : Se tromper de sens en comparant √(k + 1) + √k à 2√k. Écrire l'inégalité entre les deux racines avant de passer aux inverses, qui renversent le sens.

Exercice 4. Sommes de coefficients binomiaux de pas 2

Classiques de khôlle et concours · Khôlle

Pour n ≥ 1, calculer la somme des C(n, k) pour k pair entre 0 et n, et la somme des (−1)^j C(n, 2j) pour 2j ≤ n. Pour la seconde, on utilise la forme trigonométrique de 1 + i, vue au chapitre suivant.

Technique évaluer le binôme en des valeurs bien choisies et séparer selon la parité.

Voir le corrigé

(1 + 1)ⁿ = Σ C(n, k) = 2ⁿ et (1 − 1)ⁿ = Σ (−1)^k C(n, k) = 0 car n ≥ 1.
En additionnant, les termes d'indice impair s'annulent : 2 × (somme des C(n, k) pour k pair) = 2ⁿ, d'où 2ⁿ⁻¹.
(1 + i)ⁿ = Σ C(n, k) i^k. Les puissances de i valent 1, i, −1, −i selon k modulo 4. La partie réelle ne retient que les k = 2j pairs, avec le signe (−1)^j. Donc Σ (−1)^j C(n, 2j) = Re((1 + i)ⁿ).
Comme 1 + i = √2 e^iπ/4, cette partie réelle vaut 2^n/2 cos(nπ/4).

piège : Oublier que la somme alternée est nulle seulement pour n ≥ 1, et perdre les signes dans les puissances de i.

Exercice 5. Somme double du minimum

Classiques de khôlle et concours · Khôlle

Calculer S = Σ de i = 1 à n de Σ de j = 1 à n de min(i, j).

Technique découper le carré d'indices en diagonale et deux triangles symétriques.

Voir le corrigé

Sur la diagonale i = j, le minimum vaut i, contribution Σ i = n(n + 1)/2.
Sur le triangle i < j, le minimum vaut i. Par symétrie le triangle j < i donne la même contribution. Donc S = n(n + 1)/2 + 2T avec T = Σ des i pour 1 ≤ i < j ≤ n.
À j fixé, Σ de i = 1 à j − 1 de i = j(j − 1)/2. Donc T = Σ de j = 1 à n de (j² − j)/2 = (n(n + 1)(2n + 1)/6 − n(n + 1)/2)/2 = n(n + 1)(n − 1)/6.
S = n(n + 1)/2 + n(n + 1)(n − 1)/3 = n(n + 1)(2n + 1)/6. Pour n = 2, on retrouve 1 + 1 + 1 + 2 = 5.

piège : Compter deux fois la diagonale en prenant i ≤ j et j ≤ i. Les inégalités strictes évitent le doublon.

Exercice 6. Sommes pondérées de coefficients binomiaux

Classiques de khôlle et concours · Écrit CCINP

Pour n ≥ 2, calculer Σ de k = 0 à n de k(k − 1) C(n, k), puis Σ de k = 0 à n de k² C(n, k).

Technique formule du pion appliquée deux fois, puis décomposition k² = k(k − 1) + k.

Voir le corrigé

Pour k ≥ 2, k C(n, k) = n C(n − 1, k − 1), puis (k − 1) C(n − 1, k − 1) = (n − 1) C(n − 2, k − 2). Donc k(k − 1) C(n, k) = n(n − 1) C(n − 2, k − 2).
Les termes k = 0 et k = 1 sont nuls. La première somme vaut n(n − 1) Σ de j = 0 à n − 2 de C(n − 2, j) = n(n − 1) 2ⁿ⁻².
Comme k² = k(k − 1) + k et Σ k C(n, k) = n 2ⁿ⁻¹, la seconde somme vaut n(n − 1)2ⁿ⁻² + n 2ⁿ⁻¹ = n(n + 1) 2ⁿ⁻².
Contrôle pour n = 2 : 0 + 2 + 4 = 6 et 2 × 3 × 1 = 6.

piège : Appliquer le pion à k = 0 ou k = 1, où C(n − 2, k − 2) n'a de sens que par la convention de nullité. Le plus sûr est d'écarter ces termes.

Exercice 7. Une suite définie par une somme

Classiques de khôlle et concours · Écrit CCINP

On pose u₀ = 1 et, pour n ≥ 0, u_n+1 = Σ de k = 0 à n de u_k. Montrer que u_n = 2ⁿ⁻¹ pour tout n ≥ 1.

Technique récurrence forte, car u_n+1 dépend de tous les termes précédents.

Voir le corrigé

u₁ = u₀ = 1 = 2⁰. Initialisation faite.
Soit n ≥ 1 tel que u_k = 2^k−1 pour tout k entre 1 et n. Alors u_n+1 = u₀ + Σ de k = 1 à n de 2^k−1 = 1 + (2ⁿ − 1) = 2ⁿ.
C'est la propriété au rang n + 1. Conclusion par récurrence forte.

piège : Ne supposer que u_n = 2ⁿ⁻¹ au lieu de tous les rangs de 1 à n, alors que la somme les utilise tous. Et ne pas isoler u₀, qui ne suit pas la formule.

Exercice 8. Somme des k x^k−1 sans dériver

Classiques de khôlle et concours · Écrit CCINP

Pour x ≠ 1 et n ≥ 1, calculer S = Σ de k = 1 à n de k x^k−1.

Technique multiplier par 1 − x et faire apparaître une somme géométrique par décalage.

Voir le corrigé

(1 − x) S = Σ de k = 1 à n de k x^k−1 − Σ de k = 1 à n de k x^k.
Dans la première somme, on pose j = k − 1 : Σ de j = 0 à n − 1 de (j + 1) x^j. Dans la seconde on garde k. Terme à terme, il reste 1 + Σ de k = 1 à n − 1 de x^k − n xⁿ.
Donc (1 − x) S = (1 − xⁿ)/(1 − x) − n xⁿ, puis S = (1 − (n + 1) xⁿ + n xⁿ⁺¹)/(1 − x)².
Contrôle pour n = 1 : S = 1 et le numérateur vaut (1 − x)².

piège : Perdre le terme constant 1 ou le terme − n xⁿ lors de l'alignement des deux sommes. Écrire les deux sommes avec les mêmes bornes avant de soustraire.

Exercice 9. Descente infinie

Approfondissement · Type oral Mines

Montrer que l'équation x³ + 2y³ = 4z³ n'a pas de solution en entiers relatifs autre que (0, 0, 0).

Technique plus petit élément appliqué à l'ensemble des |x| + |y| + |z| des solutions non nulles.

Voir le corrigé

Supposons qu'il existe une solution non nulle. L'ensemble des |x| + |y| + |z| pour les solutions non nulles est une partie non vide de N, elle a un plus petit élément, atteint par une solution (x, y, z) non nulle.
x³ = 4z³ − 2y³ est pair, donc x est pair, x = 2a. Alors 8a³ + 2y³ = 4z³, soit 4a³ + y³ = 2z³. Donc y est pair, y = 2b, et 4a³ + 8b³ = 2z³, soit 2a³ + 4b³ = z³. Donc z est pair, z = 2c, et a³ + 2b³ = 4c³.
(a, b, c) est une solution, non nulle car (x, y, z) = (2a, 2b, 2c) ne l'est pas, et |a| + |b| + |c| = (|x| + |y| + |z|)/2 est strictement plus petit, ce qui contredit la minimalité.

piège : Oublier de justifier que la nouvelle solution est non nulle et que l'ensemble considéré est bien une partie de N, sans quoi le plus petit élément n'existe pas.

Erreurs fréquentes

Laisser sortir un indice muet de sa somme, comme dans « Σ a_k = n a_k ». Une lettre liée par Σ n'existe plus après le signe somme.
Oublier le cas x = 1 dans une somme géométrique, ou diviser par 1 − x sans l'avoir exclu.
Changer l'indice dans le terme général mais pas dans les bornes, ou l'inverse. Le changement se fait aux trois endroits.
Écrire « supposons P(n) vraie pour tout n » dans l'hérédité, ou omettre une initialisation dans une récurrence double.
Appliquer la formule du binôme à deux objets qui ne commutent pas. Pour les nombres c'est invisible, pour les matrices cela devient faux.

Fiche de cours rédigée à partir du programme officiel de MPSI (2021), parties « Raisonnement et vocabulaire ensembliste » pour la récurrence et « Compléments de calcul algébrique et de trigonométrie », paragraphe « Sommes et produits », pour les sommes, les produits, la factorielle, les coefficients binomiaux et la formule du binôme. Toute construction et toute axiomatique de $\N$ sont hors programme.

L'ensemble N, récurrence et sommes

Résumé en cinq points

1L'ensemble des entiers naturels

1.1Ce qu'on admet

1.2Lien avec la récurrence

2Les récurrences

2.1Récurrence simple

2.2Récurrence double

2.3Récurrence forte

2.4Erreurs classiques

3Sommes et produits

3.1Notation

3.2Règles de calcul

3.3Sommes usuelles

3.4Sommes doubles

4Coefficients binomiaux

4.1Factorielle

4.2Définition et symétrie

4.3Formule de Pascal

4.4Formule du pion

5Formule du binôme

5.1Énoncé

5.2Conséquences classiques

5.3Exemples de calcul

Méthodes

Ce qu'il faut savoir refaire en khôlle

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1. Somme des cubes

Exercice 2. Inégalité de Bernoulli

Exercice 3. Télescopage avec des racines

Exercice 4. Sommes de coefficients binomiaux de pas 2

Exercice 5. Somme double du minimum

Exercice 6. Sommes pondérées de coefficients binomiaux

Exercice 7. Une suite définie par une somme

Exercice 8. Somme des k xk−1 sans dériver

Exercice 9. Descente infinie

Erreurs fréquentes

Au concours

Exercice 8. Somme des k x^k−1 sans dériver