Raisonnement par récurrence

Principe du raisonnement par récurrence.

Il s'agit de montrer une propriété qui dépend de l'entier naturel $n$. Notons $P(n)$ cette propriété. 

Par exemple :

\[\displaystyle P(n) : \displaystyle{1+2+3 + \ldots + n = \frac{n(n+1)}{2}}.\]

Le principe du raisonnement par récurrence consiste à montrer d'abord $P(0)$ c'est-à-dire la propriété au rang $0$. Cette étape s'appelle l'initialisation. 

Ensuite, on suppose que $P(n)$ est vraie pour UN entier $n$ donné. Cette supposition s'appelle l'hypothèse de récurrence. 

Puis on montre $P(n+1)$. Cette étape s'appelle l'hérédité ou la transmission. 

Ces deux étapes permettent de conclure que la propriété est vraie pour TOUS les entiers naturel $n$.

Exemple 1 :

Montrer par récurrence que $\displaystyle{ \forall n \in {\Bbb N}^*, 1+2+3 + \ldots + n = \frac{n(n+1)}{2}}$.

Remarque :

Ici la propriété $P(n) : \displaystyle{1+2+3 + \ldots + n = \frac{n(n+1)}{2}}$ est à montrer pour tous les entiers $n \ge 1$ donc l'initialisation commencera à $n=1$.

• Initialisation : on a bien $\displaystyle 1 = \frac{1(1+1)}{2}$. Donc la propriété à montrer est vraie au rang $1$. 
• Hérédité : supposons que la propriété est vraie pour UN rang $n$ donné (c'est l'hypothèse de récurrence). Montrons-la au rang $n+1$. 

D'après l'hypothèse de récurrence, $\displaystyle{1+2+3 + \ldots + n = \frac{n(n+1)}{2}}$. On en déduit que $\displaystyle{1+2+3 + \ldots + n + (n+1)}$ $\displaystyle{= (1+2+3 + \ldots + n) + (n+1)}$ $\displaystyle{= \frac{n(n+1)}{2} + n+1}$. 

Or $\displaystyle{ \frac{n(n+1)}{2} + n+1}$ $\displaystyle{= \frac{n(n+1) + 2(n+1)}{2}}$ $\displaystyle{= \frac{(n+1)(n+2)}{2}}$. 

On a donc $\displaystyle{1+2+3 + \ldots + n + (n+1)}$ $\displaystyle{= \frac{(n+1)(n+1 + 1)}{2}}$. 

Ce qui prouve la propriété au rang $n+1$. 

Exemple 2 :

Montrer que pour tout réel $x$ positif et pour tout entier naturel $n$ : $(1+x)^n \ge 1+nx$.

• Initialisation : On a $(1+x)^0 = 1$ (par définition n'importe quel nombre à la puissance $0$ vaut $1$).
  

On a $1+0x = 1$. 

Comme $1 \ge 1$, on a bien $(1+x)^0 \ge 1+0.x$.

(En fait, dans le cas particulier de $n=0$, il y a même égalité.)

• Hérédité : on suppose que l'inégalité à montrer est vraie pour UN entier naturel $n$ (c'est l'hypothèse de récurrence). 
  

Montrons l'inégalité au rang $n+1$. 

Partons de l'hypothèse de récurrence: $(1+x)^n \ge 1+nx$.

Multiplions cette inégalité par $1+x$ qui est positif car $x$ l'est :

$(1+x)^n(1+x) \ge (1+nx)(1+x)$ ce qui donne $(1+x)^{n+1} \ge (1+nx)(1+x)$ $= 1+x +nx +nx^2$ $= 1 + (n+1)x + nx^2$.

Comme $nx^2 \ge 0$, on a $1 + (n+1)x + nx^2 \ge 1 + (n+1)x$. On a donc $(1+x)^{n + 1} \ge 1 + (n+1)x$.

On a donc montré la propriété au rang $n+1$.