Récurrence et égalités

3.1 La méthode

Pour démontrer une égalité par récurrence, l'hérédité suit toujours le même plan.

1. Écrire au brouillon le but : l'égalité au rang $n + 1$.
2. Partir d'un des deux membres, en général le plus compliqué, et y faire apparaître l'expression du rang $n$.
3. Remplacer grâce à l'hypothèse de récurrence, puis calculer jusqu'au but.

3.2 Le terme général d'une suite définie par récurrence

Exemple 7. Soit $(u_n)$ définie par $u_0 = 1$ et $u_{n+1} = 2u_n + 1$.

Conjecture. Les premiers termes sont $1$, $3$, $7$, $15$, $31$ : chacun est une puissance de $2$ moins $1$. On conjecture que $u_n = 2^{n+1} - 1$ pour tout $n$.

Démonstration. On note $\mathcal{P}(n)$ : « $u_n = 2^{n+1} - 1$ ».

• Initialisation. $2^1 - 1 = 1 = u_0$ : $\mathcal{P}(0)$ est vraie.
• Hérédité. Soit $n \in \mathbb{N}$ tel que $\mathcal{P}(n)$ est vraie. Le but est $u_{n+1} = 2^{n+2} - 1$. On part de $u_{n+1}$ : $u_{n+1} = 2u_n + 1 = 2\left(2^{n+1} - 1\right) + 1 = 2^{n+2} - 2 + 1 = 2^{n+2} - 1.$ $\mathcal{P}(n+1)$ est vraie.
• Conclusion. Pour tout $n \in \mathbb{N}$, $u_n = 2^{n+1} - 1$.

3.3 Des formules de sommes

Pour une somme, le rang $n + 1$ s'obtient à partir du rang $n$ en ajoutant un seul terme.

Exemple 8 (somme des nombres impairs). Montrer que, pour tout entier $n \geq 1$, $1 + 3 + 5 + \cdots + (2n - 1) = n^2.$ On le devine en calculant : $1 = 1^2$, $1 + 3 = 2^2$, $1 + 3 + 5 = 3^2$. Sur un dessin, chaque nouveau nombre impair ajoute une bande en équerre autour du carré précédent.

• Initialisation ($n = 1$) : la somme se réduit à $1 = 1^2$.
• Hérédité. Supposons $1 + 3 + \cdots + (2n - 1) = n^2$ pour un entier $n \geq 1$. Le nombre impair suivant est $2n + 1 = 2(n+1) - 1$, donc $1 + 3 + \cdots + (2n - 1) + (2n + 1) = n^2 + 2n + 1 = (n + 1)^2.$
• Conclusion. La formule est vraie pour tout $n \geq 1$.

Exemple 9 (somme des carrés). Montrer que, pour tout entier $n \geq 1$, $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.$

• Initialisation ($n = 1$) : $\dfrac{1 \times 2 \times 3}{6} = 1 = 1^2$.
• Hérédité. Supposons la formule vraie au rang $n$. Le but est $\dfrac{(n+1)(n+2)(2n+3)}{6}$, car $2(n+1) + 1 = 2n + 3$. On ajoute $(n+1)^2$ et on met $n + 1$ en facteur au lieu de tout développer : $\frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{n+1}{6}\big[n(2n+1) + 6(n+1)\big] = \frac{n+1}{6}\left(2n^2 + 7n + 6\right).$ Le trinôme $2n^2 + 7n + 6$ a pour racines $-2$ et $-\frac32$ : il se factorise en $(n+2)(2n+3)$. On obtient $\dfrac{(n+1)(n+2)(2n+3)}{6}$ : c'est la formule au rang $n + 1$.
• Conclusion. La formule est vraie pour tout $n \geq 1$.

Notation. Une somme peut s'écrire de façon concise avec le symbole $\sum$ : $1^2 + 2^2 + \cdots + n^2 = \displaystyle\sum_{k=1}^{n} k^2$. Le programme l'utilise seulement comme écriture ; dans ce chapitre, on écrit les sommes avec des points de suspension.