Chapitre 1. Le raisonnement par récurrence

I. Découverte du raisonnement par récurrence

On considère la suite de nombres $\left(u_n\right)_{n\in\mathbb{N}}$ définie par :

$u_0=1$ et pour tout entier naturel $n$, $u_{n+1}=2u_n+1$.

Ainsi, $u_0=1$ puis $u_1=2\times u_0+1=2\times1+1=3$ puis $u_2=2\times u_1+1=2\times3+1=7$ puis $u_3=2\times u_2+1=2\times7+1=15$.

Décrivons les premières valeurs de $u_n$ dans un tableau et comparons ces valeurs aux premières puissances de $2$.

Il semblerait que chaque terme de la suite soit $1$ au-dessous d'une certaine puissance de $2$. On conjecture donc ou encore on pense fortement que pour tout entier naturel $n$, $u_n=2^{n+1}-1$.

Conjecture : pour tout entier naturel $n$, $u_n=2^{n+1}-1$.

Nous avons la sensation que ce résultat est vrai mais nous ne l'avons jamais démontré et il s'agit maintenant de le montrer. Le tableau donné plus haut montre la formule quand $n$ est un entier compris entre $0$ et $10$ au sens large. Mais ce tableau ne montre pas la formule quand $n=11$. On peut bien sûr vérifier « à la main » si oui ou non le nombre $u_{11}$ est égal à $2^{12}-1$ :

$u_{11}=2\times u_{10}+1=2\times2047+1=4095=4096-1=2^{12}-1$,

et la formule est encore vraie pour $n=11$. Mais elle n'est pas démontrée pour $n=12$ …

Lançons nous maintenant dans ce que l'on appellera au paragraphe suivant, un raisonnement par récurrence. Nous ne savons pas si la formule est vraie quand $n=12$ car nous n'avons pas pris la peine de le vérifier. Par contre,

Si la formule est vraie au rang $12$, alors elle sera vraie au rang $13$.

En effet, si $u_{12}=2^{13}-1$, alors $u_{13}=2\times u_{12}+1=2\times(2^{13}-1)+1=2^{14}-2+1=2^{14}-1$. Ainsi, nous ne savons pas que la formule est vraie au rang $12$, mais nous savons que si elle est vraie au rang $12$, alors elle est encore vraie au rang $13$. De même, si la formule est vraie au rang $17$ ou encore si $u_{17}=2^{18}-1$ alors

$u_{18}=2\times u_{17}+1=2\times(2^{18}-1)+1=2^{19}-2+1=2^{19}-1$,

et la formule est alors vraie au rang $18$. Plus généralement, si on suppose que la formule est vraie pour un certain rang $n$ donné, alors la formule est automatiquement vraie au rang suivant. En effet, si on suppose que $u_n=2^{n+1}-1$, alors

$u_{n+1}=2\times u_n+1=2\times(2^{n+1}-1)+1=2^{(n+1)+1}-2+1=2^{(n+1)+1}-1$.

Ainsi, si on savait que la formule était vraie pour $n=0$ alors elle serait automatiquement vraie pour $n=1$ et si on savait que la formule était vraie pour $n=1$ alors elle serait automatiquement vraie pour $n=2$ et si on savait que la formule était vraie pour $n=2$ alors elle serait automatiquement vraie pour $n=3$ …

Finalement, il ne reste plus qu'à se convaincre que la formule est vraie quand $n=0$ car alors la formule devient vraie pour $n=1$ puis $n=2$ puis, de proche en proche, pour tout entier naturel $n$.

Comme $2^{0+1}-1=2-1=1$ et que $u_0=1$, on a effectivement $u_0=2^{0+1}-1$. Mais alors, d'après la remarque précédente, on a montré que pour tout entier naturel $n$, $u_n=2^{n+1}-1$.

Le type de raisonnement que nous avons tenu est un raisonnement par récurrence et le type de démonstration que l'on a effectué est une démonstration par récurrence. Dans le paragraphe suivant, on va formaliser ce type de démonstration.

II. Le raisonnement par récurrence

On énonce maintenant le principe du raisonnement par récurrence. On admet le théorème suivant :

Il se peut que la propriété $\mathscr{P}(n)$ ne soit pas vraie pour quelques valeurs de $n$ parmi les premières et ne commence à être vraie qu'à partir d'un certain rang $n_0$ auquel cas on utilise le théorème suivant :

L'étape qui consiste à vérifier que $\mathscr{P}(n_0)$ est vraie s'appelle l'initialisation et l'étape qui consiste à vérifier que pour tout $n\geqslant n_0$, si la propriété $\mathscr{P}(n)$ est vraie alors la propriété $\mathscr{P}(n+1)$ est vraie s'appelle l'hérédité ou encore cette étape consiste à vérifier que la propriété est héréditaire. L'hypothèse faite dans l'hérédité à savoir « si $\mathscr{P}(n)$ est vraie » s'appelle l'hypothèse de récurrence.

Exemple.

La rédaction « Soit $n\geqslant0$. Supposons que … et montrons que … » ne peut en aucun cas être remplacée par la rédaction « Supposons que pour tout $n\geqslant0$ … et montrons que … ». Cette deuxième phrase n'a pas du tout la même signification.

Une démonstration par récurrence ne consiste pas à supposer ce que l'on veut montrer.

Solution. Montrons par récurrence que pour tout entier naturel $n$, $u_n=3^n-2$.

