Motifs et dénombrements

3.1 Une figure qui grandit

Avec des allumettes, on construit une rangée de carrés collés les uns aux autres. On note $a_n$ le nombre d'allumettes pour $n$ carrés. Cette suite commence au rang $1$.

Relation de récurrence. On regarde ce que change une étape de plus. Un nouveau carré partage un côté avec le précédent : il ne demande que trois allumettes. $a_{n+1} = a_n + 3, \quad \text{avec } a_1 = 4.$

Formule explicite. On compte tout d'un coup, autrement : une première allumette verticale à gauche, puis trois allumettes par carré. $a_n = 3n + 1.$ Pour cent carrés, $a_{100} = 301$, sans dessiner la rangée.

3.2 Une question de dénombrement

Dans une réunion de $n$ personnes, chacun serre la main de tous les autres, une seule fois. On note $p_n$ le nombre de poignées de main.

Relation de récurrence. Une nouvelle personne arrive dans un groupe de $n$ personnes : elle serre $n$ mains. $p_{n+1} = p_n + n.$ Cette relation dépend aussi de $n$ : elle n'est pas de la forme $u_{n+1} = f(u_n)$, mais elle permet tout autant de calculer les termes de proche en proche.

Formule explicite. Chacune des $n$ personnes serre $n - 1$ mains, ce qui fait $n(n - 1)$. Mais chaque poignée de main est comptée deux fois. $p_n = \frac{n(n - 1)}{2}.$ Pour $30$ personnes, $p_{30} = \dfrac{30 \times 29}{2} = 435$.

3.3 Une suite définie par un algorithme

Une suite peut aussi être définie par un algorithme. Le symbole « $\leftarrow$ » se lit « prend la valeur ».

a ← 4
Répéter n - 1 fois
    a ← a + 3
Fin Répéter

Pour $n = 4$, la boucle tourne trois fois : $a$ prend les valeurs $7$, $10$, puis $13$. On obtient bien $a_4 = 13$.

3.4 Passer d'un mode à un autre

Une même suite peut s'écrire de plusieurs façons. On choisit la plus pratique selon la question posée.

Pour passer de la formule explicite à la relation, on calcule la différence de deux termes consécutifs : $a_{n+1} - a_n = 3(n + 1) + 1 - (3n + 1) = 3.$

Exemple 9. Pour $c_n = n^2$, on trouve $c_{n+1} - c_n = (n + 1)^2 - n^2 = 2n + 1$. Donc $c_{n+1} = c_n + 2n + 1$. Sur une figure, on passe d'un carré de $n$ points de côté au carré suivant en ajoutant une équerre de $2n + 1$ points.