DIGICOM

Chapitre 02

Partie 2 - Principe de réccurence

Objectif

Utiliser le principe de récurrence pour démontrer une proposition

Proposition

Une proposition est un énoncé mathématique complet qui est soit vrai soit faux.
Par exemple :

$"23 \geq 10"$ est une proposition fausse;
Alors que "Dans tout triangle rectangle, le carré de la longueur de l'hypothénuse est égale à la somme des carrés des longueurs des deux autres côtés" est une proposition vraie.

Proposition

Une proposition peut-être :

une égalité, par exemple $\mathcal{P}_n$ : $1 + 2 + \dots + 3 = \dfrac{n(n+1)}{2}$ ;
une inégalité, par exemple $\mathcal{P}_n$ : $(1 + \pi)^n \geq 1 + n\pi$ ;
une phrase, par exemple $\mathcal{P}_n$ : $n^3 - n$ est un multiple de 3

Domaine d'application

Le raisonnement par récurrence ne peut s’utiliser que lorsque l’on cherche à démontrer qu’une proposition est vraie pour tout entier naturel

n \in \mathbb{N}

tel que

n \geq n_0

Propriété

Soit

n_0 \in \mathbb{N}

. On considère la proposition

\mathcal{P}_n

défnie pour tout entier naturel

n \gt n_0

.
Si les deux conditions suivantes sont vérifées :

Initialisation : $P_n$ est vraie pour l’entier $n_0$ ;
Hérédité : pour tout entier naturel $k \leq n_0$ , « $\mathcal{P}_k$ est vraie.» implique $\mathcal{P}_{k+1}$ est vraie.

Alors on peut conclure que, pour tout

n\in \mathbb{N}

, tel que

n \geq n_0

, la proposition

\mathcal{P}_n

est vraie.

Exemple de mise en oeuvre

Démontrer que pour tout entier naturel

n \in \mathbb{N}^{*}

1 + 2 + \ldots + n = \dfrac{n(n+1)}{2}

0 - Ennoncé la proposition

Soit

n \in \mathbb{N}*

, on note

\mathcal{P}_{n}

la proposition

1+2+3 + \ldots + n = \dfrac{n(n+1)}{2}

I - Initialisation

Pour n = 1 :
D'une part, le membre de gauche de l'équalité vaut 1
D’autre part,le membre de droite de l'équalité vaut

\dfrac{1 \times 2}{2} = 1

On a ainsi montré que est

\mathcal{P}_1

vraie.

II - Hérédité

Supposons qu'il existe

k \in \mathbb{N}

, tel que

P_{k}

soit vraie.
Montrons que

P_{k+1}

est vraie;

II - Hérédité

D'après l'hypothèse de récurrence (

\mathcal{H.R.}

1+ 2 + 3 + \ldots + k = \dfrac{k(k+1)}{2}

1+ 2 + 3 + \ldots + k + \textcolor{orange}{k+1} = \dfrac{k(k+1)}{2} + \textcolor{orange}{k+1}

1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k(k+1)}{2} + \textcolor{orange}{\dfrac{2(k+1)}{2}}

1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k(k+1)+\textcolor{orange}{2(k+1)}}{2}

1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k\textcolor{orange}{(k+1)}+2\textcolor{orange}{(k+1)}}{2}

1+ 2 + 3 + \ldots + k + k+1 = \dfrac{(k+1)\big(k+2\big)}{2}

Donc la proposition

\mathcal{P}_{k+1}

est vraie.

III - Conclusion

Par le principe de récurrence, on en déduit que

P_n

est vraie pour tout

n \in N^{*}

Exercice type

Soit

(U_n)

la suite définie par

U_0 = 2

et, pour tout entier naturel

n,~ U_{n+ 1} = 0,6 U_n + 4

Démontrer par récurrence que $U_n \leq 10$ pour tout entier naturel $n$ .
On considère la suite $(V_n)$ , définie par :
$V_n = U_n - 10$

a. Montrer que la suite $(V_n)$ est géométrique. Déterminer son terme initial et sa raison
b. Déterminer l'expression de $V_n$ en fonction de $n$ . En déduire celle de $(U_n)$