• $u_0=-1$ et $3^0-2=1-2=-1$. Donc $u_0=3^0-1$. La formule à démontrer est vraie quand $n=0$.
• Soit $n\geqslant0$. Supposons que $u_n=3^n-2$ et montrons que $u_{n+1}=3^{n+1}-2$.
\begin{align*} u_{n+1}&=3u_n+4\\ &=3\times(3^n-2)+4\;(\text{par hypothèse de récurrence})\\ &=3^{n+1}-6+4\\ &=3^{n+1}-2. \end{align*}

On a montré par récurrence que

pour tout entier naturel $n$, $u_n=3^n-2$.

Solution. Montrons par récurrence que pour tout entier naturel $n\geqslant3$, $2^n>n+3$.

• $2^3=8$ et $3+3=6$. Donc $2^3>3+3$. L'inégalité à démontrer est vraie quand $n=3$.
• Soit $n\geqslant3$. Supposons que $2^n>n+3$ et montrons que $2^{n+1}>(n+1)+3$.
\begin{align*} 2^{n+1}&=2\times2^n\\ &>2\times(n+3)\;(\text{par hypothèse de récurrence})\\ &=2n+6=(n+1)+3+n+2\\ &>(n+1)+3. \end{align*}

On a montré par récurrence que

pour tout entier naturel $n\geqslant3$, $2^n>n+3$.

Solution. Montrons par récurrence que pour tout entier naturel $n$, $u_{n+1}\leqslant u_n$.

• $u_0=1$ puis $u_1=\dfrac{1}{3}u_0-2=\dfrac{1}{3}-2=-\dfrac{5}{3}$. Donc $u_1\leqslant u_0$. L'inégalité à démontrer est vraie quand $n=0$.
• Soit $n\geqslant0$. Supposons que $u_{n+1}\leqslant u_n$ et montrons que $u_{n+2}\leqslant u_{n+1}$. \begin{align*} u_{n+2}&=\dfrac{1}{3}u_{n+1}-2\\ &\leqslant\dfrac{1}{3}u_{n}-2\;(\text{car}\;\dfrac{1}{3}\geqslant0\;\text{et par hypothèse de récurrence})\\ &=u_{n+1}. \end{align*}

On a montré par récurrence que

pour tout entier naturel $n$, $u_{n+1}\leqslant u_n$.

Pour l'exercice suivant nous avons besoin de définir une notation. L'écriture $\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+1)}$ signifie

$\dfrac{1}{1\times2}+\dfrac{1}{2\times3}+\dfrac{1}{3\times4}+…+\dfrac{1}{(n-2)(n-1)}+\dfrac{1}{(n-1)n}+\dfrac{1}{n(n+1)}$.

$\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+1)}$ est une somme de $n$ termes. $k$ prend successivement les valeurs $1$, $2$, … , $n$ puis la fraction $\dfrac{1}{k(k+1)}$ prend successivement les valeurs $\dfrac{1}{1\times2}$, $\dfrac{1}{2\times3}$, … , $\dfrac{1}{n(n+1)}$ et enfin on additionne les $n$ fractions ainsi obtenues. Donc,

$\displaystyle\sum_{k=1}^{1}\dfrac{1}{k(k+1)}=\dfrac{1}{1\times2},\qquad\displaystyle\sum_{k=1}^{2}\dfrac{1}{k(k+1)}=\dfrac{1}{1\times2}+\dfrac{1}{2\times3},\qquad\displaystyle\sum_{k=1}^{3}\dfrac{1}{k(k+1)}=\dfrac{1}{1\times2}+\dfrac{1}{2\times3}+\dfrac{1}{3\times4}$

Enfin, on passe de la somme à $n$ termes à la somme à $n+1$ termes en ajoutant le $n+1$-ème terme :

Solution. Montrons par récurrence que pour tout entier naturel non nul $n$, $\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+1)}=\dfrac{n}{n+1}$.

• $\displaystyle\sum_{k=1}^{1}\dfrac{1}{k(k+1)}=\dfrac{1}{1\times(1+1)}=\dfrac{1}{2}$ et $\dfrac{1}{1+1}=\dfrac{1}{2}$. Donc $\displaystyle\sum_{k=1}^{1}\dfrac{1}{k(k+1)}=\dfrac{1}{1+1}$. L'égalité à démontrer est vraie quand $n=1$.
• Soit $n\geqslant1$. Supposons que $\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+1)}=\dfrac{n}{n+1}$ et montrons que $\displaystyle\sum_{k=1}^{n+1}\dfrac{1}{k(k+1)}=\dfrac{n+1}{(n+1)+1}$.
\begin{align*} \displaystyle\sum_{k=1}^{n+1}\dfrac{1}{k(k+1)}&=\left(\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+1)}\right)+\dfrac{1}{(n+1)(n+2)}\\ &=\dfrac{n}{n+1}+\dfrac{1}{(n+1)(n+2)}\;(\text{par hypothèse de récurrence})\\ &=\dfrac{n(n+2)}{(n+1)(n+2)}+\dfrac{1}{(n+1)(n+2)}=\dfrac{n(n+2)+1}{(n+1)(n+2)}\\ &=\dfrac{n^2+2n+1}{(n+1)(n+2)}=\dfrac{(n+1)^2}{(n+1)(n+2)}=\dfrac{n+1}{n+2}\\ &=\dfrac{n+1}{(n+1)+1}. \end{align*}

On a montré par récurrence que